Conditional diagnosability and strong diagnosability of shuffle-cubes under the comparison model

Abstract

The growing size of multiprocessor systems increases the vulnerability to component failures. It is crucial to locate and replace faulty processors to maintain the system's high reliability. Processor fault diagnosis is essential to the reliability of a multiprocessor system and the diagnosabilities of many well-known networks (such as hierarchical hypercubes and crossed cubes [S. Zhou, L. Lin and J.-M. Xu, Conditional fault diagnosis of hierarchical hypercubes, Int. J. Comput. Math. 89(16) (2012), pp. 2152–2164 and S. Zhou, The conditional diagnosability of crossed cubes under the comparison model, Int. J. Comput. Math. 87(15) (2010), pp. 3387–3396]) have been investigated in the literature. A system is t-diagnosable if all faulty nodes can be identified without replacement when the number of faults does not exceed t, where t is some positive integer. Furthermore, a system is strongly t-diagnosable if it is t-diagnosable and can achieve (t+1)-diagnosability except for the case where a node's neighbours are all faulty. In addition, conditional diagnosability has been widely accepted as a new measure of diagnosability by assuming that any fault-set cannot contain all neighbours of any node in a multiprocessor system. In this paper, we determine the conditional diagnosability and strong diagnosability of an n-dimensional shuffle-cube SQ_n, a variant of hypercube for multiprocessor systems, under the comparison model. We show that the conditional diagnosability of shuffle-cube SQ_n (n=4k+2 and k≥2) is 3n−9, and SQ_n is strongly n-diagnosable under the comparison model.

Keywords:

• fault tolerance
• conditional diagnosability
• strong diagnosability
• comparison model
• shuffle-cubes

2010 AMS Subject Classifications::

• 05C90
• 05C40

Acknowledgements

This work was partly supported by the National Natural Science Foundation of China (No. 61072080), Natural Science Foundation of Fujian Province (Nos. 2013J01221, 2013J01222, JA12073) and Fujian Normal University Innovative Research Team (No. IRTL1207).