The t/k-Diagnosability of Star Graph Networks

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.