Authors: Richard Beigel, William Hurwood, and Nabil Kahale
Abstract: Consider a set of n processors that can communicate with each other. Assume that each processor can be either ``good'' or ``faulty''. Also assume that the processors can test each other. We consider how to use parallel testing rounds to identify the faulty processors, given an upper bound t on their number. We prove that 4 rounds are necessary and sufficient when 2sqrt(2n) ≤ t ≤ 0.03n (for n sufficiently large). Furthermore, at least 5 rounds are necessary when t ≤ 0.49n (for n sufficiently large), and 10 rounds are sufficient when t < 0.5n (for all n). (It is well known that no general solution is possible when t ≥ 0.5n.)