# Asynchronous Gathering in a Dangerous Ring +
## 3 Gathering When \(k\) Is Known and \(n\) Is Unknown
### Oriented Rings  
We now introduce an algorithm, called Shadow, quite different from the ones used when \(k\) is known, that solves \(RV(k-2)\) for \(k\geq 4\) (also refer to the example depicted in Figure 4). The overall idea is to associate with each contiguous block of explored nodes a group of agents, expanding that specific block until either (1) the explored block contains \(n-1\) nodes (in which case a final _collection_ phase is initiated, whose goal is to collect the agents into a final designated collection point); or (2) the block merges with a neighboring explored block (in which case the corresponding groups of agents are combined into one group, expanding the new, bigger block). The group of agents expanding a block consists of at least one and at most four agents. The agents associated with a group are of two kinds: _explorers_ and _shadows_--at most one of each type for each direction. The task of the explorers is to expand the explored block in the opposite directions. The shadows scan the explored block between the explorers, countingthe size of the block. Their goal is to detect when the block contains \(n-1\) explored nodes (each node remembers--i.e., on the whiteboard--which types of agents have visited it so far). At the beginning, each explored block consists of a single node containing an agent starting as an _R-explorer_, whose task is to expand the block by moving \(right(\cdot)\). As the blocks grow, they eventually touch and their agents are combined, as follows:  
* a two-agent block (i.e., created by merging two one-agent blocks) has one _R-explorer_ and one _L-explorer_;
* a three-agent block has two explorers (one in each direction) and an _R-shadow_;
* a four-agent block has two explorers and two shadows (one in each direction);
* any additional agent (e.g., after merging two four-agent blocks) becomes _passive_. The main technical difficulty arises from the fact that the whole process is distributed, asynchronous, and the agents are not immediately aware when their block collides with another block. In addition, both ends of a block might collide with neighboring blocks at about the same time, thus complicating the coordination between the agents of the block. The adopted technique can be seen as _aging_ of agents from initial _R-explorer_ through _L-explorer_, _R-shadow_, _L-shadow_ and finally _passive_. The goal is to have only one agent of each type per explored block--whenever an agent learns that there is a more extreme (to the right for _R-_ agents), to the left for _L-_ agents) agent of the same type, the agent is aged. The actual algorithm has a few exceptions to this rule, as sometimes the aging has to be delayed in order to inform waiting shadows to recompute the size of the explored block. **Algorithm** Shadow:  
**Agent states**: _R-explorer_, _L-explorer_, _R\({}^{*}\)-shadow_, _R-shadow_, _L\({}^{*}\)-shadow_, _L-shadow_, _passive_, _collector_, _collector_ and _shadow_ agents maintain counter _size_. At the beginning all agents are _R-explorer_. **Algorithm for agent _a_:  
* _R-explorer_: Move right using cautious walk as needed until a node \(v\) already visited by a different _R-explorer_ is entered. Become _L-explorer_. * _L-explorer_: Move left using cautious walk as needed until a node \(v\) already visited by an _L-explorer_ is entered. Become _R\({}^{*}\)-shadow_ and set \(size_{a}\) to \(0\). * _R\({}^{*}\)-shadow_: Move right until the last safe node \(v\) is reached, decrementing \(size_{a}\). If \(v\) has already been visited by an _R-shadow_, set \(size_{a}\) to \(0\) and become _L\({}^{*}\)-shadow_. If the _R-shadow_ is waiting at \(v\), wake it up. If \(v\) has not been visited by an _R-shadow_, become _R-shadow_. * _R-shadow_: (Starting at the rightmost safe node in its explored part.)