Echtle, Klaus; Chen, Y.; Bucken, W.:

Efficient Algorithms for System Diagnosis with Both Processor and Comparator Faults

In: IEEE Transactions on Parallel and Distributed Systems
Los Alamitos: IEEE Computer Society Press (1993), S. 371-381
Buchaufsatz / Kapitel / Fach: Wirtschaftswissenschaften
Abstract:
For the comparison-based self-diagnosis of multiprocessor systems, an extended modelthat considers both processor and comparator faults is presented. It is shown that in thismodel the system diagnosability is t>or=Z delta /2Z, where delta is the minimum vertexdegree of the system graph. However, if the number of faulty comparators is assumednot to exceed the number of faulty processors, the diagnosability of the model reachest>or= delta . An optimal O( mod E mod ) algorithm, where E is the set of comparators, isgiven for identifying all faulty processors and comparators, provided that the total number of faulty components does not exceed the system diagnosability, and an O(mod E mod)/sup 2/ algorithm for the case t>or= delta is also presented. These efficient algorithms determine the faulty processors by calculating each processor's weight, which is mainly defined by the number of adjacent relative tests stating 'agreement'. After sorting the processors according to their weights, the algorithms determine all faulty components by separating the sorted processor list.