### 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 |

### Fingerprint

### Keywords

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

### Cite this

*IEEE Transactions on Computers*,

*64*(2), 547-555. [6684152]. https://doi.org/10.1109/TC.2013.228

}

*IEEE Transactions on Computers*, vol. 64, no. 2, 6684152, pp. 547-555. https://doi.org/10.1109/TC.2013.228

**The t/k-Diagnosability of Star Graph Networks.** / Zhou, Shuming; Lin, Limei; Xu, Li; Wang, Dajin.

Research output: Contribution to journal › Article › Research › peer-review

TY - JOUR

T1 - The t/k-Diagnosability of Star Graph Networks

AU - Zhou, Shuming

AU - Lin, Limei

AU - Xu, Li

AU - Wang, Dajin

PY - 2015/2/1

Y1 - 2015/2/1

N2 - 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.

AB - 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.

KW - Interconnection networks

KW - multiprocessor systems

KW - star graphs

KW - system-level diagnosis

KW - t/k-diagnostic strategy

UR - http://www.scopus.com/inward/record.url?scp=84951276711&partnerID=8YFLogxK

U2 - 10.1109/TC.2013.228

DO - 10.1109/TC.2013.228

M3 - Article

VL - 64

SP - 547

EP - 555

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 2

M1 - 6684152

ER -