Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds

Authors: Richard Beigel, Grigorii Margulis, and Daniel A. Spielman.

Bibliographic Information: In Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993.


Consider a set of processors, $V$, that can communicate with each other. Assume that each processor can be either ``good'' or ``faulty''. Also assume that the processors can be used to test each other. We provide a parallel algorithm that determines which processors are good and which are faulty in 32 rounds of testing, provided that a strict majority of the processors are good.
You can download this paper as Postscript, compressed Postscript, PDF, or compressed PDF.