Fault diagnosis in a small constant number of parallel testing rounds
Richard Beigel, Григорий Александрович Маргулис, Daniel A. Spielman · 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, pre Tided that a strict majority of the processors are good.