TY - GEN
T1 - Determining the conditional diagnosability of k-ary n-cubes under the MM* model
AU - Hsieh, Sun Yuan
AU - Kao, Chi Ya
PY - 2011
Y1 - 2011
N2 - 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 Qk n. Then we apply them to show that the conditional diagnosability of Qk n under the comparison diagnosis model is tc(Qk n) = 6n-5 for k ≥ 4 and n ≤ 4.
AB - 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 Qk n. Then we apply them to show that the conditional diagnosability of Qk n under the comparison diagnosis model is tc(Qk n) = 6n-5 for k ≥ 4 and n ≤ 4.
UR - http://www.scopus.com/inward/record.url?scp=79961133998&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79961133998&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22212-2_8
DO - 10.1007/978-3-642-22212-2_8
M3 - Conference contribution
AN - SCOPUS:79961133998
SN - 9783642222115
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 78
EP - 88
BT - Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011, Proceedings
T2 - 18th Colloquium on Structural Information and Communication Complexity, SIROCCO 2011
Y2 - 26 June 2011 through 29 June 2011
ER -