## Abstract

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 language | English |
---|---|

Article number | 6684152 |

Pages (from-to) | 547-555 |

Number of pages | 9 |

Journal | IEEE Transactions on Computers |

Volume | 64 |

Issue number | 2 |

DOIs | |

State | Published - 1 Feb 2015 |

## Keywords

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