The conditional diagnosability of crossed cubes under the comparison model

Abstract

The growing size of the multiprocessor systems increases their vulnerability to component failures. It is crucial to locate and replace the faulty processors to maintain the system's high reliability. The fault diagnosis is the process of identifying faulty processors in a system through testing. The conditional diagnosis requires that for each processor v in a system, all the processors that are directly connected to v do not fail simultaneously. In this paper, we show that the conditional diagnosability of the crossed cubes CQ _n under the comparison diagnosis model is 3n−5 when n≥7. Hence, the conditional diagnosability of CQ _n is three times larger than its classical diagnosability.

Keywords:

• conditional diagnosability
• comparison diagnosis model
• crossed cubes

1998 AMS Subject Classification :

• 05C40

Acknowledgements

The author is grateful to the two reviewers for their valuable comments that have improved the quality of this paper. This work was partially supported by the Natural Science Funds of Fujian Province, Grant Nos 2007F3025 and 2007J0316, and the Foundation for Key Teacher of Fujian Normal University, Grant No. 2008100208.