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(loglogn/tt) 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(logn/tt) 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.