Optimal adaptive fault diagnosis of hypercubes

System level fault diagnosis deals with the problem of identifying component failures in a multiprocessor system. Each processor is either faulty or fault-free, and the objective is to find out the fault status of each processor in the network by letting the processors test each other. A test of a processor by another processor is possible if they are connected in the system. If the tester itself is fault-free, it always reports the fault status of the testee, but if the tester is faulty, the result of the test cannot be trusted. We show that for the hypercube multiprocessor system of dimension n, in which at most n processors are faulty, adaptive diagnosis is possible using at most 2(n) + n - 1 tests, which improves earlier bounds and is optimal. We also present an algorithm which diagnoses the hypercube in 4 testing rounds, where each processor is scheduled for at most one test of each round.