A Fast Pessimistic Diagnosis Algorithm for Hypercube-Like Networks under the Comparison Model

Liang-Cheng Ye, Jia-Rong Liang, Hai Xiang Lin

Research output: Contribution to journalArticleScientificpeer-review

13 Citations (Scopus)

Abstract

Diagnosis by comparison is a realistic approach to detect faults of multiprocessor systems. This paper considers a pessimistic diagnostic strategy for hypercube-like multiprocessor systems under the comparison model. The pessimistic strategy is a diagnostic process whereby all faulty nodes can be correctly identified and at most one fault-free node may be misjudged as a faulty node. We propose a pessimistic diagnosis algorithm based on the largest component in the faulty system. For a system with N=2n nodes and n≥5 , when the number of faulty nodes is bounded by 2n−2 , the algorithm can correctly identify all nodes except at most one node left undiagnosed. The time complexity of the algorithm is O(Nlog2N) .
Original languageEnglish
Pages (from-to)2884-2888
Number of pages5
JournalIEEE Transactions on Computers
Volume65
Issue number9
DOIs
Publication statusPublished - 2016

Keywords

  • system-level diagnosis
  • Pessimistic diagnosis
  • hypercube-like networks
  • the comparison model

Fingerprint

Dive into the research topics of 'A Fast Pessimistic Diagnosis Algorithm for Hypercube-Like Networks under the Comparison Model'. Together they form a unique fingerprint.

Cite this