Abstract
We prove that, for the black hole search problem, the pure token model is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove that a team of two asynchronous agents, each endowed with a single identical pebble (that can be placed only on nodes, and with no more than one pebble per node) can locate the black hole in an arbitrary network of known topology; this can be done with Θ(n logn) moves, where n is the number of nodes, even when the links are not FIFO.
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
Albers, S., Henzinger, M.: Exploring unknown environments. In: 29th ACM Symposium on Theory of Computing (STOC), pp. 416–425 (1997)
Bender, M.A., Fernández, A., Ron, D., Sahai, A., Vadhan, S.P.: The power of a pebble: Exploring and mapping directed graphs. Information and Computation 176(1), 1–21 (2002)
Cao, J., Das, S. (eds.): Mobile Agents in Networking and Distributed Computing. John Wiley, Chichester (2008)
Chalopin, J., Das, S., Santoro, N.: Rendezvous of mobile agents in unknown graphs with faulty links. In: Pelc, A. (ed.) DISC 2007. LNCS, vol. 4731, pp. 108–122. Springer, Heidelberg (2007)
Cooper, C., Klasing, R., Radzik, T.: Searching for black-hole faults in a network using multiple agents. In: Shvartsman, M.M.A.A. (ed.) OPODIS 2006. LNCS, vol. 4305, pp. 320–332. Springer, Heidelberg (2006)
Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A.: Complexity of searching for a black hole. Fundamenta Informaticae 71(2-3), 229–242 (2006)
Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A.: Searching for a black hole in synchronous tree networks. Combinatorics, Probability & Computing 16, 595–619 (2007)
Das, S., Flocchini, P., Kutten, S., Nayak, A., Santoro, N.: Map construction of unknown graphs by multiple agents. Theoretical Computer Science 385(1-3), 34–48 (2007)
Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. Graph Theory 32(3), 265–297 (1999)
Dobrev, S., Flocchini, P., Kralovic, R., Santoro, N.: Exploring a dangerous unknown graph using tokens. In: 5th IFIP Int. Conf. on Theoretical Computer Science (TCS), pp. 131–150 (2006)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Searching for a black hole in arbitrary networks: optimal mobile agents protocol. Distributed Computing 19(1), 1–19 (2006)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Mobile search for a black hole in an anonymous ring. Algorithmica 48, 67–90 (2007)
Dobrev, S., Kralovic, R., Santoro, N., Shi, W.: Black hole search in asynchronous rings using tokens. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol. 3998, pp. 139–150. Springer, Heidelberg (2006)
Flocchini, P., Ilcinkas, D., Santoro, N.: Optimal black hole search with pure tokens, http://www.scs.carleton.ca/-santoro/Reports/PingPong.pdf
Flocchini, P., Santoro, N.: Distributed Security Algorithms For Mobile Agents. In: 3, ch. 5 (2008)
Fraigniaud, P., Gasieniec, L., Kowalski, D., Pelc, A.: Collective tree exploration. Networks 48(3), 166–177 (2006)
Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theoretical Computer Science 345(2-3), 331–344 (2005)
Klasing, R., Markou, E., Radzik, T., Sarracco, F.: Approximation bounds for black hole search problems. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds.) OPODIS 2005. LNCS, vol. 3974, pp. 261–274. Springer, Heidelberg (2005)
Klasing, R., Markou, E., Radzik, T., Sarracco, F.: Hardness and approximation results for black hole search in arbitrary networks. Theoretical Computer Science 384(2-3), 201–221 (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Flocchini, P., Ilcinkas, D., Santoro, N. (2008). Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens. In: Taubenfeld, G. (eds) Distributed Computing. DISC 2008. Lecture Notes in Computer Science, vol 5218. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87779-0_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-87779-0_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87778-3
Online ISBN: 978-3-540-87779-0
eBook Packages: Computer ScienceComputer Science (R0)