A Comparison Fault Diagnosis Algorithm for Star Networks

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

• Fault diagnosis
• star network
• Hamiltonian cycle
• the comparison model
• multiprocessor system