# Asynchronous Gathering in a Dangerous Ring +
## 1 Introduction
### Contributions  
In this paper, we consider the _gathering_ problem in the following setting: \(k\) asynchronous anonymous agents dispersed in a totally symmetric ring network of \(n\) anonymous sites, one of which is a _black hole_. The presence of the black hole makes it deterministically unfeasible for all agents to gather. So, our research goal is to determine how many agents can gather and under what conditions.  
More precisely, we study the _gathering_ problem \(RV(f(k))\), which requires at least \(f(k)\leq k\) agents to gather and enter a terminal state in the same node, where \(f\) is an arbitrary monotonically non-decreasing function. We also investigate the related _close-gathering_ problem \(G(f(k),d)\), requiring at least \(f(k)\) agents to enter a terminal state located within a distance \(d\) from each other. Clearly, \(G(f(k),0)=RV(f(k))\).  
We establish a complete characterization of the conditions under which the two problems can be solved (proving the theoretical results previously claimed in [29]). 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). 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 possibility results are summarized in the table shown in Table 1. These results are _tight_: in each case, gathering with one more agent is impossible. The analysis of the time costs of these algorithms shows that they are _optimal_.  
Some of these results are unexpected. For example, in an oriented ring, all but one agents can indeed gather, even if the ring size \(n\) is not known, a condition that makes black hole location deterministically unfeasible [13].  
In an unoriented ring, at most \(k-2\) agents can gather; surprisingly, if they cannot, there is no guarantee that more that \((k-2)/2\) will. It is, however, always possible to bring all \(k-2\) agents within a distance of \(1\) from each other.  
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 \(\Theta(n)\); this is a significant improvement over the \(O(n\log n)\) bounded time complexity, shown in [13], of the existing algorithms for the same case.  
The paper is organised as follows: in Section 2, definitions and preliminary results are introduced; also, we present a few bounds for the problem. In Sections 3 and 4 we present algorithms that solve the problem, distinguishing two cases: \(k\) known and \(n\) unknown,  
\begin{table}
\begin{tabular}{c c c c} \hline \hline  & \(n\) Unknown, \(k\) Known & \(n\) Known, \(k\) Unknown \\ \hline ORIENTED & \(RV(k-1)\) & \(RV(k-2)\) \\ \hline  & \(k\) odd & \(RV(k-2)\) & \(k\) odd or \(n\) even & \(RV(k-2)\) \\ UNORIENTED & \(k\) even & \(RV((k-2)/2)\) & \(k\) even and \(n\) odd & \(RV((k-2)/2)\) \\  & \(\forall k\) & \(G(k-2,1)\) & \(\forall k\) & \(G(k-2,1)\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Summary of possibility results.  
and \(k\) unknown and \(n\) known; in both cases, results are presented for both oriented and unoriented rings. Finally, we draw some final conclusions in Section 5.