Abstract
A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous tree network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable to identify a black hole is two. For a given tree and given starting node we are interested in the fastest possible black hole search by two agents. For arbitrary trees we give a 5/3-approximation algorithm for this problem. We give optimal black hole search algorithms for two “extreme” classes of trees: the class of lines and the class of trees in which any internal node (including the root which is the starting node) has at least 2 children.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Dobrev, S., Flocchini, P., Kralovic, R., Prencipe, G., Ruzicka, P., Santoro, N.: Black hole search by mobile agents in hypercubes and related networks. In: Proc. of Symposium on Principles of Distributed Systems (OPODIS 2002), pp. 171–182 (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 Agents Protocols. In: Proc. 21st ACM Symposium on Principles of Distributed Computing (PODC 2002), pp. 153–161 (2002)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Multiple agents rendezvous on a ring in spite of a black hole. In: Proc. Symposium on Principles of Distributed Systems, OPODIS 2003 (2003)
Hohl, F.: Time limited black box security: Protecting mobile agents from malicious hosts. In: Vigna, G. (ed.) Mobile Agents and Security. LNCS, vol. 1419, pp. 92–113. Springer, Heidelberg (1998)
Hohl, F.: A framework to protect mobile agents by using reference states. In: Proc. 20th Int. Conf. on Distributed Computing Systems (ICDCS 2000), pp. 410–417 (2000)
Ng, S., Cheung, K.: Protecting mobile agents against malicious hosts by intention of spreading. In: Proc. Int. Conf. on Parallel and Distributed Processing and Applications (PDPTA 1999), pp. 725–729 (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)
Schelderup, K., Ines, J.: Mobile agent security – issues and directions. In: Zuidweg, H., Campolargo, M., Delgado, J., Mullery, A. (eds.) IS&N 1999. LNCS, vol. 1597, pp. 155–167. Springer, Heidelberg (1999)
Vitek, J., Castagna, G.: Mobile computations and hostile hosts. In: Tsichritzis, D. (ed.) Mobile Objects, University of Geneva, pp. 241–261 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A. (2005). Searching for a Black Hole in Tree Networks. In: Higashino, T. (eds) Principles of Distributed Systems. OPODIS 2004. Lecture Notes in Computer Science, vol 3544. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11516798_5
Download citation
DOI: https://doi.org/10.1007/11516798_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-27324-0
Online ISBN: 978-3-540-31584-1
eBook Packages: Computer ScienceComputer Science (R0)