Almost certain diagnosis for intermittently faulty systems

The authors present and analyze a uniformly probabilistic model for the self-diagnosis capabilities of a multiprocessor system. In this model an individual processor fails with probability p and a fault-free processor testing a faulty processor detects a fault with probability q, modeling the situation in which processors can be intermittently faulty or the situation where tests are not capable of detecting all possible faults within a processor. They present an efficient algorithm which utilizes a relatively small number of tests (given by any function dominating n log n where n is the number of processors) and achieves correct diagnosis with high probability. They obtain a nearly matching lower bound which shows that no algorithm can achieve correct diagnosis with high probability in systems which conduct a number of tests dominated by n log n. Examples of systems which perform a modest number of tests are given in which the probability of correct diagnosis for the authors´ algorithm is very nearly one.<>