The t/k-Diagnosability of Star Graph Networks

Shuming Zhou, Limei Lin, Li Xu, Dajin Wang

Research output: Contribution to journalArticlepeer-review

63 Scopus citations


The {{t/k}}-diagnosis is a diagnostic strategy at system level that can significantly enhance the system's self-diagnosing capability. It can detect up to {{t}} faulty processors (or nodes, units) which might include at most {{k}} misdiagnosed processors, where { {k}} is typically a small number. Somani and Peleg (, 1996) claimed that an n-dimensional Star Graph (denoted {{S-n}} ), a well-studied interconnection model for multiprocessor systems, is {{((k + 1)n-3k-2)/k}}-diagnosable. Recently, Chen and Liu (, 2012) found counterexamples for the diagnosability obtained in, without further pursuing the cause of the flawed result. In this paper, we provide a new, complete proof that an {\mbi {n}}-dimensional Star Graph is actually {{((k + 1)n-3k-1)/k}}-diagnosable, where {{1 \leq k \leq 3}}, and investigate the reason that caused the flawed result in . Based on our newly obtained fault-tolerance properties, we will also outline an { {O(N \log N)}} diagnostic algorithm ({ {N = n!}} is the number of nodes in {{Sn}} ) to locate all (up to { {(k + 1)n-3k-1}} ) faulty processors, among which at most { {k\, (1 ≤ k ≤ 3)}} fault-free processors might be wrongly diagnosed as faulty.

Original languageEnglish
Article number6684152
Pages (from-to)547-555
Number of pages9
JournalIEEE Transactions on Computers
Issue number2
StatePublished - Feb 2015


  • Interconnection networks
  • multiprocessor systems
  • star graphs
  • system-level diagnosis
  • t/k-diagnostic strategy


Dive into the research topics of 'The t/k-Diagnosability of Star Graph Networks'. Together they form a unique fingerprint.

Cite this