Abstract
A black hole is a harmful host that destroys incoming agents without leaving any observable trace of such a destruction. The black hole search problem is to unambiguously determine the location of the black hole. A team of agents, provided with a network map and executing the same protocol, solves the problem if at least one agent survives and, within finite time, knows the location of the black hole.
It is known that a team must have at least two agents. Interestingly, two agents with a map of the network can locate the black hole with O(n) moves in many highly regular networks; however the protocols used apply only to a narrow class of networks. On the other hand, any universal solution protocol must use Ω(n log n) moves in the worst case, regardless of the size of the team.
A universal solution protocol has been recently presented that uses a team of just two agents with a map of the network, and locates a black hole in at most O(n log n) moves. Thus, this protocol has both optimal size and worst-case-optimal cost. We show that this result, far from closing the research quest, can be significantly improved.
In this paper we present a universal protocol that allows a team of two agents with a network map to locate the black hole using at most O(n + d log d) moves, where d is the diameter of the network. This means that, without losing its universality and without violating the worst-case Ω(n log n) lower bound, this algorithm allows two agents to locate a black hole with Θ(n) cost in a very large class of (possibly unstructured) networks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alpern, S.: The Rendezvous search problem. SIAM J. of Control and Optimization 33, 673–683 (1995)
Arkin, E., Bender, M., Fekete, S., Mitchell, J.: The freeze-tag problem: how to wake up a swarm of robots. In: 13th ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pp. 568–577 (2002)
Awerbuch, B., Betke, M., Singh, M.: Piecemeal graph learning by a mobile robot. Information and Computation 152, 155–172 (1999)
L. Barriére, P. Flocchini, P. Fraigniaud, and N. Santoro. Capture of an intruder by mobile agents. In 14th ACM-SIAM Symp. on Parallel Algorithms and Architectures (SPAA ’02), 200-209, 2002.
Barriére, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Election and rendezvous in fully anonymous systems with sense of direction. In: 10th Colloquium on Structural Information and Communication complexity (SIROCCO 2003), pp. 17–32 (2003)
Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. of Graph Theory 32, 265–297 (1999)
Dessmark, A., Fraigniaud, P., Pelc, A.: Deterministic rendezvous in graphs. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 184–195. Springer, Heidelberg (2003)
Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. In: 13th ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pp. 588–597 (2002)
Dobrev, S., Flocchini, P., Král’ovič, R., Prencipe, G., Ružička, P., Santoro, N.: Optimal search for a black hole in common interconnection networks. In: Proc. of Symposium on Principles of Distributed Systems, OPODIS 2002 (2002)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Mobile agents searching for a black hole in an anonymous ring. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol. 2180, pp. 166–179. Springer, Heidelberg (2001)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Searching for a black hole in arbitrary networks: Optimal mobile agent protocols. In: Proc. of 21st ACM Symposium on Principles of Distributed Computing (PODC 2002), pp. 153–162 (2002)
Hohl, F.: A Model of attacks of malicious hosts against mobile agents. In: Secure Internet Programming. LNCS, vol. 1603, pp. 105–120 (1998)
Kranakis, E., Krizanc, D., Santoro, N., Sawchuk, C.: Mobile agent rendezvous in a ring. In: 23rd International Conference on Distributed Computing Systems, ICDCS 2003 (2003)
Oppliger, R.: Security issues related to mobile code and agent-based systems. Computer Communications 22(12), 1165–1170 (1999)
Sander, T., Tschudin, C.F.: Protecting mobile agents against malicious hosts. In: Vigna, G. (ed.) Mobile Agents and Security. LNCS, vol. 1419, pp. 44–60. Springer, Heidelberg (1998)
Vitek, J., Castagna, G.: Mobile computations and hostile hosts. In: Tsichritzis, D. (ed.) Mobile Objects, pp. 241–261. University of Geneva (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dobrev, S., Flocchini, P., Santoro, N. (2004). Improved Bounds for Optimal Black Hole Search with a Network Map. In: Královic̆, R., Sýkora, O. (eds) Structural Information and Communication Complexity. SIROCCO 2004. Lecture Notes in Computer Science, vol 3104. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27796-5_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-27796-5_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22230-9
Online ISBN: 978-3-540-27796-5
eBook Packages: Springer Book Archive