# Asynchronous Gathering in a Dangerous Ring +
## 3 Gathering When \(k\) Is Known and \(n\) Is Unknown
### Oriented Rings
A similar argument applies to the leftmost \(L\)-_shadow_ if the explored block reaches \(n-1\) nodes by exploring the leftmost node. Finally, if the explored block reaches size \(n-1\) by the merging of two blocks, either \(a\) will detect that directly, or will be awakened by the \(R^{*}\)-_shadow_ created by the collision of the blocks and re-scan to become a _collector_. We can finally state the following:  
**Theorem 11**. : _Let \(k\geq 4\). Algorithm Shadow solves \(RV(k-2)\) in \(8(n-2)\) time steps, using at most \(4n^{2}+nk-k^{2}/2+O(n)+o(k^{2})\) moves._  
Proof. : The correctness of the algorithm follows from Lemmas 4 and 5, and from the action of the _collector_ agent. Consider now the time steps of the algorithm. Let \(s_{0}\) be the position of the leftmost agent (measured from the Bh, going right) and \(s_{1}\) be the position of the second leftmost agent. Then, at time \(3(s_{1}-s_{0})\) the leftmost agent becomes an \(L\)-_explorer_ and enters the Bh at time \(3s+4(s_{1}-s_{0})\). If only the leftmost agent woke up spontaneously, it takes \(3(n-s_{0}-1)\) time step for the right exploration to reach the Bh. Therefore, all nodes are explored by time \(\max(3s+4(s_{1}-s_{0}),3(n-s_{0}-1))<4(n-2)\). Note also, that by time \(3(n-s_{0}-1)\) there is a single \(R\)-_explorer_, as all other \(R\)-_explorer_ agents would have entered a node already visited by an \(R\)-_explorer_. This also means that, by time \(3(n-s_{0}-1)+n-2<4(n-2)\) there will remain only one \(L\)-_explorer_, i.e., all other agents have become shadows. This means by time \(5(n-2)\) there will remain a single right shadow (\(R^{*}\)-_shadow_ or \(R\)-_shadow_) and by time \(6(n-2)\) there will be a single left shadow. If a shadow initiates a scan after time \(4(n-2)\), it will detect that \(n-1\) nodes have been explored and will become a _collector_. The algorithm would then terminate in at most \(n-2\) additional steps. An unsuccessful scan (without becoming a _collector_) takes at most \(2(n-3)\) steps, therefore a successful scan would be initiated at time less than \(6(n-2)\) and the algorithm would terminate by time \(8(n-2)\). Consider now the number of moves employed by the agents. First, note that at most \(O(n)\) moves are performed by the explorers. Let us now count the number of moves executed by all agents in states \(R^{*}\)-_shadow_ and \(R\)-_shadow_. Let us call _recharge_ the events of an \(R\)-_shadow_ being awakened by an \(R^{*}\)-_shadow_ or \(R\)-_explorer_. Note that, there are at most \(2n\) recharge events for all right shadows, as in each event either an \(R^{*}\)-_shadow_ becomes an \(L^{*}\)-_shadow_, or the \(R\)-_explorer_ has made progress. Moreover, an \(R\)-_shadow_ (or \(R^{*}\)-_shadow_) can make at most \(2(n-2)\) moves between recharges--if it is not recharged it turns into an \(L^{*}\)-_shadow_. This means that the total number of moves by all agents in states \(R\)-_shadow_ and \(R^{*}\)-_shadow_ can be bound by \(2n^{2}\). Using analogous arguments, it is easy to see that the total number of moves by all agents in states \(L\)-_shadow_ and \(L^{*}\)-_shadow_ is at most \(2n^{2}\) as well. The total cost of collection can be bound by \(nk-k^{2}/2+o(k^{2})\), using similar arguments as in the proof of Theorem 7.