# Asynchronous Gathering in a Dangerous Ring +
## 2 Definitions, Basic Properties, and Techniques
### Basic Results and Lower Bounds  
There are some basic obvious facts:  
**Theorem 1**. : _In an anonymous ring with a black hole:_  
1. \(RV(k)\) _is unsolvable;_
2. _If the ring is unoriented, then_ \(RV(k-1)\) _is unsolvable._  
Proof. : We distinguish the two cases. (1) It suffices for the adversary to choose as the location of the black hole the node where the first moving agent goes to: it disappears in the black hole, hence it will never be able to gather. (2) By contradiction, let \(\mathcal{A}\) be a deterministic solution algorithm, let the ring be unoriented, and let \(a_{i}\) be the first moving agent. Let us assume, without loss of generality, that \(a_{i}\) (according to the algorithm) moves to its left. The adversary chooses as the location of the black hole the node to the left of \(a_{i}\). Then, it places another agent \(a_{j}\) to the immediate left of the black hole, and assigns to \(a_{j}\) a sense of orientation opposite to the one of \(a_{i}\). Moreover, the adversary does not activate any other agents until both \(a_{i}\) and \(a_{j}\) make their move. This implies that, since \(\mathcal{A}\) is deterministic, \(a_{j}\) will choose right as its moving direction. Therefore, both \(a_{i}\) and \(a_{j}\) will eventually disappear into the black hole, a contradiction. Less obvious are the following facts. **Theorem 2**. : _Let \(k\) be unknown. \(RV(k-1)\) is unsolvable even if \(n\) is known and the ring is oriented._  
Proof. : By contradiction, let \(\mathcal{A}\) be an algorithm that solves \(RV(k-1)\) for any \(k\geq 2\). Consider an execution of \(\mathcal{A}\) where, initially, all agents are activated at the same time. Observe that, in this case, the agents must all move in the same direction; otherwise, if the adversary places the black hole at a distance of one from two agents that move towards each other, then both agents will enter the black hole, making \(RV(k-1)\) impossible. Thus, in this execution of \(\mathcal{A}\) all agents initially must move in the same direction, e.g., right. Let the agents be logically grouped in pairs \((h_{i},t_{i})\) (\(1\leq i\leq\lfloor k/2\rfloor\)), where \(h_{i}\) and \(t_{i}\) are called the head and the tail of the \(i\)-th pair; if \(k\) is odd, the remaining agent forms group \((h_{0})\) without a tail. Let the adversary choose the initial distinct locations of the agents as follows: each pair \((h_{i},t_{i})\) is positioned on two neighboring nodes, \(x_{i}\) and \(y_{i}\), with the head to the right of the tail; the single group \((h_{0})\) (if it exists) is positioned on an unoccupied node \(x_{0}\); the selection of the nodes is made so that, if \(k>3\) at least two pairs have an empty node between them (see Figure 1). Once all agents are simultaneously activated in this initial configuration and start moving right, the adversary slows down the movement of the heads, and makes each tail \(t_{i}\) reach its destination \(x_{i}\) simultaneously. Consider now what \(\mathcal{A}\) does at this point if \(k=2\), i.e., there is only one pair \((h_{1},t_{1})\). Let us focus on \(t_{1}\), which is currently on \(x_{1}\). Since, by assumption \(\mathcal{A}\) is correct, \(t_{1}\) must use cautious walk, thus it cannot move to the node \(z\), to the right of \(x_{1}\) (otherwise the adversary would choose \(z\) as the location of the black hole and both agents would disappear); if \(h_{1}\) has entered the black hole, within a finite amount of time \(t_{1}\) has to enter a terminal state. How this is achieved depends on the specifics of \(\mathcal{A}\); there are two possible cases:  
**Case 1:**\(t_{1}\) becomes _arrived_ after a finite amount of time \(\Delta_{1}\) from the start without ever reaching other nodes beside \(x_{1}\) and \(y_{1}\). 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_{1}\).