A Comparison Fault Diagnosis Algorithm for Star Networks
Open Access
- 29 June 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 9, 94214-94223
Abstract
Fault diagnosis for a multiprocessor system is a process of identifying the faulty nodes in the system and is an important issue on the reliability of the system. As to the problem that there are few effective algorithms to diagnose faulty nodes in a given star network system in the literature, this paper proposes a precise fault diagnosis algorithm to identify faulty nodes in a star network system with a given syndrome under the comparison model. Such an algorithm contains three main parts. In the first part, we present an algorithm called Partition-Cycle for partitioning a cycle into sequences based on a given syndrome of the cycle. In the second part, we introduce an algorithm called Digout to diagnose these cycle sequences obtained the first part, which can diagnose each node in the cycle to be faulty or fault-free or unknown. In the third part, we design a diagnosis algorithm called Star-Digout to diagnose faulty nodes in an $n$ -dimensional ( $n\geqslant 6$ ) star networks, which is proved to contain a cycle that contains all nodes in the network and is not the same two nodes. Our theoretical analysis shows the time complexity of the diagnosis algorithm is $O(n!)$ . Our simulation results show that our algorithm is a precise diagnosis algorithm for a star network system.Keywords
Funding Information
- Natural Science Foundation of China (61862003, 61761006)
- Natural Science Foundation of the Guangxi Zhuang Autonomous Region of China (2018GXNSFDA281052)
This publication has 30 references indexed in Scilit:
- A Fast Pessimistic Diagnosis Algorithm for Hypercube-Like Networks under the Comparison ModelIEEE Transactions on Computers, 2015
- Five-Round Adaptive Diagnosis in Hamiltonian NetworksIEEE Transactions on Parallel and Distributed Systems, 2014
- Structural Properties and Conditional Diagnosability of Star Graphs by Using the PMC ModelIEEE Transactions on Parallel and Distributed Systems, 2013
- A Scalable Comparison-Based Diagnosis Algorithm for Hypercube-Like NetworksIEEE Transactions on Reliability, 2013
- Relating Diagnosability, Strong Diagnosability and Conditional Diagnosability of Strong NetworksIEEE Transactions on Computers, 2013
- A Systematic Algorithm for Identifying Faults on Hypercube-Like Networks Under the Comparison ModelIEEE Transactions on Reliability, 2012
- Strong Diagnosability and Conditional Diagnosability of Augmented Cubes Under the Comparison Diagnosis ModelIEEE Transactions on Reliability, 2011
- Diagnosability of Two-Matching Composition Networks under the MM{}^{\ast} ModelIEEE Transactions on Dependable and Secure Computing, 2010
- Diagnosability of star graphs under the comparison diagnosis modelInformation Processing Letters, 2005
- Sequential Diagnosis of Processor Array SystemsIEEE Transactions on Reliability, 2004