The $t/k$-Diagnosability of Star Graph Networks
Shuming Zhou, Limei Lin, Li Xu, Dajin Wang · IEEE Transactions on Computers · 2014
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${{S_n}}$) to locate all (up to${ {(k + 1)n - 3k - 1}}$) faulty processors, among which at most${ {k\, (1 \leq k \leq 3)}}$fault-free processors might be wrongly diagnosed as faulty.