Abstract
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 $Q_{n}$, under the PMC model. We will show that in $Q_{n}$ ($n\geq 7$), the detectability is $2n-1$ for the minimal bipartite subgraph $K_{1,1}$, and $4n-5$ for the 4-node cycle $C_{4}$. Notably, detectability consistently exceeds traditional diagnosability, tolerating more faulty nodes. We have also designed, validated, and implemented detection algorithms of $O(n\cdot 2^{n-1})$ complexity to detect faulty $K_{1,1}$ and $C_{4}$ in $Q_{n}$. Simulations show a 100% detection rate, with effectiveness maintained even in lower-dimensional $Q_{n}$ where theoretical assumptions do not fully hold.
Funding Information
  • National Natural Science Foundation of China (62262032)
  • National Natural Science Foundation of China (61862035)
  • National Natural Science Foundation of China (61562046)
  • Natural Science Foundation of Ji’an City (20255-061656)

This publication has 25 references indexed in Scilit: