# Asynchronous Gathering in a Dangerous Ring +
## 3 Gathering When \(k\) Is Known and \(n\) Is Unknown
### Unoriented Rings
#### 3.2.2 \(k\) Even
If passing the role of collector to an _explorer_, it passes also the distance information;
2. if a _collector_ meets another _collector_ (they must be from different collection points): 1. if they are of the same color, since they both agree on the same orientation of the ring, then they agree on a unique site (e.g., the rightmost of the two) as the final common collection point; 2. if they are of different colors, if the distance between the collection points is odd, they agree on the middle node as the final common collection point; otherwise, each chooses the closest site incident on the middle edge as the final collection point of its group; 3. each collector goes back to its group and notifies all the agents there of their final collection point. **Lemma 3**. : _Strategy Gr-Even guarantees that \((k-2)\) agents will either gather in the same node or gather within a distance of \(1\)._  
Proof. : If only one collection point is formed, the correctness of Gr-Even follows from the correctness of algorithm Gr-Odd. If two collection points are formed, then two collectors moving in opposite directions will eventually meet, decide on the final collection point (or edge), and inform all the followers. The time and movement costs of strategy Gr-Even can be easily determined. Figure 3: Mirror symmetric distribution for (**a**) \(n\) odd, and (**b**) \(n\) even. **Theorem 8**: _Strategy Gr-Even terminates in a time of at most \(5(n-2)\)._  
If only one collection point is formed, the argument is the same as in the proof of Theorem 7, and the time complexity is at most \(5(n-2)\). Assume now that two collection points are formed at a distance \(d\) from each other (measuring over part of the ring not containing the Bh). Let \(t_{1}\) be the time when the last collection point is formed and let \(s\) be the number of edges explored at that moment. Let \(t_{2}\) be the time when the two collectors meet, and \(t_{3}\) be the time when all agents gather at the common collection point or edge. Clearly, \(t_{1}\leq 3s\), and \(t_{2}\leq t_{1}+d/2+2(n-2-s)\) (since the collectors that meet travel towards each other, and at most \(n-2-s\) edges must be traversed using cautious walk). It takes less than \(d\) time steps for the collectors to come back to their collection points to inform the followers (they could have met quite asymmetrically), and \(d/2\) steps for everybody to come to the new common collection point (recall, it is in the middle, between the two old collection points); hence, \(t_{3}\leq t_{2}+3/2d\). Combining together we obtain \(t_{3}\leq 3s+d/2+2(n-2-s)+3/2d=2(n-2)+2d+s\). Since \(d\) and \(s\) are at most \(n-2\), then \(t_{3}\leq 5(n-2)\). **Theorem 9**: _Strategy Gr-Even uses at most \(3 nk/2-k^{2}/4+o(nk)\) moves._  
If there is a single collection point, the proof of Theorem 7 applies directly. If there are two collection points, applying Theorem 5 for the two groups creating collection points yields \(2\times(nk/2+k^{2}/8)\) moves. Again, only \(O(n)\) moves will be spent by collectors. Incidentally, the cost of moving the agents from the two collection points to the final collection point (or pair of points) is \((n-2)(k-2)/2\) regardless of the location of the final collection point, as both collection points contain the same amount of followers. Summarizing:  
**Theorem 10**:  
_1. If \(k\) is odd, \(RV(k-2)\) can always be solved. 2. If \(k\) is even, \(RV(p)\) cannot be solved for \(p>(k-2)/2\); however, \(RV((k-2)/2)\) can always be solved. 3. \(G(k-2,1)\) can always be solved. 4. Gathering When \(k\) Is Unknown and \(n\) Is Known_  
We now consider the case when \(k\) is unknown. Clearly, by Theorem 3, the ring size \(n\) must be known for any non-trivial gathering to be possible. Let us examine under what conditions and how the problem can be solved. Since \(k\) is unknown, we know by Theorem 2 that there exists no algorithm that solves \(RV(k-1)\), even if \(n\) is known. Let us now examine under what conditions the problem \(RV(k-2)\) can be solved.