<i>t</i>/<i>k</i>-Diagnosability of Regular Networks under the Comparison Model

Abstract

As multiprocessor systems continue to grow in processor scale, the incidence of faults also increases. As a result, fault diagnosis is becoming a key mechanism for maintaining the normal operation of multiprocessor systems. To explore more effective diagnostic methods, Somani et al. introduced a generalized pessimistic diagnostic strategy, named t/k-diagnosis, in which all faulty nodes are isolated in a set of nodes and at most k fault-free nodes are misdiagnosed, provided that the quantity of faults is limited by t. By imposing certain conditions or restrictions, the t/k-diagnosability of some regular networks under the Preparata, Metze, and Chien (PMC) model has been determined. However, the t/k-diagnosability of many networks under the comparison model remains unidentified. In this paper, we provide new insights into the study of t/k-diagnosability under the comparison model. After introducing some new notions, such as the 0-test unit, 0-test set and 0-test subgraph, under the comparison model, we study the relationship in a system G between the 0-test subgraphs and the components of G−F, where F is the set of faulty nodes, and we obtain some important correlation properties. Based on these results, we study t/k-diagnosability under the comparison model. As a result, the t/k-diagnosability of some regular interconnection networks can be efficiently determined.

Keywords

• <i>t</i>/<i>k</i>-diagnosability
• <i>t</i>/<i>k</i>-diagnosis algorithm
• interconnection networks
• comparison model