Node-edge hybrid diagnosability and conditional node-edge hybrid diagnosability under the HPMC* model

Abstract Connectivity and diagnosability are widely recognized as crucial parameters for assessing the reliability of multiprocessor systems. Traditionally, connectivity has been classified into two distinct types: node connectivity and edge connectivity. In addition, system-level fault diagnosis theories have typically assumed that communication link faults do not occur, disregarding the potential coexistence of processor failures and communication link faults. In this paper, we propose a novel hybrid model called the HPMC* (Hybrid Preparata, Metze, and Chien) model, which no longer adheres to the stringent assumptions. We introduce the concepts of hybrid connectivity and super hybrid connectivity, and determine the hybrid connectivity of general graphs as well as the super hybrid connectivity of bijective connection (BC) networks. Motivated by these connectivity concepts, we present two novel hybrid fault diagnosis strategies: node-edge hybrid diagnosability and conditional node-edge hybrid diagnosability. These theories address the simultaneous diagnosis of node and edge faults, improving fault diagnosis capability of multiprocessor systems. Additionally, we determine the node-edge hybrid diagnosability of general graphs under the HPMC* model and develop an effective node-edge hybrid $t$-diagnosis algorithm. Finally, we establish a relationship between conditional node-edge hybrid diagnosability and super hybrid connectivity. As a result, we determine the conditional node-edge hybrid diagnosabilities of BC networks.