Abstract
A black hole is a highly harmful host that disposes of visiting agents upon their arrival. It is known that it is possible for a team of mobile agents to locate a black hole in an asynchronous ring network if each node is equipped with a whiteboard of at least O(log n) dedicated bits of storage. In this paper, we consider the less powerful token model: each agent has has available a bounded number of tokens that can be carried, placed on a node or removed from it. All tokens are identical (i.e., indistinguishable) and no other form of communication or coordination is available to the agents. We first of all prove that a team of two agents is sufficient to locate the black hole in finite time even in this weaker coordination model. Furthermore, we prove that this can be accomplished using only O(n log n) moves in total, which is optimal, the same as with whiteboards. Finally, we show that to achieve this result the agents need to use only O(1) tokens each.
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
Barriere, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Election and rendezvous in fully anonymous systems with sense of direction. Theory of Computing Systems (to appear, 2006); Preliminary version in Proc. of SIROCCO 2003
Chess, D.M.: Security issues in mobile code systems. In: Vigna, G. (ed.) Mobile Agents and Security. LNCS, vol. 1419, pp. 1–14. Springer, Heidelberg (1998)
Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A.: Searching for a black hole in tree networks. In: Higashino, T. (ed.) OPODIS 2004. LNCS, vol. 3544, pp. 67–80. Springer, Heidelberg (2005)
Dobrev, S., Flocchini, P., Kralovic, R., Prencipe, G., Ruzicka, P., Santoro, N.: Optimal search for a black hole in common interconnection networks. Networks (to appear, 2006); Preliminary version in Proc. of OPODIS 2002
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Mobile search for a black hole in an anonymous ring. Algorithmica (to appear, 2006); Preliminary version in Proc. of DISC 2001
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Searching for a black hole in a arbitrary networks: optimal mobile agent protocols. Distributed Computing (to appear, 2006); Preliminary version in Proc. of PODC 2002
Dobrev, S., Flocchini, P., Santoro, N.: Improved bounds for optimal black hole search in a network with a map. In: Proc. of 10th International Colloquium on Structural Information and Communication Complexity, pp. 111–122 (2004)
Fraigniaud, P., Gasieniec, L., Kowalski, D., Pelc, A.: Collective tree exploration. In: 6th Latin American Theoretical Informatics Symp., pp. 141–151 (2004)
Fraigniaud, P., Ilcinkas, D.: Digraph exploration with little memory. In: 21st Symp. on Theoretical Aspects of Computer Science, pp. 246–257 (2004)
Greenberg, M.S., Byington, J.C., Harper, D.G.: Mobile agents and security. IEEE Commun. Mag. 36(7), 76–85 (1998)
Hohl, F.: A model of attacks of malicious hosts against mobile agents. In: Proc. of the ECOOP Workshop on Distributed Object Security and 4th Workshop on Mobile Object Systems. LNCS, vol. 1603, pp. 105–120. Springer, Heidelberg (1998)
Klasing, R., Markou, E., Radzik, T., Sarracco, F.: Hardness and approximation results for black hole search in arbitrary graphs. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol. 3499, pp. 200–215. Springer, Heidelberg (2005)
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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dobrev, S., Královič, R., Santoro, N., Shi, W. (2006). Black Hole Search in Asynchronous Rings Using Tokens. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds) Algorithms and Complexity. CIAC 2006. Lecture Notes in Computer Science, vol 3998. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758471_16
Download citation
DOI: https://doi.org/10.1007/11758471_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34375-2
Online ISBN: 978-3-540-34378-3
eBook Packages: Computer ScienceComputer Science (R0)