{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T06:50:25Z","timestamp":1768978225393,"version":"3.49.0"},"reference-count":29,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2023,4,26]],"date-time":"2023-04-26T00:00:00Z","timestamp":1682467200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Natural Science and Engineering Research Council (Canada)"},{"name":"Italian National Group for Scientific Computation GNCS-INdAM"},{"name":"Progetto PRA_2022_81 (Universit\u00e0 di Pisa, Italy)"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Consider a set of k identical asynchronous mobile agents located in an anonymous ring of n nodes. The classical Gather (or Rendezvous) problem requires all agents to meet at the same node, not a priori decided, within a finite amount of time. This problem has been studied assuming that the network is safe for the agents. In this paper, we consider the presence in the ring of a stationary process located at a node that disables any incoming agent without leaving any trace. Such a dangerous node is known in the literature as a black hole, and the determination of its location has been extensively investigated. The presence of the black hole makes it deterministically unfeasible for all agents to gather. So, the research concern is to determine how many agents can gather and under what conditions. In this paper we establish a complete characterization of the conditions under which the problem can be solved. In particular, we determine the maximum number of agents that can be guaranteed to gather in the same location depending on whether k or n is unknown (at least one must be known). These results are tight: in each case, gathering with one more agent is deterministically unfeasible. All our possibility proofs are constructive: we provide mobile agent algorithms that allow the agents to gather within a predefined distance under the specified conditions. The analysis of the time costs of these algorithms show that they are optimal. Our gathering algorithm for the case of unknown k is also a solution for the black hole location problem. Interestingly, its bounded time complexity is \u0398(n); this is a significant improvement over the existing O(nlogn) bounded time complexity.<\/jats:p>","DOI":"10.3390\/a16050222","type":"journal-article","created":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T01:28:28Z","timestamp":1682558908000},"page":"222","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Asynchronous Gathering in a Dangerous Ring"],"prefix":"10.3390","volume":"16","author":[{"given":"Stefan","family":"Dobrev","sequence":"first","affiliation":[{"name":"Informatics Department, Slovak Academy of Science, 841 04 Bratislava, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3584-5727","authenticated-orcid":false,"given":"Paola","family":"Flocchini","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, ON K1N 6N5, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5646-7388","authenticated-orcid":false,"given":"Giuseppe","family":"Prencipe","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 di Pisa, 56127 Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7954-3918","authenticated-orcid":false,"given":"Nicola","family":"Santoro","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, Ottawa, ON K1S 5B6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,4,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Cao, J., and Das, S. (2012). Mobile Agents in Networking and Distributed Computing, Wiley.","DOI":"10.1002\/9781118135617"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Prencipe, G., and Santoro, N. (2019). Distributed Computing by Mobile Entities, Springer.","DOI":"10.1007\/978-3-030-11072-7"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jpdc.2015.10.006","article-title":"Black hole search in computer networks: State-of-the-art, challenges and future directions","volume":"88","author":"Peng","year":"2016","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Prencipe, G., and Santoro, N. (2019). Distributed Computing by Mobile Entities, Springer. Chapter 17.","DOI":"10.1007\/978-3-030-11072-7"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s00224-005-1223-5","article-title":"Rendezvous and election of mobile agents: Impact of sense of direction","volume":"40","author":"Flocchini","year":"2007","journal-title":"Theory Comput. Syst."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/j.tcs.2018.06.045","article-title":"On asynchronous rendezvous in general graphs","volume":"753","author":"Bampas","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"37:1","DOI":"10.1145\/2344422.2344427","article-title":"How to meet asynchronously (almost) everywhere","volume":"8","author":"Czyzowicz","year":"2012","journal-title":"Acm. Trans. Algorithms"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1137\/130931990","article-title":"How to meet asynchronously at polynomial cost","volume":"44","author":"Pelc","year":"2015","journal-title":"Siam J. Comput."},{"key":"ref_9","first-page":"160","article-title":"Mobile agent security against malicious hosts: A survey","volume":"3","author":"Chattopadhyay","year":"2022","journal-title":"Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Vigna, G. (1998). Mobile Agent Security, Springer.","DOI":"10.1007\/3-540-68671-1"},{"key":"ref_11","unstructured":"Tsichritzis, D. (1999). Mobile Objects, University of Geneva."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Cao, J., and Das, S. (2012). Mobile Agents in Networking and Distributed Computing, Wiley. Chapter 3.","DOI":"10.1002\/9781118135617"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/s00453-006-1232-z","article-title":"Mobile search for a black hole in an anonymous ring","volume":"48","author":"Dobrev","year":"2007","journal-title":"Algorithmica"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Chalopin, J., Das, S., Labourel, A., and Markou, E. (2011, January 20\u201322). Black hole search with finite automata scattered in a synchronous torus. Proceedings of the 25th International Symposium on Distributed Computing, Rome, Italy.","DOI":"10.1007\/978-3-642-24100-0_41"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/j.tcs.2013.02.010","article-title":"Tight bounds for Black Hole Search with scattered agents in a synchronous ring","volume":"509","author":"Chalopin","year":"2013","journal-title":"Theor. Comput. Sci."},{"key":"ref_16","first-page":"229","article-title":"Complexity of searching for a Black Hole","volume":"71","author":"Czyzowicz","year":"2006","journal-title":"Fundam. Inform."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/j.tcs.2015.09.002","article-title":"Explore and repair graphs with black holes using mobile entities","volume":"605","author":"Frigioni","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/net.20095","article-title":"Optimal search for a black hole in common interconnection networks","volume":"47","author":"Dobrev","year":"2006","journal-title":"Networks"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.tcs.2012.11.022","article-title":"Exploring an unknown dangerous graph using tokens","volume":"472","author":"Dobrev","year":"2013","journal-title":"Theor. Comput. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00446-006-0154-y","article-title":"Searching for a black hole in arbitrary networks: Optimal mobile agents protocols","volume":"19","author":"Dobrev","year":"2006","journal-title":"Distrib. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Kellett, M., Mason, P., and Santoro, N. (2009, January 23\u201329). Map construction and exploration by mobile agents scattered in a dangerous network. Proceedings of the 28th IEEE International Parallel and Distributed Processing Symposium, Rome, Italy.","DOI":"10.1109\/IPDPS.2009.5161080"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Kellett, M., Mason, P., and Santoro, N. (2012, January 1\u20134). Fault-tolerant exploration of an unknown dangerous graph by scattered agents. Proceedings of the 14th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Toronto, ON, Canada.","DOI":"10.1007\/978-3-642-33536-5_30"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1002\/net.20233","article-title":"Approximation bounds for Black Hole Search problems","volume":"52","author":"Klasing","year":"2008","journal-title":"Networks"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"5752","DOI":"10.1016\/j.tcs.2011.05.054","article-title":"Synchronous black hole search in directed graphs","volume":"412","author":"Kosowski","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Markou, E., and Paquette, M. (2012, January 18\u201320). Black hole search and exploration in unoriented tori with synchronous scattered finite automata. Proceedings of the 14th International Conference on Principles of Distributed Systems, Rome, Italy.","DOI":"10.1007\/978-3-642-35476-2_17"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Prencipe, G., and Santoro, N. (2019). Distributed Computing by Mobile Entities, Springer. Chapter 18.","DOI":"10.1007\/978-3-030-11072-7"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S1793830911001346","article-title":"Time optimal algorithms for black hole search in rings","volume":"3","author":"Balamohan","year":"2011","journal-title":"Discret. Math. Algorithms Appl."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1355","DOI":"10.1142\/S0129054108006327","article-title":"Using scattered mobile agents to locate a black hole in a unoriented ring with tokens","volume":"19","author":"Dobrev","year":"2008","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_29","unstructured":"Dobrev, S., Flocchini, P., Prencipe, G., and Santoro, N. (2003, January 10\u201313). Multiple agents rendezvous in a ring in spite of a black hole. Proceedings of the 7th International Conference on Principles of Distributed Systems, La Martinique, France."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/5\/222\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:23:37Z","timestamp":1760124217000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/5\/222"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,26]]},"references-count":29,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2023,5]]}},"alternative-id":["a16050222"],"URL":"https:\/\/doi.org\/10.3390\/a16050222","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,26]]}}}