Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR94-011 | 12th December 1994 00:00

Fault Diagnosis in a Flash

RSS-Feed




TR94-011
Authors: R. Beigel, W. Hurwood, N. Kahale
Publication: 12th December 1994 00:00
Downloads: 1166
Keywords: 


Abstract:

We consider the fault diagnosis problem: how to use parallel testing
rounds to identify which processors in a set are faulty. We prove
that 4 rounds suffice when 3% or less of the processors are faulty,
and 4 rounds are necessary when any nontrivial constant fraction of
the processors are faulty. In addition we prove that 10 rounds
suffice when less than half of the processors are faulty, and 5 rounds
are necessary when at least 49% of the processors are faulty.



ISSN 1433-8092 | Imprint