Strong diagnosability of regular networks under the comparison model

摘要

Diagnosability has played an important role in the reliability of multiprocessor systems. The strongly τ-diagnosable system is (τ + 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 τ-regular and τ-connected networks under the comparison model. We show that a τ-regular and τ-connected multiprocessor system with at least 2τ + 6 nodes, for τ ≥ 4, is strongly f-diagnosable under the comparison model if the following two conditions hold: (1) the system is triangle free, and (2) there are at most t - 2 common neighbors for each pair of distinct nodes in the system.