Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-020 | 8th March 1995 00:00

Dynamic Fault Diagnosis

RSS-Feed




TR95-020
Authors: William Hurwood
Publication: 19th April 1995 16:03
Downloads: 3163
Keywords: 


Abstract:

We consider a dynamic fault diagnosis problem: There are n
processors, to be tested in a series of rounds. In every
testing round we use a directed matching to have some
processors report on the status (good or faulty) of other
processors. Also in each round up to t processors may
break down, and we may direct that up to t processors are
repaired. We show that it is possible to limit the number
of faulty processors to O(t log t), even if the system is
run indefinitely. We present an adversary which shows that
this bound is optimal.



ISSN 1433-8092 | Imprint