Back to Search
Start Over
Searching for a black hole in arbitrary networks: optimal mobile agents protocols.
- Source :
-
Distributed Computing . Sep2006, Vol. 19 Issue 1, p1-18. 18p. 9 Diagrams, 1 Chart. - Publication Year :
- 2006
-
Abstract
- Consider a networked environment, supporting mobile agents, where there is a black hole: a harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The black hole search problem is the one of assembling a team of asynchronous mobile agents, executing the same protocol and communicating by means of whiteboards, to successfully identify the location of the black hole; we are concerned with solutions that are generic (i.e., topology-independent). We establish tight bounds on the size of the team (i.e., the number of agents), and the cost (i.e., the number of moves) of a size-optimal solution protocol. These bounds depend on the a priori knowledge the agents have about the network, and on the consistency of the local labelings. In particular, we prove that: with topological ignorance Δ+1 agents are needed and suffice, and the cost is Θ( n 2), where Δ is the maximal degree of a node and n is the number of nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is Θ( n 2); and with complete topological knowledge only two agents suffice and the cost is Θ( n log n). All the upper-bound proofs are constructive. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01782770
- Volume :
- 19
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Distributed Computing
- Publication Type :
- Academic Journal
- Accession number :
- 22081846
- Full Text :
- https://doi.org/10.1007/s00446-006-0154-y