Asynchronous Gathering in a Dangerous Ring
Consider a set of <i>k</i> identical asynchronous mobile agents located in an anonymous ring of <i>n</i> nodes. The classical <span style="font-variant: small-caps;">Gather</span> (or <span style="font-variant: small-caps;">Rendezvous<...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-04-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/16/5/222 |
| _version_ | 1797601388365086720 |
|---|---|
| author | Stefan Dobrev Paola Flocchini Giuseppe Prencipe Nicola Santoro |
| author_facet | Stefan Dobrev Paola Flocchini Giuseppe Prencipe Nicola Santoro |
| author_sort | Stefan Dobrev |
| collection | DOAJ |
| description | Consider a set of <i>k</i> identical asynchronous mobile agents located in an anonymous ring of <i>n</i> nodes. The classical <span style="font-variant: small-caps;">Gather</span> (or <span style="font-variant: small-caps;">Rendezvous</span>) 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 <i>k</i> or <i>n</i> 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 <i>k</i> is also a solution for the black hole location problem. Interestingly, its bounded time complexity is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>Θ</mo><mo>(</mo><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula>; this is a significant improvement over the existing <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo form="prefix">log</mo><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula> bounded time complexity. |
| first_indexed | 2024-03-11T04:00:20Z |
| format | Article |
| id | doaj.art-1f9b9ffcef644b958169b16425a20ef3 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-11T04:00:20Z |
| publishDate | 2023-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-1f9b9ffcef644b958169b16425a20ef32023-11-18T00:08:24ZengMDPI AGAlgorithms1999-48932023-04-0116522210.3390/a16050222Asynchronous Gathering in a Dangerous RingStefan Dobrev0Paola Flocchini1Giuseppe Prencipe2Nicola Santoro3Informatics Department, Slovak Academy of Science, 841 04 Bratislava, SlovakiaSchool of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, ON K1N 6N5, CanadaDipartimento di Informatica, Università di Pisa, 56127 Pisa, ItalySchool of Computer Science, Carleton University, Ottawa, ON K1S 5B6, CanadaConsider a set of <i>k</i> identical asynchronous mobile agents located in an anonymous ring of <i>n</i> nodes. The classical <span style="font-variant: small-caps;">Gather</span> (or <span style="font-variant: small-caps;">Rendezvous</span>) 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 <i>k</i> or <i>n</i> 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 <i>k</i> is also a solution for the black hole location problem. Interestingly, its bounded time complexity is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>Θ</mo><mo>(</mo><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula>; this is a significant improvement over the existing <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo form="prefix">log</mo><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula> bounded time complexity.https://www.mdpi.com/1999-4893/16/5/222mobile agentsrendezvousgatheringblack holeharmful hostring network |
| spellingShingle | Stefan Dobrev Paola Flocchini Giuseppe Prencipe Nicola Santoro Asynchronous Gathering in a Dangerous Ring Algorithms mobile agents rendezvous gathering black hole harmful host ring network |
| title | Asynchronous Gathering in a Dangerous Ring |
| title_full | Asynchronous Gathering in a Dangerous Ring |
| title_fullStr | Asynchronous Gathering in a Dangerous Ring |
| title_full_unstemmed | Asynchronous Gathering in a Dangerous Ring |
| title_short | Asynchronous Gathering in a Dangerous Ring |
| title_sort | asynchronous gathering in a dangerous ring |
| topic | mobile agents rendezvous gathering black hole harmful host ring network |
| url | https://www.mdpi.com/1999-4893/16/5/222 |
| work_keys_str_mv | AT stefandobrev asynchronousgatheringinadangerousring AT paolaflocchini asynchronousgatheringinadangerousring AT giuseppeprencipe asynchronousgatheringinadangerousring AT nicolasantoro asynchronousgatheringinadangerousring |