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 ba sis of previous test results. Fault-free testers give always correct test r esults, while faulty testers are completely unreliable. The aim of diagnosi s 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 were found to be significantly smaller than that of classical (one-step) diagnosis. (C) 1999 John Wiley & Sons, Inc.