On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach

This paper analyzes the diagnosability and diagnosis problems for a model introduced in [2] of a self-diagnosable multiprocessor system where processors compare the results of tasks performed by other processors in the system. In this paper, 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.