# Asynchronous Gathering in a Dangerous Ring +
## 3 Gathering When \(k\) Is Known and \(n\) Is Unknown
### Oriented Rings
If \(size_{a}=0\) (i.e., you left this node, traveled across the explored block and returned, and the _R-explorer_ meanwhile did not explore a new node), wait until woken up by an _R\({}^{*}\)-shadow_ or the _R-explorer_ (which just explored the node to the right and returned to make the link safe). In the latter case, become _R\({}^{*}\)-shadow_, otherwise, set \(size_{a}=0\) and move left until the last safe node is reached, counting in \(size_{a}\) the number of nodes traversed. If \(size_{a}=n-1\), then become _collector_, else become _R\({}^{*}\)-shadow_. * _L\({}^{*}\)-shadow_: Move left until the last safe node \(v\) is reached, decrementing \(size_{a}\). If \(v\) has already been visited by an _L-shadow_, become _passive_ (but if the _L-shadow_ is waiting at \(v\), wake it up before becoming _passive_). If \(v\) has not been visited by an _L-shadow_, become _L-shadow_. * _L-shadow_: Analogous to _R-shadow_, but with reversed directions. * _collector_: A _collector_ agent traverses the explored part and collects all the agents on the way (if an agent meets a _collector_, it stops its activity and follows the _collector_). Once the whole explored part has been traversed (_collector_ counts \(n-1\) links), \(k-2\) agents have been collected and have gathered at the same place. There is a technical detail: it can happen that both shadows can become collectors. In that case, the gathering point is the node where they meet (or, if they crossed each other on a link, the right endpoint of that link). * _passive:_ Wait to be collected by a _collector_. Lemma 4: _Within a finite amount of time all nodes will be explored, there will be only one R-explorer and one L-explorer, and they will both enter the black hole._  
Proof. : Consider the rightmost agent. From construction, it will remain an _R-explorer_ until it reaches the Bh. Any other _R-explorer_ will eventually become an _L-explorer_. The leftmost of those will remain an _L-explorer_ and will eventually enter the Bh, all others will become an _R\({}^{*}\)-shadow_. Of those, the rightmost one will eventually become an _R-shadow_, any remaining one will become an _L\({}^{*}\)-shadow_. Finally, out of those, the leftmost one will become an _L-shadow_, all others will become _passive_. Let \(v\) be an arbitrary node. If there was an agent to the left of \(v\) in the initial configuration, the closest such agent \(a\) will reach \(v\) as an _R-explorer_. If there were no agents to the left of \(v\), the leftmost _L-explorer_ would eventually explore it. Lemma 5: _Eventually, at least one agent will become a collector._  
Proof. : Consider the rightmost _R-shadow_\(a\) (since \(k\geq 4\) and from the proof of Lemma 4 we know that there will be an _R-shadow_). From construction, \(a\) will remain an _R-shadow_ (more precisely, alternating between _R-shadow_ and _R\({}^{*}\)-shadow_) until it becomes a _collector_ or itself is collected by a _collector_. It remains to be proven that \(a\) will not be blocked, forever waiting for the next node to the right to be explored. Applying Lemma 4, we know that eventually there will be a single explored block. Consider the last step leading to an explored block of \(n-1\) nodes. If the explored block  
Figure 4: An example for Algorithm Shadow, where the ring is assumed to be oriented clockwise, with 8 agents. The empty circles represent _active_ agents; the white squares are the _explorers_, the grey squares the _shadows_, and the black squares the _passive_ agents. The bold line shows the segments delimited by the explorers. The numbers are placed only to clarify how the agents move and are not used at all during the computation. reaches \(n-1\) nodes by exploring the rightmost node, either \(a\) is waiting in the rightmost safe node (in which case it will be awakened by the \(R\)-_explorer_ and will traverse the \(n-1\) explored nodes to become a collector), or is currently scanning the explored block and will eventually return to the (new) rightmost explored node, notice that the block has been expanded, and re-scan it.