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 -