# Asynchronous Gathering in a Dangerous Ring +
## 3 Gathering When \(k\) Is Known and \(n\) Is Unknown
### Unoriented Rings  
Interestingly, we discover for the unoriented case better conditions than those we have found when \(k\) was known instead of \(n\). As in the oriented case, let us consider \(k\geq 4\). The main ideas of algorithm Shadow carry over to algorithm Un-Shadow, however, several technicalities have to be dealt with differently, due to lack of agreement on orientation. Again, we color the agents red and blue according to their initial orientation. In general, the agents follow algorithm Shadow, ignoring the agents of the different color, however, these exceptions apply:when an _R-explorer_ comes to a node already visited by an _L-explorer_ of the opposite color, it becomes an _R\({}^{*}\)-shadow_;
2. when an _L-explorer_ comes to a node already visited by an _R-explorer_ of the opposite color, it becomes an _R\({}^{*}\)-shadow_;
3. the L- and R- for shadows are used only for aging purposes. The tests are made against the shadows working in the same direction. For example, when a red _R\({}^{*}\)-shadow a_ arrives to the last explored node \(v\) in its direction, it checks whether \(v\) has been visited by a red _R-shadow_ or blue _L-shadow_. If yes, \(a\) becomes an _L\({}^{*}\)-shadow_ (and possibly awakens the shadow at \(v\), regardless of its color), otherwise \(a\) becomes an _R-shadow_;
4. when (if) two collectors cross each other on an edge, they may not agree on which endpoint to meet (if the situation is symmetric), therefore, only \(G(k-2,1)\) is guaranteed, not \(RV(k-2)\). Note that if all agents are of the same color, the algorithm Un-Shadow behaves exactly as algorithm Shadow and its correctness follows. Therefore, in the rest we assume there is at least one agent of each color. Let us also assume that a red _R-explorer_ moves to the right and a blue _R-explorer_ moves to the left. Lemma 6: _Within a finite amount of time, all nodes will be explored._  
Proof: Consider an initial configuration. Let \(v\) be an arbitrary node and let \(a_{l}\) and \(b_{l}\) be the closest and second closest agents to \(v\) from the left, and \(a_{r}\) and \(b_{r}\) be the closest agents from the right, respectively. (Not all of them might be present, but at least one side has at least two agents--because \(k\geq 4\).) From construction, if \(a_{l}\) or \(b_{l}\) is a red agent, it will travel to the right and either reach \(v\) or meet a left-moving agent that already visited \(v\). Similarly, \(v\) will be explored if \(a_{r}\) or \(b_{r}\) is blue. Without loss of generality, assume the left side has at least two agents and both \(a_{l}\) and \(b_{l}\) are blue. \(b_{l}\) starts moving left as an _R-explorer_ and when it enters the starting node of \(a_{l}\), it will become an _L-explorer_ and start moving right. Therefore, \(v\) will eventually be explored either by \(b_{l}\) or by an agent coming from the right. Lemma 7: _Within a finite amount of time, an agent will become a collector._  
Proof: Since the only time an agent is waiting is either when it is passive, or as an _R-shadow_ or _L-shadow_, and because \(k\geq 4\), eventually there will be a shadow for the right direction (red _R-shadow_ or blue _L-shadow_) and a shadow for the left direction. The rightmost such right shadow and the leftmost left shadow will not age anymore, because other shadows will age due to their rightmost/leftmost mark. When all nodes become explored (Lemma 6 tells us that this will eventually happen), at least one of those extreme agents will be awakened, traverse the explored nodes, and become a _collector_ (using the same arguments as in Lemma 5). Consider first the case when \(k\) is odd or \(n\) is even. Lemma 8: _There will be a unique collection point._  
Proof: If there is only one _collector_, there will be a single collection point--when the _collector_ traveled \(n-1\) nodes.