Strong Diagnosability of Regular Networks Under the Comparison Model

Abstract

Diagnosability has played an important role in the reliability of multiprocessor systems. The strongly t -diagnosable system is (t+1t+1) diagnosable except when all of the neighbors of a node are simultaneously faulty. In this paper, we discuss the in-depth properties of diagnosability for t -regular and t -connected networks under the comparison model. We show that a t -regular and t -connected multiprocessor system with at least 2t+62t+6 nodes, for t⩾4t⩾4, is strongly t -diagnosable under the comparison model if the following two conditions hold: (1) the system is triangle free, and (2) there are at most t−2t−2 common neighbors for each pair of distinct nodes in the system.