The diagnosability of the k-ary n-cubes using the pessimistic strategy

Abstract

The pessimistic strategy, also called the t ₁/t ₁-diagnosis strategy, allows to contain all faulty vertices and at most one fault-free vertex. However, the degree of the diagnosability of a system increases quickly using the pessimistic strategy. In this paper, we consider the k-ary n-cube, which is an important hypercube variant, and show that the 3-ary n-cube and k-ary n-cube with k≥4 are (4n−3)/(4n−3)-diagnosable and (4n−2)/(4n−2)-diagnosable, respectively. Finally, we obtain the degree of the diagnosability of the tori using the pessimistic strategy.

Keywords:

• k-ary n-cubes
• tori
• t ₁/t ₁-diagnosability
• PMC model
• interconnection networks
• pessimistic strategy

2010 AMS Subject Classification:

• 05C90

Acknowledgement

This work was supported by the National Natural Science Foundation of China under Grant No. 11101322.