g-Good-Neighbor Conditional Diagnosability and g-Extra Conditional Diagnosability of Hypercubes Under Symmetric PMC Model
Fault diagnosis plays a very important role in maintaining the reliability of multiprocessor systems,and the diagno-sability is an important measure of the diagnosis capability of the system.Except for the traditional diagnosability,there are also conditional diagnosability,such as g-good-neighbor conditional diagnosability,g-extra conditional diagnosability,etc.Where g-good-neighbor conditional diagnosability is defined under the condition that every fault-free vertex has at least g fault-free neigh-bors,and g-extra conditional diagnosability is defined under the condition that every fault-free component contains more than g vertices.Fault diagnosis needs to be performed under a specific diagnosis model,such as PMC model,symmetric PMC model,in which the symmetric PMC model is a new diagnosis model proposed by adding two assumptions to the PMC model.The n-dimen-sional hypercube has many excellent properties,so it has been widely studied by researchers.At present,there are a number of diagnosability studies under the PMC models,but there is a lack of diagnosability studies under the symmetric PMC models.This paper first investigates the upper and lower bounds for the g-good-neighbor conditional diagnosability of hypercubes under the symmetric PMC model,with an upper bound of 2g+1(n-g-1)+2g-1 when n≥4 and 0≤g≤n-4 and a lower bound of(2n-2g+1+1)2g-1+(n-g)2g-1-1 when g≥0 and n≥max{g+4,2g+1-2-g-g-1}.Also study the upper and lower bounds for the g-extra conditional diagnosability of hypercubes under the symmetric PMC model,the upper bound is 2n(g+1)-5g-2C2g-2 when n≥4 and 0≤g≤n-4,and the lower bound is 3/2n(g+1)-g-5/2 C2g+1-1 when n ≥4 and 0≤g≤min{n-4,([)2/3n(])}.Fi-nally,the correctness of the relevant theoretical conclusions is verified by simulation experiments.
万方数据
维普
