TY - GEN

T1 - Computing the (t,k)-diagnosability of component-composition graphs and its application

AU - Hsieh, Sun Yuan

AU - Chen, Chun An

PY - 2010/12/1

Y1 - 2010/12/1

N2 - (t,k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least k faulty processors should be identified and repaired in each iteration provided there are at most t faulty processors, where t ≥ k. Let κ(G) and n(G) be the node connectivity and the number of nodes in G, respectively. We show that the class of m-dimensional component-composition graphs G for m ≥ 4 is (Ω(h),κ(G))-diagnosable, where h = 2 m-2 x lg (m-1)/m-1 if 2m-1 ≤ n(G) < m!; and h = 2m-2 if n(G) ≥ m!. Based on this result, the (t,k)-diagnosability of numerous multiprocessor systems can be computed efficiently.

AB - (t,k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least k faulty processors should be identified and repaired in each iteration provided there are at most t faulty processors, where t ≥ k. Let κ(G) and n(G) be the node connectivity and the number of nodes in G, respectively. We show that the class of m-dimensional component-composition graphs G for m ≥ 4 is (Ω(h),κ(G))-diagnosable, where h = 2 m-2 x lg (m-1)/m-1 if 2m-1 ≤ n(G) < m!; and h = 2m-2 if n(G) ≥ m!. Based on this result, the (t,k)-diagnosability of numerous multiprocessor systems can be computed efficiently.

UR - http://www.scopus.com/inward/record.url?scp=78650855442&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650855442&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17514-5_31

DO - 10.1007/978-3-642-17514-5_31

M3 - Conference contribution

AN - SCOPUS:78650855442

SN - 3642175163

SN - 9783642175169

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 363

EP - 374

BT - Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings

T2 - 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010

Y2 - 15 December 2010 through 17 December 2010

ER -