Ongoing fault diagnosis

摘要

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 log2 t), even if the system is run indefinitely. We present an adversary which shows that this bound is optimal.