Distributed probabilistic fault diagnosis for multiprocessorsystems

摘要

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