The t/s-Diagnosability and Diagnostic Strategy of Balanced Hypercube Under Two Classic Diagnostic Models

Fault diagnosis plays a crucial role in the fault tolerability assessment of an interconnection network, which is of great value in the design and maintenance of large-scale multiprocessor systems. A t/s-diagnostic strategy, as the generalization of the t/t-diagnostic strategy, refers to the self-diagnosis of a multiprocessor system in which all faulty vertices can be identified in a set of size at most s in the presence of at most t faulty vertices. In this work, we show that the balanced hypercube BH_n\;\; (n\geqslant 4) is ((2n+1)\left \lceil g/2\right \rceil-\left \lceil g/2\right \rceil^2)/((2n+1)\left \lceil g/2\right \rceil-\left \lceil g/2\right \rceil^2+(g-2))-diagnosable under both the Preparata, Metze, and Chien (PMC) and MM^* models for 4\leqslant \left \lceil g/2\right \rceil\leqslant n. Moreover, we propose two effective t/s-diagnosis algorithms under the PMC and MM^* models with time complexity O(N\rm logN) and O(N(\rm logN)^2) (N=2^2n is the order of BH_n), respectively. Finally, comparison results indicate that t/s-diagnosability strengthens the self-diagnosable capability of the system compared with traditional diagnosabilities.