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 $B{H}_n(n⩾4)$ is $((2n+1)\lceil g/2\rceil -{\lceil g/2\rceil }^2)/((2n+1)\lceil g/2\rceil -{\lceil g/2\rceil }^2+(g-2))$-diagnosable under both the Preparata, Metze, and Chien (PMC) and MM^* models for $4⩽\lceil g/2\rceil ⩽n$. Moreover, we propose two effective $t/s$-diagnosis algorithms under the PMC and MM^* models with time complexity $O(N\mathrm{l}\mathrm{o}\mathrm{g}N)$ and $O(N(\mathrm{l}\mathrm{o}\mathrm{g}N{)}^2)$ ( $N=2^{2n}$ is the order of $B{H}_n$), respectively. Finally, comparison results indicate that $t/s$-diagnosability strengthens the self-diagnosable capability of the system compared with traditional diagnosabilities.