**Authors:** Richard Beigel, Rao Kosaraju, and Gregory Sullivan

**Abstract:**
Consider a system of processing elements in which elements may
administer tests to other elements. We show, surprisingly, that a
constant number of rounds of parallel testing are sufficient to
identify all faults (in all cases where fault identification is
possible). We also present an
O(loglog_{n/t}*t*) algorithm with a small
constant of proportionality, where *n* denotes the total number
of processors and *t* denotes the number of faulty processors.
Both of these results improve upon the previous best, which was
O(log_{n/t}*t*) rounds.

For the problems of identifying a single faulty processor
(diagnosis-with-repair) and identifying a single good processor, we
present an oblivious constant-time algorithm using a fixed 3-regular
interconnect that tolerates a linear number of faults. This contrasts
with the well-known result that every oblivious algorithm for complete
diagnosis must use a number of rounds that is linear in *t*.