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 thediagnosabilityis 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 theDetectabilityof 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 is2n − 1for the minimal bipartite subgraphK1,1, and4n − 5for the 4-node cycleC4. Notably, detectability consistently exceeds traditional diagnosability, tolerating more faulty nodes. We have also designed, validated, and implemented detection algorithms ofO(n·2n−1)complexity to detect faultyK1,1andC4inQn. Simulations show a 100% detection rate, with effectiveness maintained even in lower-dimensionalQnwhere theoretical assumptions do not fully hold.