Ping pong in dangerous graphs: Optimal black hole search with pure tokens. (English) Zbl 1161.68335
Taubenfeld, Gadi (ed.), Distributed computing. 22nd international symposium, DISC 2008, Arcachon, France, September 22–24, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-87778-3/pbk). Lecture Notes in Computer Science 5218, 227-241 (2008).
Summary: 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 \(\Theta (n \log n)\) moves, where \(n\) is the number of nodes, even when the links are not FIFO.
For the entire collection see [Zbl 1148.68007].
For the entire collection see [Zbl 1148.68007].
MSC:
| 68M14 | Distributed systems |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
Keywords:
distributed computing; graph exploration; mobile agents; autonomous robots; dangerous graphsReferences:
| [1] | Albers, S., Henzinger, M.: Exploring unknown environments. In: 29th ACM Symposium on Theory of Computing (STOC), pp. 416-425 (1997) · Zbl 0968.68156 |
| [2] | 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) · Zbl 1012.68202 · doi:10.1006/inco.2001.3081 |
| [3] | Cao, J.; Das, S., Mobile Agents in Networking and Distributed Computing (2008), Chichester: John Wiley, Chichester |
| [4] | Chalopin, J.; Das, S.; Santoro, N.; Pelc, A., Rendezvous of mobile agents in unknown graphs with faulty links, Distributed Computing, 108-122 (2007), Heidelberg: Springer, Heidelberg · Zbl 1145.68347 · doi:10.1007/978-3-540-75142-7_11 |
| [5] | Cooper, C.; Klasing, R.; Radzik, T.; Shvartsman, M. M.A. A., Searching for black-hole faults in a network using multiple agents, Principles of Distributed Systems, 320-332 (2006), Heidelberg: Springer, Heidelberg · doi:10.1007/11945529_23 |
| [6] | Czyzowicz, J.; Kowalski, D.; Markou, E.; Pelc, A., Complexity of searching for a black hole, Fundamenta Informaticae, 71, 2-3, 229-242 (2006) · Zbl 1095.68078 |
| [7] | Czyzowicz, J.; Kowalski, D.; Markou, E.; Pelc, A., Searching for a black hole in synchronous tree networks, Combinatorics, Probability & Computing, 16, 595-619 (2007) · Zbl 1130.68029 · doi:10.1017/S0963548306008133 |
| [8] | 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) · Zbl 1124.68078 · doi:10.1016/j.tcs.2007.05.011 |
| [9] | Deng, X.; Papadimitriou, C. H., Exploring an unknown graph, J. Graph Theory, 32, 3, 265-297 (1999) · Zbl 0941.68099 · doi:10.1002/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8 |
| [10] | 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) · Zbl 1259.68159 |
| [11] | 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) · Zbl 1266.68208 · doi:10.1007/s00446-006-0154-y |
| [12] | Dobrev, S.; Flocchini, P.; Prencipe, G.; Santoro, N., Mobile search for a black hole in an anonymous ring, Algorithmica, 48, 67-90 (2007) · Zbl 1123.68018 · doi:10.1007/s00453-006-1232-z |
| [13] | Dobrev, S.; Kralovic, R.; Santoro, N.; Shi, W.; Calamoneri, T.; Finocchi, I.; Italiano, G. F., Black hole search in asynchronous rings using tokens, Algorithms and Complexity, 139-150 (2006), Heidelberg: Springer, Heidelberg · Zbl 1183.68035 · doi:10.1007/11758471_16 |
| [14] | Flocchini, P., Ilcinkas, D., Santoro, N.: Optimal black hole search with pure tokens, http://www.scs.carleton.ca/-santoro/Reports/PingPong.pdf · Zbl 1161.68335 |
| [15] | Flocchini, P., Santoro, N.: Distributed Security Algorithms For Mobile Agents. In: 3, ch. 5 (2008) |
| [16] | Fraigniaud, P.; Gasieniec, L.; Kowalski, D.; Pelc, A., Collective tree exploration, Networks, 48, 3, 166-177 (2006) · Zbl 1107.68065 · doi:10.1002/net.20127 |
| [17] | 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) · Zbl 1081.68045 · doi:10.1016/j.tcs.2005.07.014 |
| [18] | Klasing, R.; Markou, E.; Radzik, T.; Sarracco, F.; Anderson, J. H.; Prencipe, G.; Wattenhofer, R., Approximation bounds for black hole search problems, Principles of Distributed Systems, 261-274 (2005), Heidelberg: Springer, Heidelberg · doi:10.1007/11795490_21 |
| [19] | 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) · Zbl 1125.68139 · doi:10.1016/j.tcs.2007.04.024 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
