Characterization of t_diagnosable systems based on the generalized comparison model and a parallel algorithm for diagnosis

A model, named the generalized comparison model, is introduced for system level fault diagnosis. It allows a processor to be the comparator of itself and another processor, and combines the advantages of both the classical PMC model and the Maeng/Malek model. Based on this model, the problem of t-diagnosis ability of multiprocessor systems is analyzed, the characterization of t-diagnosable systems is presented and a new necessary and sufficient conditions for the system to be t-diagnosable are proven. Once a multiprocessor system is judged to be t-diagnosable, the following problem is to identify all the faulty processors. It is shown that the problem of identifying the set of faulty processors in the system is equivalent to the problem of finding a minimum traversal of a hypergraph which is constructed according to the interconnection graph and the comparison graph of a given multiprocessor system. A special case is considered and a parallel algorithm for system level fault diagnosis is given. This algorithm is fully distributive and optimal with respect to the number of message transmissions.