Determining the Conditional Diagnosability of k-Ary n-Cubes Under the MM Model

Processor fault diagnosis plays an important role for measuring the reliability of multiprocessor systems, and the diagnosability of many well-known interconnection networks has been investigated widely. Conditional diagnosability is a novel measure of diagnosability, which is introduced by Lai et al., by adding an additional condition that any faulty set cannot contain all the neighbors of any vertex in a system. The class of k-ary n-cubes contains as special cases many topologies important to parallel processing, such as rings, hypercubes, and tori. In this paper, we study some topological properties of the k-ary n-cube, denoted by Q(n)(k). Then we apply them to show that the conditional diagnosability of Q(n)(k) under the comparison diagnosis model is t(c)(Q(n)(k)) = 6n-5 for k >= 4 and n >= 4.