An efficient algorithm for multiprocessor fault diagnosis using the comparison approach

AbstractIn this paper, a comparison model is considered for multiprocessor fault diagnosis. In this approach, system tasks are assigned to pairs of processors (or units) and the results are compared. These agreements and disagreements among units are the basis for identifying faulty units. Such a system is said to be t1-diagnosable if, given any complete collection of comparison outcomes, the set of faulty units can be isolated to within a set of at most t1 units, assuming that no more than t1 units can be faulty. This paper shows an optimal O(|E|) algorithm (where |E| corresponds to the number of comparisons), by which, on the basis of the collection of comparison outcomes, all the faulty units except at most one can be correctly identified and all the faulty units can be isolated to within a set of t1 or fewer units in which at most one can possibly be fault-free