Abstract
We consider a fixed, undirected, known network and a number of "mobile agents" which can traverse the network in synchronised steps. Some nodes in the network may be faulty and the agents are to find the faults and repair them. The agents could be software agents, if the underlying network represents a computer network, or robots, if the underlying network represents some potentially hazardous physical terrain. Assuming that the first agent encountering a faulty node can immediately repair it, it is easy to see that the number of steps necessary and sufficient to complete this task is Theta(n/k + D), where n is the number of nodes in the network, D is the diameter of the network, and k is the number of agents. We consider the case where one agent can repair only one faulty node. After repairing the fault, the agent dies. We show that a simple deterministic algorithm for this problem terminates within O(n/k + D log f/log log f) steps, where f = min{n/k, n/D}, assuming that the number of faulty nodes is at most k/2. We also demonstrate the worst-case asymptotic optimality of this algorithm by showing a network such that for any deterministic algorithm, there is a placement of k/2 faults forcing the algorithm to work for Omega(n/k + D logf/log logf) steps. (C) 2010 Elsevier B.V. All rights reserved.
| Original language | English |
|---|---|
| Pages (from-to) | 1638 - 1647 |
| Number of pages | 10 |
| Journal | Theoretical Computer Science |
| Volume | 411 |
| Issue number | 14-15 |
| DOIs | |
| Publication status | Published - 17 Mar 2010 |