TY - JOUR
T1 - Conditional (t,k)-Diagnosis in Regular and Irregular Graphs under the Comparison Diagnosis Model
AU - Wei, Chia Chen
AU - Chen, Chun An
AU - Hsieh, Sun Yuan
PY - 2018/3/1
Y1 - 2018/3/1
N2 - Assume that there are at most t faulty vertices. A system is conditionally (t,k)-diagnosable if at least k faulty vertices (or all faulty vertices if fewer than k faulty vertices remain) can be identified in each iteration under the assumption that every vertex is adjacent to at least one fault-free vertex. Let κc(G) be the conditional vertex connectivity of G, which measures the vertex connectivity of G according to the assumption that every vertex is adjacent to at least one fault-free vertex. Let Δ (G) be the maximum degrees of the given graph G. When a graph G satisfies the condition that for any pair of vertices with distance two has at least two common neighbors in G, we show the following two results: 1) An r -regular network G containing N vertices is conditionally (N+√ 4κ (G)N}{(r+1)(r-1)}}-2}{r+1},κc(G)) -diagnosable, where r ≥ 3 and N ≥ (r+1)(25r-9)}{4κ (G)}. 2) An irregular network G containing N vertices is conditionally (NΔ (G)+1}-1,κc(G))-diagnosable. By applying the above results to multiprocessor systems, we can measure conditional (t,k)-diagnosabilities for augmented cubes, folded hypercubes, balanced hypercubes, and exchanged hypercubes.
AB - Assume that there are at most t faulty vertices. A system is conditionally (t,k)-diagnosable if at least k faulty vertices (or all faulty vertices if fewer than k faulty vertices remain) can be identified in each iteration under the assumption that every vertex is adjacent to at least one fault-free vertex. Let κc(G) be the conditional vertex connectivity of G, which measures the vertex connectivity of G according to the assumption that every vertex is adjacent to at least one fault-free vertex. Let Δ (G) be the maximum degrees of the given graph G. When a graph G satisfies the condition that for any pair of vertices with distance two has at least two common neighbors in G, we show the following two results: 1) An r -regular network G containing N vertices is conditionally (N+√ 4κ (G)N}{(r+1)(r-1)}}-2}{r+1},κc(G)) -diagnosable, where r ≥ 3 and N ≥ (r+1)(25r-9)}{4κ (G)}. 2) An irregular network G containing N vertices is conditionally (NΔ (G)+1}-1,κc(G))-diagnosable. By applying the above results to multiprocessor systems, we can measure conditional (t,k)-diagnosabilities for augmented cubes, folded hypercubes, balanced hypercubes, and exchanged hypercubes.
UR - http://www.scopus.com/inward/record.url?scp=85043779778&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85043779778&partnerID=8YFLogxK
U2 - 10.1109/TDSC.2016.2585489
DO - 10.1109/TDSC.2016.2585489
M3 - Article
AN - SCOPUS:85043779778
VL - 15
SP - 351
EP - 356
JO - IEEE Transactions on Dependable and Secure Computing
JF - IEEE Transactions on Dependable and Secure Computing
SN - 1545-5971
IS - 2
ER -