Probabilistic diagnosis of multiprocessor systems with arbitrary connectivity

Presents probabilistic fault diagnosis algorithms and a comparison-based fault model for homogeneous systems where the probability of correct diagnosis approaches one when the number of tests conducted on each processor grows slightly faster than log N. For a comparison-based model, this means that each processor has to compare its result on test jobs with a constant number of other processors where the number of test jobs grows slightly faster than log N. These algorithms do not require the neighborhood of processors to grow and thus could be used on systems with arbitrary processor graphs with the in-degree of each processor being greater than a specified value, which in most practical situations is two. Also, diagnosis decisions are made in a distributed fashion. The asymptotic performance of the algorithm is considered.<>