Detecting Faulty Substructures in Networks

The traditional, well-known system-level fault diagnosis is to precisely identify faulty nodes in a network via mutual testing between the nodes, and the diagnosability is the maximum allowed number of faulty nodes for correct diagnosis. This paper proposes a new scheme that focuses on detecting whether a given critical substructure (e.g., a specific cycle or path) contains any faulty node. If the detecting outcome is “Yes”, the entire substructure is deemed as faulty, regardless of how many faulty nodes, and where they are in the substructure. This approach is often more cost-effective and technically feasible than pinpointing every faulty node. We name the maximum allowed number of faulty nodes for this strategy to work as the Detectability of the network, as opposed to the diagnosability. We study the detectability for the hypercube Qn, under the PMC model. We will show that in Qn (n ≥ 7), the detectability is 2n − 1 for the minimal bipartite subgraph K1,1, and 4n − 5 for the 4-node cycle C4. Notably, detectability consistently exceeds traditional diagnosability, tolerating more faulty nodes. We have also designed, validated, and implemented detection algorithms of O(n · 2ⁿ⁻¹) complexity to detect faulty K1,1 and C4 in Qn. Simulations show a 100% detection rate, with effectiveness maintained even in lower-dimensional Qn where theoretical assumptions do not fully hold.