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

Fault diagnosis plays an crucial role in the fault-tolerance 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 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\geq 4) is (2n+1)\left \lceil \fracg2\right \rceil-\left \lceil \fracg2\right \rceil^2/(2n+1)\left \lceil \fracg2\right \rceil-\left \lceil \fracg2\right \rceil^2+(g-2)-diagnosable under both PMC and MM^* model for 4\leq \left \lceil \fracg2\right \rceil\leq n. Moreover, we propose two effective t/s-diagnosis algorithms under PMC and MM^* model with time complexity O(N\rm logN) and O(N(\rm logN)^2), where 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.