# Asynchronous Gathering in a Dangerous Ring +
## 3 Gathering When \(k\) Is Known and \(n\) Is Unknown
### Unoriented Rings
#### 3.2.2 \(k\) Even  
Consider now the case when \(k\) is even (recall \(k\) is known). We first observe that \(RV((k-2)/2)\) can always be solved by trivially having each set execute the gathering algorithm GoRight for oriented rings, and terminating it when at least \(k/2-1\)_follower_ agents of the same set gather in the same node. To complete the proof, we need to show that, when \(k\) is even, gathering of a greater number of agents cannot be guaranteed. **Lemma 2**. : _If \(k\) is even then \(RV(p)\) cannot be solved for \(p>(k-2)/2\)._  
Proof. : Assume first that \(n\) is odd. Consider the symmetry axis passing through the Bh and dividing the ring into two sides of equal size (note that when \(n\) is odd, the symmetry axis passes through an edge); denote by \(\overline{v}\) the symmetric image of node \(v\). Consider now a symmetric but \"complemented\" distribution of the agents on the two sides of the ring: if there is a blue agent in node \(v\) then there is a red agent in node \(\overline{v}\) (see Figure 2(a)); thus, to each agent \(a\) with homebase \(v\), corresponds an agent \(\overline{a}\), of opposite color, with homebase \(\overline{v}\). In this distribution, let both neighbors of the Bh be occupied by agents. Consider now a synchronous execution (i.e., every move of an agent takes exactly one time step) of any solution algorithm, where all agents start at the same time, and where the first move of the agents neighboring the Bh is directed towards the Bh. Observe now that, for any move in a given direction by an agent \(a\), there corresponds a move in the opposite direction by agent \(\overline{a}\). In particular, whenever an agent \(a\) crosses the symmetry axis, agent \(\overline{a}\) will cross the axis in the opposite direction. Since after the first step there are \((k-2)/2\) agents on each side (two agents went into the Bh), the number of agents on each side will always be \((k-2)/2\), thus rendering \(RV(p)\) with \(p>(k-2)/2\) impossible. If \(n\) is even, choose the symmetry axis to be the line dividing the ring into two sides of equal size, passing through the link between the Bh and its clockwise neighbor \(v\) (see Figure 2(b)). Force the other link incident to \(v\) to be very slow. Since the algorithm does not know \(n\), it cannot distinguish this situation from the case of \(n\) odd, and the same arguments as for \(n\) odd would apply. We now show that, although we cannot guarantee that more than half of the surviving agents gather, we can however guarantee that _all_ the surviving agents gather within a distance of \(1\) from each other. To prove this, we use the following strategy, that we will call Gr-Even. First, each set of agents executes the gathering algorithm GoRight for oriented rings, independently of and ignoring the agents of the other set, and terminates it when (at least) \(k/2-1\)_follower_ agents of the same set gather in the same node. Notice that it is possible that two (but no more than two) such gathering points will be formed; further, notice that they could be both made of agents of the same color! Let us concentrate on one of them and assume, without loss of generality, that it is formed of _red_ agents. By definition, associated with it, there is a red _explorer_ that will become a _right-collector_ once it realizes the collection point has been formed; among the _followers_ gathered there, a _left-collector_ has also been selected. Both collectors behave as in Gr-Odd except that, now, each of them could encounter a collector from the other group (if it exists). Therefore, we need to add the following additional rules:  
1. a _collector_ computes and remembers the distance from its collection point.