The Diagnosability and 1-Good-Neighbor Conditional Diagnosability of Hypercubes with Missing Links and Broken-Down Nodes

[[abstract]]In system-level diagnosis, we propose to further classify faulty nodes into two categories. One category is the “ordinary” faulty nodes – they are malfunctioning, but they still participate in the diagnosis, rendering unreliable test results. The other category contains nodes that are completely broken down so that they cannot test other nodes, and they cannot be tested by other nodes either. In this paper, we study the diagnosability and 1-good-neighbor conditional diagnosability of hypercubes with both ordinary faulty nodes and broken-down nodes. Let S be a set of missing links and broken-down nodes in a hypercube with . We prove that the diagnosability of is for . Furthermore, we show that the 1-good-neighbor conditional diagnosability of is for , which is the maximum number of faulty nodes can guarantee to identify, under the condition that every fault-free node has at least a fault-free neighbor