Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model

In [10], Sengupta and Dahbura discussed how to characterize a diagnosable system under the comparison diagnosis model proposed by Maeng and Malek [7] 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 greater than or equal to 5. The paper also studies the diagnosability of enhanced hypercube [11], 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 greater than or equal to 6.