Fault diagnosis in a flash
Richard Beigel, William Hurwood, Nabil Kahalé · 2002
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 2/spl radic/(2n)/spl les/0.03n (for n sufficiently large). Furthermore, at least 5 rounds are necessary when t/spl ges/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/spl ges/0.5n).