t/k-Diagnosability of Regular Networks under the Comparison Model
Open Access
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 -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 -diagnosability of some regular networks under the Preparata, Metze, and Chien (PMC) model has been determined. However, the -diagnosability of many networks under the comparison model remains unidentified. In this paper, we provide new insights into the study of -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 , where F is the set of faulty nodes, and we obtain some important correlation properties. Based on these results, we study -diagnosability under the comparison model. As a result, the -diagnosability of some regular interconnection networks can be efficiently determined.
Keywords
Funding Information
- National Natural Science Foundation of China (61862003)
This publication has 15 references indexed in Scilit:
- The t/s-diagnosability and t/s-diagnosis algorithm of folded hypercube under the PMC/MM* modelTheoretical Computer Science, 2021
- On g-extra connectivity of hypercube-like networksJournal of Computer and System Sciences, 2017
- The $t/k$-Diagnosability of Star Graph NetworksIEEE Transactions on Computers, 2013
- Reliability Evaluation of BC NetworksIEEE Transactions on Computers, 2012
- The t/k-diagnosability of the BC graphsIEEE Transactions on Computers, 2005
- On diagnosability of large fault sets in regular topology-based computer systemsIEEE Transactions on Computers, 1996
- On self-diagnosable multiprocessor systems: diagnosis by the comparison approachIEEE Transactions on Computers, 1992
- Properties and performance of folded hypercubesIEEE Transactions on Parallel and Distributed Systems, 1991
- A Theory of Diagnosability of Digital SystemsIEEE Transactions on Computers, 1976
- On the Connection Assignment Problem of Diagnosable SystemsIEEE Transactions on Electronic Computers, 1967