Distributed probabilistic fault diagnosis for multiprocessor systems

A class of n-unit multiprocessor systems with O(n log n) interconnecting links is constructed, and a distributed probabilistic fault diagnosis algorithm whose probability of correctness converges to 1 as n → ∞ is proposed. For small probability of unit failure, a distributed diagnosis whose probability also converges to 1 as the size of the system grows is proposed for the hypercube. On the other hand, it is proved that if a class of systems has fewer than kn log n links for a small constant k, the probability of correctness of every fault diagnosis converges to 0 as n → ∞. By combining the probabilistic and the distributed approach the authors' model of fault diagnosis removes the major drawbacks of the PMC (Preparata-Metze-Chien) model: the assumption of tests with complete fault coverage and the assumption of a fault-free central monitoring unit capable of performing diagnosis.