.png){kind=icon}
.png){kind=icon}
Return
An efficient two-stage diagnostic algorithm for assessing system reliability
.png){kind=icon}
PRE
AI
DOI：10.1016/j.tcs.2025.115679.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Assessing the diagnosability of multiprocessor systems is vital for maintaining reliability and fault-tolerance, especially in extensive interconnection networks where precise reliability assessments are crucial for system stability and resilience against processor failures. In this paper, we introduce a novel diagnosability metric called h-extra r-component diagnosability, which extends traditional models by considering both component-level robustness and structural constraints. Specifically, for a graph G, a vertex subset F & Iuml; V(G) is termed an h-extra r-component vertex-cut if G-F is disconnected with at least r connected components, each containing at least h + 1 vertices. The h-extra r-component diagnosability of G, denoted by th r(G), is defined as the maximum integer t such that G is conditionally t-diagnosable under this constraint. We establish theoretical characterization for hypercube networks Qn under the condition that there does not exist exactly one isolated node in Qn-(F1 boolean OR F2) for two distinct sets F1, F2. Specifically, we show that 4n-8 <= t12(Qn) <= 4n-7 for n >= 7 and t13(Qn) = 6n-15 for n >= 13 under the MM* diagnostic model. To enhance fault identification efficiency, we propose a two-stage diagnosis algorithm (TSDA-MM*), leveraging network structural properties to improve diagnostic accuracy and efficiency. Extensive simulation experiments on hypercube networks and the data center networks Bcube(n, k) demonstrate that TSDA-MM* achieves high performance in terms of Accuracy, True Negative Rate, True Positive Rate, and Precision, thereby providing a promising solution for practical fault diagnosis in large-scale systems.
Keywords:
Multiprocessor systems
h-extra r-component diagnosability
Hypercube
MM* model
Journal
IF:
1
Papers:
248
Citations:
1.0W