Pessimistic Fault Diagnosis Algorithm for Hypercube-Like Networks Under the BGM Model
摘要
Faulty processors inevitably exist in multi-processor systems, and the existence of faulty processors will seriously affect the stability, reliability and dependability of the system. It is necessary to quickly and accurately determine the state of the processors in the system. In practice, the pessimistic strategy is more widely accepted, which assumes that at most one fault-free node is misidentified as faulty. However, in recent years, there have been limited studies on pessimistic fault diagnosability and diagnosis algorithms based on BGM models. In this paper, we determine that the pessimistic diagnosability for hypercube-like networks is \(t_{1}/t_{1} = (2n-2)\) under the BGM model. Then, we explore the method of determining node state through local diagnostic information based on the twin-star structure. This method can determine the state of at least one of a pair of neighbor nodes, even if there are \((2n-2)\) faulty nodes in the twin-star. Finally, we propose a system-level pessimistic fault diagnosis algorithm for hypercube-like networks based on the BGM model. The algorithm employs a local fault diagnosis strategy to determine node states. Simulation experiments show that our algorithm can accurately and quickly determine the status of nodes in the system.