Sort:
Regular Paper Issue
The t/s-Diagnosability and Diagnostic Strategy of Balanced Hypercube Under Two Classic Diagnostic Models
Journal of Computer Science and Technology 2024, 39(5): 1207-1222
Published: 05 December 2024
Abstract Collect

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 BHn(n4) is ((2n+1)g/2g/22)/((2n+1)g/2g/22+(g2))-diagnosable under both the Preparata, Metze, and Chien (PMC) and MM* models for 4g/2n. Moreover, we propose two effective t/s-diagnosis algorithms under the PMC and MM* models with time complexity O(NlogN) and O(N(logN)2) ( N=22n is the order of BHn), respectively. Finally, comparison results indicate that t/s-diagnosability strengthens the self-diagnosable capability of the system compared with traditional diagnosabilities.

Total 1