On self-diagnosable multiprocessor systems: diagnosis by the comparison approach

The diagnosability and diagnosis problems for a model introduced by J. Maeng and M. Malek (1981) of a self-diagnosable multiprocessor system where processors compare the results of tasks performed by other processors in the system are analyzed. A set of criteria is given for determining whether the faulty processors in the system can be diagnosed on the basis of the comparisons, and a polynomial-time algorithm is presented to identify the faulty units of such a system on the basis of the comparison results when the system is known to be diagnosable