# Asynchronous Gathering in a Dangerous Ring +
## 3 Gathering When \(k\) Is Known and \(n\) Is Unknown
### Unoriented Rings
#### 3.2.1 \(k\) Odd  
Consider first the case when \(k\) is odd (recall \(k\) is known). In this case, only one of the two sets contains at least \((k-1)/2\) agents, for example, the red one. The agents of each set first of all execute a modification of algorithm GoRight for oriented rings, independently of and ignoring the agents of the other set, terminating this step as soon as \((k-1)/2\)_red follower_ agents gather in the same node: notice that, since \(k\) is odd, there is at most one such node. This node is designated as the _red collection_ point: at this time, on the whiteboard of this node it is specified which is the left and right direction of the winning group (in this case, the red one); this direction will be used from now on as the global orientation of the ring. Next, one of the agents at the collection point node is designated to be the _right-collector_. The task of the _right-collector_ is to move rightwards, to notify all agents on its way that the collection point has been identified, and to go there for final gathering: notification occurs through the whiteboard, by writing there the safe direction to follow to reach the collection point. A second agent from the collection point is designated as the _left-collector_: it will behave similarly to the right one, moving leftwards. Upon being notified, an agent goes safely towards the collection point. As we will show, at most two agents (possibly none) enter the black hole; all others achieve the gathering within a finite amount of time. The set of rules describing the algorithm is reported in the following. All agents at the beginning are _explorers_ (either red or blue). **Algorithm** Gr-Odd:  
1. A red (resp. blue) _explorer_ at node \(u\) moves to its right using cautious walk. 1. if it enters the black hole, it dies; 2. if it enters a node visited by another red (resp. blue) agent, it becomes a red (resp. blue) _follower_, returns to \(u\), making the link safe; 3. if it enters a node that is a blue (resp. red) _collection point_, it becomes a blue (resp. red) _follower_; 4. if it enters a node where on the whiteboard there is a message indicating the direction of the collection point, it becomes _notified_; 5. if it enters a node where on the whiteboard there is a message to become a _left-collector_, it cancels the message, and it becomes a _left-collector_; 6. if it enters an unvisited node, it returns to \(u\). If there are less than \((k-1)/2\) red (resp. blue) _followers_ at \(u\), it renders the right link safe and goes again to the _right\((u)\)_ to continue the cautious walk. If there are at least \((k-1)/2\) red (resp. blue) _followers_ at \(u\), it becomes a _right-collector_; moreover, if \(u\) is not a collection point, it registers this node as the red (resp. blue) _collection_ point on the whiteboard. 2. A red (resp. blue) _follower_ at node \(u\): 1. if \(u\) is not a collection point and there are less than \((k-1)/2\) red (resp. blue) _followers_, it moves to its right if its right link is safe; 2. if \(u\) is not a collection point and there are at least \((k-1)/2\) red (resp. blue) followers at \(u\), it registers \(u\) as a collection point; if its right link is safe, it becomes a _right-collector_, otherwise, it becomes a _left-collector_; 3. if \(u\) is a collection point and there is no _left-collector_, then it becomes a _left-collector_; 4. if it enters a node where on the whiteboard there is a message indicating the direction of the collection point, it becomes _notified_. 3. The _left-collector_\(x\) travels (using cautious walk when necessary) left, writing on the whiteboards of every visiting node the instruction to reach the collection point; it does so until it either dies in the black hole or reaches the last safe node explored by a blue _explorer_. In the latter case, the _left-collector_ leaves a message for the blue _explorer_\(y\), informing it of the collection point and instructing it to become a _left-collector_; it then becomes _notified_. 4.