Capital Area Theory Seminar

Consider a set of processors that can communicate with each other. Each processor is either "good" or "faulty," and the processors can be used to test each other. (A good tester will tell whether the testee is good or faulty. A faulty tester may lie.)

Assuming that no processors fail during testing and that a strict majority of the processors are good, we present a parallel algorithm that determines which processors are good and which are faulty in 10 rounds of testing (independent of the number of processors).

The algorithm above requires that the status of each processor (good or faulty) be static. But, in a huge system, we may expect a few processors to fail in each round. Dynamic faults make diagnosis substantially more difficult. In our dynamic fault model all processors are initially good, at most t fail per round, and s may be repaired per round. If s < t, then eventually almost all processors may be faulty. However, if s > t, we give an algorithm that guarantees that (at most) O(tlogt) processors are faulty at any one time.

The work above is joint with Will Hurwood. We will also sketch joint work with Bin Fu on diagnosing intermittent faults.

Contact: Vincenzo Liberatore (liberato@umiacs.umd.edu)