A tree structure for local diagnosis in multiprocessor systems under the comparison model

Meirun Chen, Cheng Kuan Lin*, Kung Jui Pai

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Diagnosability is an important indicator to measure the reliability of multiprocessor systems. If we focus on the status of a particular node, instead of doing global diagnosis, Hsu and Tan introduced the concept of local diagnosis and proposed an extended star structure to diagnose a node under the comparison model. Usually, there is a gap between the local diagnosability and the lower bound guaranteed by the extended star structure mentioned above. In this paper, we propose a new testing structure and a corresponding diagnosis algorithm to diagnose a node under the comparison model and better evaluate the local diagnosability. The local diagnosability of a node is upper bounded by its degree in the system. If the local diagnosability of each node equals to its degree in the system, then we say this system has the strong local diagnosability property. Based on the new structure, we provide two sufficient conditions for a multiprocessor system to have the strong local diagnosability property. As applications, we show that the n-dimensional star graph Sn and pancake graph Pn with faulty links have the strong local diagnosability property no matter how many edges are faulty, provided that each node connects to at least three fault-free links. Moreover, we show that Sn and Pn keep the strong local diagnosability property even if they have up to 3n−12 faulty links, assuming that each node connects to at least two fault-free links. Simulations are presented to show the performance of our tree structure.

Original languageEnglish
Article number114444
JournalTheoretical Computer Science
Volume992
DOIs
StatePublished - 21 Apr 2024

Keywords

  • Comparison model
  • Local diagnosability
  • Pancake graph
  • Star graph

Fingerprint

Dive into the research topics of 'A tree structure for local diagnosis in multiprocessor systems under the comparison model'. Together they form a unique fingerprint.

Cite this