Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model

Research output: Contribution to journalArticlepeer-review

94 Scopus citations

Abstract

In [10], Sengupta and Dahbura discussed how to characterize a diagnosable system under the comparison diagnosis model proposed by Maeng and Malek and a polynomial algorithm was given to identify the faulty processors provided that the system's diagnosability is known. However, for a general system, the determination of its diagnosability is not algorithmically easy. This paper proves that, for the important hypercube-structured multiprocessor systems (n-cubes), the diagnosability under the comparison model is n when n≥5. The paper also studies the diagnosability of enhanced hypercube, which is obtained by adding 2 n-1 more links to a regular hypercube of 2 n processors. It is shown that the augmented communication ability among processors also increases the system's diagnosability under the comparison model. We will prove that the diagnosability is n+1 for an enhanced hypercube when n≥6.

Original languageEnglish
Pages (from-to)1369-1374
Number of pages6
JournalIEEE Transactions on Computers
Volume48
Issue number12
DOIs
StatePublished - 1 Dec 1999

Fingerprint Dive into the research topics of 'Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model'. Together they form a unique fingerprint.

Cite this