G - Good Neighbor Conditional Diagnosis Of Hypercube Networks

The fault diagnosis and analysis of large multiprocessor system plays a vital role in reliability calculation. The diagnosablity of a system is defined as the maximum number of faulty processors that the system can guarantee to identify, which is a parameter to measure fault diagnosis ability of multiprocessor systems. The traditional diagnosablity has generally been assumed that any subset of processors can potentially fail at the same time. However, for large multiprocessor system, the failure probability that all the neighbors of a vertex is very small. As a consequence, It cannot precisely evaluate the self-diagnosable ability of parallel computer system. To overcome the shortcoming, Lai et al. proposed the conditional diagnosability, by claiming the property that any faulty set cannot contain all neighbors of any processor. Similarly, Peng et al. proposed the g-good-neighbor conditional diagnosability, which restricted every fault-free node containing at least g fault-free neighbors. Simultaneously, they study the-good-neighbor conditional diagnosability of hypercubes.In the area of diagnosability, the PMC model and MM* model are two well-known and widely used fault diagnosis models. Hypercube is one of most common interconnection networks in a multiprocessor system. Exchanged hypercube and k-ary n-cubes are two important transmutation networks. This paper study the g-good-neighbor conditional diagnosability of exchanged hypercube and k-ary n-cubes under the two models. We proved that:(1) Let 1 ￡ s￡ t, 0 ￡ g￡ s. Then the g-good-neighbor conditional diagnosablity of exchange hypercube under the PMC model and MM* model, (EH(,)) 2g( 2) 1gt s t =s + -g -;(2) Let n32, 0 ￡ g￡ n. Then the g-good-neighbor conditional diagnosablity of dual cube DCn under the PMC model and MM* model, (DC) 2g( 2) 1g nt =n + -g -.(3) Let 0 ￡ g￡ n, n33, k34. Then the g-good-neighbor conditional diagnosablity of k-ary n-cubes knQ under the PMC model and MM* model, ( ) ( )2 1 2k gg nt Q =n -g +. My conclusions suggest that if we restrict every fault-free processor containing at least g fault-free neighbors, the number of fault processor in the multiprocessor will have a significant increase.