Local Diagnosis Algorithms for Multiprocessor Systems Under the Comparison Diagnosis Model

Cheng-Kuan Lin, Yuan-Hsiang Teng, Jiann-Mean Tan, Lih-Hsing Hsu

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


An efficient diagnosis is very important for a multiprocessor system. The ability to identify all the faulty devices in a multiprocessor system is known as diagnosability. In the comparison model, the diagnosis is performed by sending two identical signals from a processor to a pair of distinct neighbors, and then comparing their responses. Sengupta and Dahbura proposed a polynomial-time algorithm with time complexity O(N-5) to diagnose a system with a total number N of processors under the comparison model. Recently, some concepts, such as the conditional diagnosability and the local diagnosability, are concerned with the measure which is able to better reflect fault patterns in real systems. In this paper, we propose a specific structure, the balanced wind-bell-tree, and give an algorithm to determine the fault status of each processor for conditional local diagnosis under the comparison model. According to our results, a specific t-connected network with the balanced wind-bell-tree structure is conditionally (2t - 1)*-diagnosable, and the time complexity to diagnose all the faulty processors is O(N(log N)(2)) with our algorithm, where N is the total number of the processors in the network.
Original languageEnglish
Pages (from-to)800-810
Number of pages11
JournalIEEE Transactions on Reliability
Issue number4
StatePublished - Dec 2013


  • Comparison diagnosis model; conditional diagnosability; local diagnosis; system diagnosis

Fingerprint Dive into the research topics of 'Local Diagnosis Algorithms for Multiprocessor Systems Under the Comparison Diagnosis Model'. Together they form a unique fingerprint.

Cite this