TY - JOUR

T1 - Conditional (t,k)-Diagnosis in graphs by using the comparison diagnosis model

AU - Chen, Chun An

AU - Chang, Guey Yun

AU - Hsieh, Sun Yuan

N1 - Publisher Copyright:
© 2014 IEEE.

PY - 2015/6/1

Y1 - 2015/6/1

N2 - (t,k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least k faulty processors be identified and repaired in each iteration when there are at most t faulty processors, where t ≥ k. Based on the assumption that each vertex is adjacent to at least one fault-free vertex, the conditional (t,k)-diagnosis of graphs was investigated by using the comparison diagnosis model. Lower bounds on the conditional (t, k)-diagnosability of graphs were derived, and applied to obtain the following results. 1) Symmetric d-dimensional grids are conditionally (N/2d+1 - 1,2d - 1)-diagnosable when d ≥ 2 and N (the number of vertices)≥ 4d. 2) Symmetric d-dimensional tori are conditionally (1/5(N + min{8/5 N2/3, 2N-20/15} - 2),6)-diagnosable when d = 2 and N ≥ 49 and (N/2d+1 - 1,4d - 2)-diagnosable when d ≥ 3 and N ≥ 4d. 3) Cube-connected cycles are conditionally (N/4 - 1, 4)-diagnosable. 4) k-ary trees are conditionally (N/k+1 - 1, 1)-diagnosable.

AB - (t,k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least k faulty processors be identified and repaired in each iteration when there are at most t faulty processors, where t ≥ k. Based on the assumption that each vertex is adjacent to at least one fault-free vertex, the conditional (t,k)-diagnosis of graphs was investigated by using the comparison diagnosis model. Lower bounds on the conditional (t, k)-diagnosability of graphs were derived, and applied to obtain the following results. 1) Symmetric d-dimensional grids are conditionally (N/2d+1 - 1,2d - 1)-diagnosable when d ≥ 2 and N (the number of vertices)≥ 4d. 2) Symmetric d-dimensional tori are conditionally (1/5(N + min{8/5 N2/3, 2N-20/15} - 2),6)-diagnosable when d = 2 and N ≥ 49 and (N/2d+1 - 1,4d - 2)-diagnosable when d ≥ 3 and N ≥ 4d. 3) Cube-connected cycles are conditionally (N/4 - 1, 4)-diagnosable. 4) k-ary trees are conditionally (N/k+1 - 1, 1)-diagnosable.

KW - (t,k)-diagnosis

KW - Conditional fault diagnosis

KW - MM∗ model

KW - fault-tolerance

KW - multiprocessor systems

KW - sequential diagnosis

KW - system-level diagnosis

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

U2 - 10.1109/TC.2014.2345407

DO - 10.1109/TC.2014.2345407

M3 - 期刊論文

AN - SCOPUS:84946240764

VL - 64

SP - 1622

EP - 1632

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 6

M1 - 6871331

ER -