Conditional (t, k)-Diagnosis under the PMC model

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


In this paper, assuming that each vertex is neighboring to at least one fault-free vertex, we investigate the (t,k)-diagnosability of a graph G under the PMC model. Lower bounds on the numeric degrees of (t,k)-diagnosability are suggested when G is a general graph or G is a regular graph. In particular, the following results are obtained. Symmetric d-dimensional grids are (N-m\over 2d, min m, 2d-1-diagnosable, where d≥ 2, 1≤ m≤ 2d-1, and N are the number of vertices. Symmetric d-dimensional tori are (N+0.62 2/3-2/4,1)-diagnosable if d=2, and (N-m 2d m, 4d-2)-diagnosable if d≥ 3, where 1≤ m≤ 4d-2. Hypercubes are (N-2 N+2 N ,2 N-2)-diagnosable. Cube-connected cycles are (N-m 3, m, 4)-diagnosable, where 1≤ m ≤ 4; k-ary trees are (N-1 k, 1)-diagnosable.

Original languageEnglish
Article number5733340
Pages (from-to)1797-1803
Number of pages7
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number11
StatePublished - 2011


  • (t, k)-diagnosis
  • Conditional fault
  • PMC model
  • fault-tolerance
  • multiprocessor system
  • sequential diagnosis
  • system-level diagnosis


Dive into the research topics of 'Conditional (t, k)-Diagnosis under the PMC model'. Together they form a unique fingerprint.

Cite this