The t/k-Diagnosability of Star Graph Networks

Shuming Zhou, Limei Lin, Li Xu, Dajin Wang

Research output: Contribution to journalArticle

26 Citations (Scopus)

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 languageEnglish
Article number6684152
Pages (from-to)547-555
Number of pages9
JournalIEEE Transactions on Computers
Volume64
Issue number2
DOIs
StatePublished - 1 Feb 2015

Fingerprint

Diagnosability
Star Graph
Stars
n-dimensional
Diagnostics
Multiprocessor Systems
Vertex of a graph
Fault tolerance
Fault Tolerance
Interconnection
Counterexample
Fault
Unit
Model
Strategy

Keywords

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

Cite this

Zhou, Shuming ; Lin, Limei ; Xu, Li ; Wang, Dajin. / The t/k-Diagnosability of Star Graph Networks. In: IEEE Transactions on Computers. 2015 ; Vol. 64, No. 2. pp. 547-555.
@article{3a87251d0ee546918da8ddf257adba2d,
title = "The t/k-Diagnosability of Star Graph Networks",
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.",
keywords = "Interconnection networks, multiprocessor systems, star graphs, system-level diagnosis, t/k-diagnostic strategy",
author = "Shuming Zhou and Limei Lin and Li Xu and Dajin Wang",
year = "2015",
month = "2",
day = "1",
doi = "10.1109/TC.2013.228",
language = "English",
volume = "64",
pages = "547--555",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "2",

}

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

In: IEEE Transactions on Computers, Vol. 64, No. 2, 6684152, 01.02.2015, p. 547-555.

Research output: Contribution to journalArticle

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

AN - SCOPUS:84951276711

VL - 64

SP - 547

EP - 555

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 2

M1 - 6684152

ER -