An efficient two-stage diagnostic algorithm for assessing system reliability

C.T. Liang

doi:10.1016/j.tcs.2025.115679

Return

An efficient two-stage diagnostic algorithm for assessing system reliability

2025-12-01

PRE

DOI：10.1016/j.tcs.2025.115679

Original

Original request for help

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