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.
Abstract
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.