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 ⩾ 4) is ((2n + 1) ⌈g/2⌉ − ⌈g/2⌉²)/((2n + 1) ⌈g/2⌉ − ⌈g/2⌉² + (g − 2))-diagnosable under both the Preparata, Metze, and Chien (PMC) and MM* models for 4 ⩽ ⌈g/2⌉ ⩽ n. Moreover, we propose two effective t/s-diagnosis algorithms under the PMC and MM* models with time complexity O(NlogN) and O(N(logN)²) (N = 2²ⁿ 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.