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 ([26], 1996) claimed that an n-dimensional Star Graph (denoted Sn), a well-studied interconnection model for multiprocessor systems, is ((k + 1)n – 3k – 2)/k-diagnosable. Recently, Chen and Liu ([5], 2012) found counterexamples for the diagnosability obtained in [26], without further pursuing the cause of the flawed result.
In this paper, we provide a new, complete proof that an n-dimensional Star Graph is actually ((k + 1)n – 3k – 1)/k-diagnosable, where 1 ≤ k ≤ 3, and investigate the reason that caused the flawed result in [26]. 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.