# Asynchronous Gathering in a Dangerous Ring +
## 2 Definitions, Basic Properties, and Techniques
### Basic Results and Lower Bounds
In this case, however, the adversary can make the algorithm fail for \(k>3\) by having all tails experiencing the same delays as \(t_{1}\), and delaying all heads \(\Delta_{1}\) time units. In this way, all tails enter the terminal state after \(\Delta_{1}\) time, making \(RV(k-1)\) impossible, a contradiction. **Case 2:**\(t_{1}\) reaches other nodes besides \(x_{1}\) and \(y_{1}\) before becoming _arrived_. Since it cannot move to the right of \(x_{1}\), these nodes are on the left of \(y_{1}\). Let \(w\) be the node immediately to the left of \(y_{1}\), and let \(t_{1}\) reach it for the first time \(\Delta_{2}\) time units after reaching \(x_{1}\) the first time. Note that this can happen even if \(h_{1}\) has not entered the black hole, e.g., if the adversary has made the delay of its initial movement, and return to \(x_{1}\), at least \(\Delta_{2}\). In this case, however, the adversary can make the algorithm fail for \(k>3\) as follows. The adversary places the black hole between two groups, e.g., \((h_{i},t_{i})\) and \((h_{i+1},t_{i+1})\) (refer to Figure 1), that have one empty node between them (recall that they exist by construction whenever \(k>3\)). Again, by having all tails experiencing the same delays as \(t_{1}\), and delaying all heads (except \(h_{i}\)) by \(\Delta_{2}\) time units, we have that not only \(h_{i}\), but also \(t_{i+1}\) enter the black hole within a finite amount of time, making \(RV(k-1)\) unachievable, a contradiction. It is known that knowledge of \(n\) is necessary to locate the black hole [13]. On the other hand, even without such knowledge, the gathering problem \(RV(f(k))\) is _trivially_ solvable if \(f(k)\leq\lfloor k/2\rfloor\):  
**Lemma 1**. : _Even if neither \(k\) nor \(n\) are known, \(RV(f(k))\) is solvable if \(f(k)\leq\lfloor k/2\rfloor\)._  
Figure 1: Example used in the proof of Theorem 2. Proof. : The algorithm that lets any robot choose a direction and move for as long as possible in that direction, trivially solves the problem. Now, we are ready to state the following:  
**Theorem 3**. : _If neither \(k\) nor \(n\) are known, \(RV(f(k))\) is unsolvable for \(f(k)>\lfloor k/2\rfloor\)._  
Proof. : By contradiction, let \(\mathcal{A}\) be a deterministic algorithm that solves \(RV(f(k))\) for \(f(k)>\lfloor k/2\rfloor\) for every \(k<n\), without knowledge of \(k\) and \(n\). For any non-constant monotonically non-decreasing function \(f\), there exists a \(\overline{k}\) such that \(f(\overline{k})<f(2\overline{k})\): let us consider an execution \(\mathcal{E}\) of \(\mathcal{A}\) on a ring \(\mathcal{R}\) of size \(n>\overline{k}\), with \(\overline{k}\) agents. By hypothesis, the execution of \(\mathcal{A}\) terminates with at least \(f(\overline{k})\) agents gathered on the same node of \(\mathcal{R}\), entering the terminal state. Now, let us build a new ring \(\overline{\mathcal{R}}\), having size \(2n-1\) and \(2\overline{k}\) agents, composed of two copies (including the initial location of the agents) of \(\mathcal{R}\), connected as depicted in Figure 2.  
Consider now the execution \(\mathcal{E}\) of \(\mathcal{A}\) on \(\overline{\mathcal{R}}\). The agents of \(\mathcal{R}^{\prime}\) will behave independently and exactly as the execution by the agents in \(\mathcal{R}\). Thus, within a finite amount of time, two distinct gathering points of size \(f(\overline{k})\) will be achieved. Since \(f(\overline{k})<f(2\overline{k})\), we have a contradiction. Finally, let us state a general lower bound on the number of moves. **Theorem 4**. : _Let \(n\) be known, and the ring be unoriented. The \(RV(k)\) problem requires at least \(\lfloor\frac{k}{2}\rfloor(n-\frac{k}{2}-2)\) moves._  
Proof. : Consider the situation when the agents are divided in two groups \(a_{1},\ldots a_{\lfloor\frac{k}{2}\rfloor}\) and \(a_{-1},\ldots a_{\lfloor\frac{k}{2}\rfloor}\) adjacent to the black hole. Let \(x\) be an arbitrary gathering point inside the segment between the two groups at distance \(d\) from \(a_{1}\).