Abstract
We prove that, for the black hole search problem in networks of arbitrary but known topology, the pebble model of agent interaction 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 Θ(nlog n) moves, where n is the number of nodes, even when the links are not FIFO. These results are obtained with a novel algorithmic technique, **-pong, for agents using pebbles.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164–1188 (2000)
Bender, M.A., Fernández, A., Ron, D., Sahai, A., Vadhan, S.P.: The power of a pebble: Exploring and map** directed graphs. Inf. Comput. 176(1), 1–21 (2002)
Cao, J., Das, S. (eds.): Mobile Agents in Networking and Distributed Computing. Wiley, New York (2009)
Chalopin, J., Das, S., Santoro, N.: Rendezvous of mobile agents in unknown graphs with faulty links. In: 21st Conference on Distributed Computing (DISC), pp. 108–122 (2007)
Cooper, C., Klasing, R., Radzik, T.: Searching for black-hole faults in a network using multiple agents. In: 10th International Conference on Principles of Distributed Systems (OPODIS), pp. 320–332 (2006)
Czyzowicz, J., Dobrev, S., Královic, R., Miklík, S., Pardubská, D.: Black hole search in directed graphs. In: 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 182–194 (2009)
Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A.: Complexity of searching for a black hole. Fundam. Inform. 71(2–3), 229–242 (2006)
Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A.: Searching for a black hole in synchronous tree networks. Comb. Probab. Comput. 16, 595–619 (2007)
Das, S., Flocchini, P., Kutten, S., Nayak, A., Santoro, N.: Map construction of unknown graphs by multiple agents. Theor. Comput. Sci. 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 International Conference 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. Distrib. Comput. 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: 6th International Conference on Algorithms and Complexity (CIAC), pp. 139–150 (2006)
Flocchini, P., Ilcinkas, D., Santoro, N.: ** Pong in dangerous graphs: optimal black hole search with pure tokens. In: 22nd International Symposium on Distributed Computing (DISC). LNCS, vol. 5218, pp. 227–241 (2008)
Flocchini, P., Kellett, M., Mason, P., Santoro, N.: Map construction and exploration by mobile agents scattered in a dangerous network. In: 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1–10 (2009)
Flocchini, P., Santoro, N.: Distributed Security Algorithms for Mobile Agents. Chapter 5 of [3] (2009)
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. Theor. Comput. Sci. 345(2–3), 331–344 (2005)
Glaus, P.: Locating a black hole without the knowledge of incoming link. In: 5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS). LNCS, vol. 5804, pp. 128–138 (2009)
Klasing, R., Markou, E., Radzik, T., Sarracco, F.: Approximation bounds for black hole search problems. Networks 52(4), 216–226 (2008)
Klasing, R., Markou, E., Radzik, T., Sarracco, F.: Hardness and approximation results for black hole search in arbitrary networks. Theor. Comput. Sci. 384(2–3), 201–221 (2007)
Kosowski, A., Navarra, A., Pinotti, C.M.: Synchronization helps robots to detect black holes in directed graphs. In: 13th International Conference on Principles of Distributed Systems (OPODIS). LNCS, vol. 5923, pp. 86–98 (2009)
Královic, R., Miklík, S.: Periodic data retrieval problem in rings containing a malicious host. In: 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO). LNCS, vol. 6058, pp. 157–167 (2010)
Shi, W.: Black hole search with tokens in interconnected networks. In: The 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 670–682 (2009)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper appeared in the Proceedings of the 22nd International Symposium on Distributed Computing (DISC 2008) [15].
Rights and permissions
About this article
Cite this article
Flocchini, P., Ilcinkas, D. & Santoro, N. ** Pong in Dangerous Graphs: Optimal Black Hole Search with Pebbles. Algorithmica 62, 1006–1033 (2012). https://doi.org/10.1007/s00453-011-9496-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-011-9496-3