Fault Tolerability Analysis of Hypercubes Based on g-Extra H-Structure Fault Pattern

With the rapid development of multiprocessor systems, fault tolerability plays a vital role in measuring the reliability of multiprocessor systems. The traditional connectivity and conditional connectivity are excellent indicators to measure the reliability of multiprocessor system’s underlying network. However, the cardinality and the number of connected components of the survival network are indispensable to measure the robustness of the interconnection networks. Therefore, [Formula: see text]-extra [Formula: see text]-structure connectivity has been proposed. Motivated by the [Formula: see text]-extra [Formula: see text]-structure connectivity, the g-extra H-structure diagnosability is proposed in this paper to evaluate the fault diagnostic capability of multiprocessor systems successively. In this paper, we determine the [Formula: see text]-extra [Formula: see text]-structure connectivity and diagnosability of hypercube, where [Formula: see text] and [Formula: see text]. Furthermore, we develop a novel fault diagnosis algorithm to detect all faulty units and demonstrate its efficiency through extensive experimental evaluations.