Locating faults in a constant number of parallel testing rounds
Richard Beigel, S. Rao Kosaraju, G. F. Sullican · 1989
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(log log 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. 1 Introduction Consider a system composed of many processing element...