Paper Info
Title
Locating and repairing faults in a network with mobile agents
Abstract
We consider a fixed, undirected, known network and a number of “mobile agents” which can traverse the network in synchronized 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 Θ(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 + Dlogf/loglogf) 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 Ω(n/k + Dlogf/loglogf) steps.
Year
DOI
Venue
2010
10.1016/j.tcs.2010.01.011
Theoretical Computer Science
Keywords
Field
DocType
problem terminates,software agent,underlying network,hazardous physical terrain,deterministic algorithm,faulty node,mobile agent,simple deterministic algorithm,computer network,Distributed computing,Mobile agents,Graph exploration,known network
Computer science,Terrain,Software agent,Deterministic algorithm,Robot,Distributed computing,Traverse
Journal
Volume
Issue
ISSN
411
14-15
Theoretical Computer Science
Citations 
PageRank 
References 
18
0.67
22
Authors
3
Name
Order
Citations
PageRank
Colin Cooper185791.88
Ralf Klasing286654.83
Tomasz Radzik3109895.68