We consider the problem of adaptive fault diagnosis in hypercube multiproce
ssor systems. Processors perform tests on one another and later tests can b
e scheduled on the basis of previous test results. Fault-free testers corre
ctly identify the fault status of tested processors, while faulty testers c
an give arbitrary test results. The goal is to identify correctly the statu
s of all processors, assuming that the number of faults does not exceed the
hypercube dimension. We propose an adaptive diagnosis algorithm whose effi
ciency is drastically better than that of any previously known strategies.
While the worst-case number of tests for any of them exceeds 2(n) log n for
an n-dimensional hypercube, our method uses at most 2(n) + 3n/2 tests in t
he worst case. We can also modify our algorithm to improve the number of te
sting rounds. By slightly increasing the number of tests to 2(n) + (n + 1)(
2) (still a much better performance than 2(n) log n), we can carry out diag
nosis in at most 11 rounds in the worst case (as opposed to over n rounds i
n the best previously known strategy).