G-good-neighbor diagnosability under the modified comparison model for multiprocessor systems

• Published in: Theoretical computer science 2025-02, Vol.1028, p.115027, Article 115027
• Main Authors: Wang, Mu-Jiang-Shan, Xiang, Dong, Hsieh, Sun-Yuan
• Format: Article
• Language: English
• Subjects: Diagnosability; Diagnosis model; Diagnostic algorithm; Fault diagnosis; g-good-neighbor; Hypercube; Model design; Multiprocessor system; Reliability; System diagnosis; The MC model
• ISSN: 0304-3975
• DOI: 10.1016/j.tcs.2024.115027

Diagnosing faults in multiprocessor systems has long been significant due to its performance impact and its blend of Graph Theory and Computer Science concepts. In 2012, Peng et al. introduced the g-good-neighbor diagnosability, ensuring every fault-free node has at least g fault-free neighbors. This concept, gaining traction over the years, has led to extensive research on the connectivity and diagnosability of many prominent multiprocessor systems. In this paper, we introduce a novel comparison model, the MC model, for multiprocessor systems. This model integrates the strengths of both the PMC and MM⁎ models, optimizing computing power and time. We present an algorithm detailing the MC model's operations and establish the conditions for a multiprocessor system G to be g-good-neighbor t-diagnosable under the MC model. A general method to determine a G's g-good-neighbor diagnosability under the MC model is also provided. We further highlight the MC model's advantages over the PMC and MM (including MM⁎) models. Lastly, we apply the MC model to Hypercube, determining its g-good-neighbor diagnosability.