Authors: Richard Beigel, Grigorii Margulis, and Daniel Spielman
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.
Download Full Paper