Optimal adaptive fault diagnosis for simple multiprocessor systems

We studied adaptive system-level fault diagnosis for multiprocessor systems. Processors can test each other and future tests can be selected on the basis of previous test results. Fault-free testers give always correct test results, while faulty testers are completely unreliable. The aim of diagnosis is to determine correctly the fault status of all processors. We present adaptive diagnosis algorithms for systems modeled by trees, rings, and tori. These algorithms use the smallest possible number of tests in each case. Our results also imply optimal diagnosis for more general systems, assuming a small number of faults. The cost of adaptive diagnosis was found to be significantly smaller than that of classical (one-step) diagnosis.