Marjorie Bournat

Swan Dubois

Franck Petit

Gracefully

Gracefully Degrading Gathering in Dynamic Rings

Keywords:

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The classical approach in distributed computing consists in, first, fixing a set of assumptions that captures the properties of the studied system (atomicity, synchrony, faults, communication modalities, etc.) and, then, focusing on the impact of these assumptions in terms of calculability and/or of complexity on a given problem. When coming to dynamic systems, it is natural to adopt the same approach. Many recent works focus on defining pertinent assumptions for capturing the dynamics of those systems [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF][START_REF] Kuhn | Distributed computation in dynamic networks[END_REF][START_REF] Xuan | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF]. When these assumptions become very weak, that is, when the system becomes highly dynamic, a somewhat frustrating but not very surprising conclusion emerge: many fundamental distributed problems are impossible at least, in their classical form [START_REF] Biely | Gracefully degrading consensus and k -set agreement in directed dynamic networks[END_REF][START_REF] Braud-Santoni | The next 700 impossibility results in timevarying graphs[END_REF][START_REF] Casteigts | Shortest, fastest, and foremost broadcast in dynamic networks[END_REF].

To circumvent such impossibility results, Biely et al. recently introduced the gracefully degrading approach [START_REF] Biely | Gracefully degrading consensus and k -set agreement in directed dynamic networks[END_REF]. This approach relies on the definition of weaker but related variants of the considered problem. A gracefully degrading algorithm guarantees that it will solve simultaneously the original problem under some assumption of dynamics and each of its variants under some other (hopefully weaker) assumptions. As an example, Biely et al. provide a consensus algorithm that gracefully degrades to k-set agreement when the dynamics of the system increase. The underlying idea is to solve the problem in its strongest variant when connectivity conditions are sufficient but also to provide (at the opposite of a classical algorithm) some minimal quality of service described by the weaker variants of the problem when those conditions degrade.

Note that, although being applied to dynamic systems by Biely et al. for the first time, this natural idea is not a new one. Indeed, indulgent algorithms [START_REF] Alistarh | Generating fast indulgent algorithms[END_REF][START_REF] Dutta | The inherent price of indulgence[END_REF][START_REF] Guerraoui | Indulgent algorithms[END_REF] provide similar graceful degradation of the problem to satisfy with respect to synchrony (not with respect to dynamics). Speculation [START_REF] Dubois | Introducing speculation in self-stabilization: an application to mutual exclusion[END_REF][START_REF] Kotla | Zyzzyva: Speculative byzantine fault tolerance[END_REF] is a related, but somewhat orthogonal, concept. A speculative algorithm solves the problem under some assumptions and moreover provides stronger properties (typically better complexities) whenever conditions are better.

The goal of this paper is to apply graceful degradation to robot networks where a cohort of autonomous robots have to coordinate their actions in order to solve a global task. We focus on gathering in a dynamic ring. In this problem, starting from any initial position, robots must meet on an arbitrary location in a bounded time. Note that we can classically split this specification into a liveness property (all robots terminate in bounded time) and a safety property (all robots that terminate do so on the same node).

Related works. Several models of dynamic graphs have been defined recently [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF][START_REF] Latapy | Stream graphs and link streams for the modeling of interactions over time[END_REF][START_REF] Xuan | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF]. In this paper, we adopt the evolving graph model [START_REF] Xuan | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF] in which a dynamic graph is simply a sequence of static graphs on a fixed set of nodes: each graph of this sequence contains the edges of the dynamic graph present at a given time. We also consider the hierarchy of dynamics assumptions introduced by Casteigts et al. [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF]. The idea behind this hierarchy is to gather all dynamic graphs that share some temporal connectivity properties within classes. This allows us to compare the strength of these temporal connectivity properties based on the inclusion of classes between them. We are interested in the following classes: COT (connected-over-time graphs) where edges may appear and disappear without any recurrence nor periodicity assumption but guaranteeing that each node is infinitely often reachable from any other node; RE (recurrent-edge graphs) where any edge that appears at least once does so recurrently; BRE (bounded-recurrent-edge graphs) where any edge that appears at least 1: Summary of our results. The symbol -means that a stronger variant of the problem is already proved solvable under the dynamics assumption. Our algorithm is gracefully degrading since it solves each variant of the gathering problem as soon as dynamics assumptions allow it. once does so recurrently in a bounded time; AC (always-connected graphs) where the graph is connected at each instant; and ST (static graphs) where any edge that appears at least once is always present. Note that ST ⊂ BRE ⊂ RE ⊂ COT and ST ⊂ AC ⊂ COT by definition.

G G E G W G EW COT
In robot networks, the gathering problem was extensively studied in the context of static graphs, e.g., [START_REF] Flocchini | Multiple mobile agent rendezvous in a ring[END_REF][START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF][START_REF] Stefano | Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings[END_REF]. The main motivation of this vein of research is to characterize the initial positions of the robots allowing gathering in each studied topology in function of the assumptions on the robots as identifiers, communication, vision range, memory, etc. On the other hand, few algorithms have been designed for robots evolving in dynamic graphs. The majority of them deals with the problem of exploration [START_REF] Bournat | Self-stabilizing robots in highly dynamic environments[END_REF][START_REF] Bournat | Computability of perpetual exploration in highly dynamic rings[END_REF][START_REF] Flocchini | On the exploration of time-varying networks[END_REF][START_REF] Ilcinkas | Exploration of constantly connected dynamic graphs based on cactuses[END_REF][START_REF] Luna | Live exploration of dynamic rings[END_REF] (robots must visit each node of the graph at least once or infinitely often depending on the variant of the problem). In the most related work to ours [START_REF] Luna | Gathering in dynamic rings[END_REF], Di Luna et al. study the gathering problem in dynamic rings. They first note the impossibility of the problem in the AC class and consequently propose a weaker variant of the problem, the near-gathering: all robots must gather in finite time on two adjacent nodes. They characterize the impact of chirality (ability to agree on a common orientation) and cross-detection (ability to detect whenever a robot cross the same edge in the opposite direction) on the solvability of the problem. All their algorithms are designed for the AC class and are not gracefully degrading.

Contributions. By contrast with the work of Di Luna et al. [START_REF] Luna | Gathering in dynamic rings[END_REF], in this paper we choose to keep unchanged the safety of the classical gathering problem (all robots that terminate do so on the same node) and, to circumvent impossibility results, we weaken only its liveness: at most one robot may not terminate or (not exclusively) all robots that terminate do so eventually (and not in a bounded time as in the classical specification). This choice is motivated by the approach adopted with indulgent algorithms [START_REF] Alistarh | Generating fast indulgent algorithms[END_REF][START_REF] Dutta | The inherent price of indulgence[END_REF][START_REF] Guerraoui | Indulgent algorithms[END_REF]: the safety captures the "essence" of the problem and should be preserved even in degraded variants of the problem. Namely, we obtain the four following variants of the gathering problem: G (gathering) all robots terminate on the same node in bounded time; G E (eventual gathering) all robots terminate on the same node in finite time; G W (weak gathering) all robots but (at most) one terminate on the same node in bounded time; and G EW (eventual weak gathering) all robots but (at most) one terminate on the same node in finite time.

We present then a set of impossibility results, summarized in Table 1, for these specifications for different classes of dynamic rings. Motivated by these impossibility results, our main contribution is a gracefully degrading gathering algorithm. For each class of dynamic rings we consider, our algorithm solves the strongest possible of our variants of the gathering problem (refer to Table 1). Note that this challenging property is obtained without any knowledge or detection of the dynamics by the robots that always execute the same algorithm. Our algorithm needs that robots have distincts identifiers, chirality, strong multiplicity detection (i.e. ability to count the number of colocated robots), memory (of size sublinear in the size of the ring and identifiers), and communication capacities but deals with (fully) anonymous ring. Note that these assumptions (whose necessity is left as an open question here) are incomparable with those of Di Luna et al. [START_REF] Luna | Gathering in dynamic rings[END_REF] that assume anonymous but home-based robots (hence, non fully anonymous rings). This algorithm brings two novelties with respect to the state-of-the-art: (i) it is the first gracefully degrading algorithm dedicated to robot networks; and (ii) it is the first algorithm solving (a weak variant of) the gathering problem in the class COT (the largest class of dynamic graphs that guarantees an exploitable recurrent property).

Roadmap. The organization of the paper follows. Section 2 presents formally the model we consider. Section 3 sums up impossibility results while Section 4 presents our gracefully degrading algorithm. Section 5 proves the correctness of our gracefully degrading algorithm. Finally, Section 6 concludes the paper with some comments.

Model

Dynamic graphs. We consider the model of evolving graphs [START_REF] Xuan | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF]. Time is discretized and mapped to N. An evolving graph G is an ordered sequence {G 0 , G 1 , . . .} of subgraphs of a given static graph G = (V, E) such that, for any i ≥ 0, we call G i = (V, E i ) the snapshot of G at time i. Note that V is static and |V | is denoted by n.

We say that the edges of E i are present in G at time i. G is the footprint of G. The underlying graph of G, denoted by U G , is the static graph gathering all edges that are present at least once in G (i.e. U G = (V, E G ) with E G = ∞ i=0 E i ). An eventual missing edge is an edge of E such that there exists a time after which this edge is never present in G. A recurrent edge is an edge of E that is not eventually missing. The eventual underlying graph of G, denoted U ω G , is the static graph gathering all recurrent edges of G (i.e. U ω G = (V, E ω G ) where E ω G is the set of recurrent edges of G). We only consider graphs whose footprints are anonymous and unoriented rings of size n ≥ 4. The class COT (connected-over-time graphs) contains all evolving graphs such that their eventual underlying graph is connected. The class RE (recurrent-edges graphs) gathers all evolving graphs whose footprint contains only recurrent edges. The class BRE (bounded-recurrent-edges graphs) includes all evolving graphs in which there exists a δ ∈ N such that each edge of the footprint appears at least once every δ units of time. The class AC (always-connected graphs) collects all evolving graphs where the graph G i is connected for any i ∈ N. The class ST (static graphs) encompasses all evolving graphs where the graph G i is the footprint for any i ∈ N.

Robots. We consider systems of R ≥ 4 autonomous mobile entities called robots moving in a discrete and dynamic environment modeled by an evolving graph G = {(V, E 0 ), (V, E 1 ) . . .}, V being a set of nodes representing the set of locations where robots may be, E i being the set of bidirectional edges through which robots may move from a location to another one at time i. Each robot knows n and R. Each robot r possesses a distinct (positive) integer identifier id r strictly greater than 0. Initially, a robot only knows the value of its own identifier. Robots have a persistent memory so they can store local variables. Each robot r is endowed with strong local multiplicity detection, meaning that it is able to count the exact number of robots that are co-located with it at any time t. When this number equals 1, the robot r is isolated at time t. By opposition, we define a tower T as a couple (S, θ), where S is a set of robots with |S| > 1 and θ = [t s , t e ] is an interval of N, such that all the robots of S are located at a same node at each instant of time t in θ and S or θ is maximal for this property. We say that the robots of S form the tower at time t s and that they are involved in the tower between time t s and t e . Robots are able to communicate (by direct reading) the values of their variables to each others only when they are involved in the same tower.

Finally, all the robots have the same chirality, i.e. each robot is able to locally label the two ports of its current node with left and right consistently over the ring and time and all the robots agree on this labeling. Each robot r has a variable dir r that stores the direction it currently considers (right, left or ⊥).

Algorithms and execution. The state of a robot at time t corresponds to the values of its local variables at time t. The configuration γ t of the system at time t gathers the snapshot at time t of the evolving graph, the positions (i.e. the nodes where the robots are currently located) and the state of each robot at time t. The view of a robot r at time t is composed from the state of r at time t, the state of all robots involved in the same tower as r at time t if any, and of the following local functions: ExistsEdge(dir, round), with dir ∈ {right, lef t} and round ∈ {current, previous} which indicates if there exists an adjacent edge to the location of r at time t and t -1 respectively in the direction dir in G t and in G t-1 respectively; N odeM ate() which gives the set of all the robots co-located with r (r is not included in this set); N odeM ateIds() which gives the set of all the identifiers of the robots co-located with r (excluded the one of r) ; and HasM oved() which indicates if r has moved between time t -1 and t (see below).

The algorithm of a robot is written in the form of an ordered set of guarded rules (label) :: guard -→ action where label is the name of the rule, guard is a predicate on the view of the robot, and action is a sequence of instructions modifying its state. Robots are uniform in the sense they share the same algorithm. Whenever a robot has at least one rule whose guard is true at time t, we say that this robot is enabled at time t. The local algorithm also specifies the initial value of each variable of the robot but cannot restrict its arbitrary initial position.

Given an evolving graph G = {G 0 , G 1 , . . .} and an initial configuration γ 0 , the execution σ in G starting from γ 0 of an algorithm is the maximal sequence (γ 0 , γ 1 )(γ 1 , γ 2 )(γ 2 , γ 3 ) . . . where, for any i ≥ 0, the configuration γ i+1 is the result of the execution of a synchronous round by all robots from γ i that is composed of three atomic and synchronous phases: Look, Compute, Move. During the Look phase, each robot captures its view at time i. During the Compute phase, each robot enabled by the algorithm executes the action associated to the first rule of the algorithm whose guard is true in its view. In the case the direction dir r of a robot r is in {right, lef t}, the Move phase consists of moving r in the direction it considers if there exists an adjacent edge in that direction to its current node, otherwise (i.e. the adjacent edge is missing) r is stuck and hence remains on its current node. In the case where the direction dir of a robot is ⊥, the robot remains on its current node.

Impossibility Results

In this section, we present the set of impossibility results summarized in Table 1. These results show that some variants of the gathering problem cannot be solved depending on the dynamics of the ring in which the robots evolve and hence motivate our gracefully degrading approach.

First, we prove in Theorem 1 that G E (the eventual variant of the gathering problem) is impossible to solve in AC. Note that Di Luna et al. [START_REF] Luna | Gathering in dynamic rings[END_REF] provide a similar result but show it in an informal way only. Moreover, our result subsumes theirs since the considered models are different: we show that the result remains valid even if robots are identified, able to communicate, and not necessarily initially all scattered (other different assumptions exist between the two models but have no influence on our proof).

The proof of Theorem 1 relies on a generic framework introduced by Braud-Santoni et al. [START_REF] Braud-Santoni | The next 700 impossibility results in timevarying graphs[END_REF]. Note that even though this generic framework is designed for another model (namely, the classical message passing model), it is straightforward to borrow it for our current model. Indeed, as its proof only relies on the determinism of algorithms and indistinguishability of dynamic graphs, its arguments are directly translatable in our model. We present briefly this framework here. The interested reader is referred to the original work [START_REF] Braud-Santoni | The next 700 impossibility results in timevarying graphs[END_REF] for more details.

This framework is based on a result showing that, if we take a sequence of evolving graphs with ever-growing common prefixes (that hence converges to the evolving graph that shares all these common prefixes), then the sequence of corresponding executions of any deterministic algorithm also converges. Moreover, we are able to describe the execution to which it converges as the execution of this algorithm in the evolving graph to which the sequence converges. This result is useful since it allows us to build counterexamples in the context of impossibility results. Indeed, it is sufficient to construct a sequence of evolving graphs with ever-growing common prefixes and prove that its corresponding execution violates the specification of the problem for evergrowing time to exhibit an execution that never satisfies the specification of the problem. Theorem 1. There exists no deterministic algorithm that satisfies G E in rings of AC with size 4 or more for 4 robots or more.

Proof. By contradiction, assume that there exists a deterministic algorithm A that satisfies G E in any ring of AC with size 4 or more for 4 robots or more. Let us choose arbitrarily two of these robots and denote them r 1 and r 2 .

Note that A may allow the last robot to terminate only if it is co-located with all other robots (otherwise, we obtain a contradiction with the safety of G E ). So, proving the existence of an execution of A in a ring of AC where r 1 and r 2 are never co-located is sufficient to obtain a contradiction with the liveness property of G E and to show the result. This is the goal of the remainder of the proof.

To help the construction of this execution, we need introduce some notation as follows. Given an evolving graph F, an edge ẽ of F, and a time interval I ⊆ N, the evolving graph F\{ẽ, I} is the evolving graph F defined by: e ∈ F i if and only if e = ẽ ∧ i / ∈ I ∧ e ∈ F i or e = ẽ ∧ e ∈ F i . Given an evolving graph F and two integers t 1 , t 2 such that t 1 ≤ t 2 , we denote F t1,...,t2 the subsequence {F t1 , . . . , F t2 } of F. Given two evolving graphs, F and H, and an integer t, the evolving graph F {0,...,t} ⊗ H {t+1,...,+∞} is the evolving graph F defined by: e ∈ F i if and only if i ≤ t ∧ e ∈ F i or i > t ∧ e ∈ H i .

Let G = {G 0 , G 1 , . . .} be a graph of AC whose footprint G is a ring of size 4 or more such that ∀i ∈ N, G i = G. Consider two nodes u and v of G, such that the node v is the adjacent node of u in G to the right. We denote by e uv the edge linking the nodes u and v. Let G be G\{e uv , N}. Let ε be the execution of A in G starting from the configuration where r 1 is located on node u and r 2 is located on node v. Note that the distance in the footprint of G between r 1 and r 2 (denoted d(r 1 , r 2 )) is equal to one.

Our goal is to construct a sequence of rings of AC denoted (G m ) m∈N such that G 0 = G and, for any i ≥ 0, r 1 and r 2 are never co-located before time t i in ε i (the execution of A in G i starting from the same configuration as ε), (t m ) m∈N being a strictly increasing sequence with t 0 = 0. First, we show in the next paragraph that, if some such G i exists and moreover ensures the existence of a time t i + 1 > t i where the two robots are still on different nodes in ε i , then we can construct G i+1 as shown on Figure 1. We then prove that our construction guarantees the existence of such a t i , implying the well-definition of (G m ) m∈N .

As r 1 and r 2 are not co-located at time t i in ε i , at least one of them must move in finite time in any execution starting from γ ti (otherwise, we obtain a contradiction with the liveness of G E ). Let t i ≥ t i be the smallest such time in the execution where the topology of the graph does not evolve from time t i to time t i . In the following, we show how we construct the evolving graph G i+1 , in function of t i and G i . As we assume that in G i , at time t i + 1, r 1 and r 2 are on two different nodes, i.e. d(r 1 , r 2 ) ≥ 1, the following cases are possible.

Case 1: d(r 1 , r 2 ) = 1 at time t i + 1.
Let e be the edge between the respective locations of r 1 and r 2 at time t i + 1. We define G i+1 on the same footprint as G i by G i+1 = G 0,...,t i i ⊗ (G t i +1,...,+∞ \{e, {t i + 1, . . . , +∞}}).

Case 2: d(r 1 , r 2 ) = 2 at time t i + 1. Denote e and e the two consecutive edges between the respective locations of r 1 and r 2 at time t i + 1.

1)

2)

3) We define first G i on the same footprint as G i by G i = G 0,...,t i i ⊗ G t i +1,...,+∞ . Note that G i belongs to AC by assumption on G i and since G is the static ring. Then, to avoid a contradiction with the liveness of G E , we know that there exists a time α i ≥ t i + 1 in the execution of A on G i where at least one of our two robots move (w.l.o.g. assume that α i is the smallest one). If, at time α i + 1, the two robots are on distinct nodes in G i , then we define G i+1 on the same footprint as G i by G i+1 = G 0,...,t i i ⊗ G t i +1,...,+∞ . If, at time α i + 1, the two robots are on the same node in G i , then we define G i+1 on the same footprint as G i by G i+1 = G 0,...,t i i ⊗ (G t i +1,...,+∞ \{e, {t i + 1, . . . , +∞}}).

Case 3: d(r 1 , r 2 ) > 2 at time t i + 1.
We define G i+1 on the same footprint as

G i by G i+1 = G 0,...,t i i ⊗ G t i +1,...,+∞ .
Note that G i and G i+1 are indistinguishable for robots until time t i . This implies that, at time t i + 1, r 1 and r 2 are on the same nodes in ε i and in ε i+1 . By construction of t i , either r 1 or r 2 or both of the two robots move at time t i in ε i+1 . Moreover, by construction of G i , even if one or both of the robots move during the Move phase of time t i , at time t i + 1 the robots are still on two distinct nodes (since, in all cases above, either the distance between the robots before the move is strictly greater than 2, an edge between the two robots is missing before the move and prevents the meeting, or the two robots move in a way that prevents the meeting by indistinguishability between G i and G i+1 ). Note that, by construction, G i+1 has at most one edge missing at each instant time and hence belongs to AC.

Defining t i+1 = t i + 1, we succeed to construct G i+1 with the desired properties. Note that t i and G 0 trivially satisfy all our assumptions. In other words, (G m ) m∈N is well-defined.

We can then define the evolving graph G ω such that G ω and G 0 have the same footprint, and such that for all i ∈ N, G ω shares a common prefix with G i until time t i . As the sequence (t m ) m∈N is increasing by construction, this implies that the sequence (G m ) m∈N converges to G ω . Applying the theorem of Braud-Santoni et al. [START_REF] Braud-Santoni | The next 700 impossibility results in timevarying graphs[END_REF], we obtain that, until time t i , the execution of A in G ω is identical to the one in G i . This implies that, executing A in G ω (whose footprint is a ring of size 4 or more), r 1 and r 2 are always on distinct nodes, contradicting the liveness of G E and proving the result.

It is possible to derive some other impossibility results from Theorem 1. Indeed, the inclusion AC ⊂ COT allows us to state that G E is impossible under COT as well.

Corollary 1. There exists no deterministic algorithm that satisfies G E in rings of COT with size 4 or more for 4 robots or more.

From the very definitions of G and G E , it is straightforward to see that the impossibility of G E under a given class implies the one of G under the same class.

Corollary 2. There exists no deterministic algorithm that satisfies G in rings of COT or AC with size 4 or more for 4 robots or more.

Finally, impossibility results for bounded variants of the gathering problem (i.e. the impossibility of G under RE and of G W under COT and RE) are obtained as follows. The definition of COT and RE does not exclude the ability for all edges of the graph to be missing initially and for any arbitrary long time, hence preventing the gathering of robots for any arbitrary long time if they are initially scattered. This observation is sufficient to prove a contradiction with the existence of an algorithm solving G or G W in these classes. Corollary 3. There exists no deterministic algorithm that satisfies G or G W in rings of COT or RE with size 4 or more for 4 robots or more.

Gracefully Degrading Gathering

This section presents GDG, our gracefully degrading gathering algorithm, that aims to solve different variants of the gathering problem under various dynamics (refer to Table 1).

In Subsection 4.1, we informally describe our algorithm clarifying which variant of gathering is satisfied within which class of evolving graphs. Next, Subsection 4.2 presents formally the algorithm.

Overwiew

Our algorithm has to overcome various difficulties. First, robots are evolving in an environment in which no node can be distinguished. So, the trivial algorithm in which the robots meet on a particular node is impossible. Moreover, since the footprint of the graph is a ring, (at most) one of the n edges may be an eventual missing edge. This is typically the case of classes COT and AC. In that case, no robot is able to distinguish an eventual missing edge from a missing edge that will appear later in the execution. In particular, a robot stuck by a missing edge does not know whether it can wait for the missing edge to appear again or not. Finally, despite the fact that no robot is aware of which class of dynamic graphs robots are evolving in, the algorithm is required to meet at least the specification of the gathering according to the class of dynamic graphs in which it is executed or a better specification than this one. The overall scheme of the algorithm consists in first detecting r min , the robot having the minimum identifier so that the R robots eventually gather on its node (i.e., satisfying specification G E ). Of course, depending on the particular evolving graph in which our algorithm is executed, G E may not achieved. In the weakest class (class COT ) and the "worst" possible evolving graph, one can expect specification G EW only, i.e., at least R -1 robots gathered.

The algorithm proceeds in four successive phases: M, K, W, and T. Actually, again depending on the class of graphs and the evolving graph in which our algorithm is executed, we will see that the four phases are not necessarily all executed since the execution can be stopped prematurely, especially in case where G E (or G) is achieved. By contrast, they can also never be completed in some weak settings (namely AC or COT ), solving G EW (or G W ) only.

Phase M. This phase leads each robot to know whether it possesses the minimum identifier. Initially every robot r considers the right direction. Then r always moves to the right until it moves 4 * n * id r steps on the right, where id r is the identifier of r and n, the size of the ring. The first robot that succeeds to do so is necessarily r min . Depending on the class of graph, one eventual missing edge may exist, preventing r min to move on the right direction during 4 * n * id rmin steps.

However, in that case at least R -1 robots succeed to be located on a same node, but not necessarily the node where r min is located. Note that the weak form of gathering (G EW ) could be solved in that case. However, the R -1 robots gathered cannot stop their execution. Indeed, our algorithm aims at gathering the robots on the node occupied by r min . However, r min may not be part of the R -1 robots that gathered. Further, it is possible for R -1 robots to gather (without r min ) even when r min succeeds in moving 4 * n * id rmin steps to the right (i.e. even when r min stops to move because it completed Phase M). In that case, if the R -1 robots that gathered stop their execution, G E cannot be solved in RE, BRE and ST rings, as GDG should do. Note that, it is also possible for r min to be part of the R -1 robots that gathered.

Recall that robots can communicate when they are both located in the same node. So, the R -1 robots may be aware of the identifier of the robot with the minimum identifier among them. Since it can or cannot be the actual r min , let us call this robot potentialM in. Then, driven by potentialM in, a search phase starts during which the R -1 robots try to visit all the nodes of the ring infinitely often in both directions by subtle round trips. Doing so, r min eventually knows that it possesses the actual minimum identifier.

Phase K. The goal of the second phase consists in spreading the identifier of r min among the other robots. The basic idea is that during this phase, r min stops moving and waits until R -3 other robots join it on its node so that its identifier is known by at least R -3 other robots. The obvious question arises:"Why waiting for R -3 extra robots only?". A basic idea to gather could be that once r min is aware that it possesses the minimum identifier, it can just stop to move and just wait for the other robots to eventually reach its location, just by moving toward the right direction. Actually, depending on the particular evolving graph considered one missing edge e may eventually appear, preventing robots from reaching r min by moving toward the same direction only. That is why the gathering of the R -2 robots is eventually achieved by the same search phase as in Phase M. However, by doing this, it is possible to have 2 robots stuck on each extremity of e. Further, these two robots cannot change the directions they consider since a robot is not able to distinguish an eventual missing edge from a missing edge that will appear again later. This is why during Phase K, r min stops to move until R -3 other robots join it to form a tower of R -2 robots. In this way these R -2 robots start the third phase simultaneously.

Phase W. The third phase is a walk made by the tower of R -2 robots. The R -2 robots are split into two distinct groups, Head and Tail. Head is the unique robot with the maximum identifier of the tower. Tail, composed of R -3 robots, is made of the other robots of the tower, led by r min . Both move alternatively in the right direction during n steps such that between two movements of a given group the two groups are again located on a same node. This movement permits to prevent the two robots that do not belong to any of these two groups to be both stuck on different extremities of an eventual missing edge (if any) once this walk is finished. Since there exists at most one eventual missing edge, we are sure that if the robots that have executed the walk stop moving forever, then at least one robot can join them during the next and last phase.

As noted, it can exist an eventual missing edge, therefore, Head and Tail may not complete Phase W. Indeed, one of the two situations below may occur: (i) Head and Tail together form a tower of R -2 robots but an eventual missing edge on their right prevents them to complete Phase W; (ii) Head and Tail are located on neighboring node and the edge between them is an eventual missing edge that prevents Head and Tail to continue to move alternatively.

Call u the node where Tail is stuck on an eventual missing edge. In the two situations described even if Phase W is not complete by both Head and Tail, either G E or G EW is solved. Indeed, in the first situation, necessarily at least one robot r succeeds to join u. In fact, either r considers the good direction to reach u or it meets a robot on the other extremity of the eventual missing edge that makes it considers the good direction to reach u. In the second situation, necessarily at least two robots r and r succeed to join u. This is done either because r and r consider the good direction to reach u or because they reach the node where Head is located without Tail making them consider the good direction to reach u.

Once a tower of R -1 robots including r min is formed, G EW is solved. Then, the latter robot tries to reach the tower to eventually solve G E in favorable cases.

Phase T. The last phase starts once the robots of Head have completed Phase W. If it exists a time at which the robots of Tail complete Phase W, then Head and Tail form a tower of R -2 robots and stop moving. As explained in the previous phase, Phase W ensures that at least one extra robot eventually joins the node where Head and Tail are located to form a tower of R -1 robots. Once a tower of R -1 robots including r min is formed, G EW is solved. Then, the latter robot tries to reach the tower to eventually solve G E in favorable cases. In the case the robots of Tail never complete the phase W, then this implies that Head and Tail are located on neighboring node and that the edge between them is an eventual missing edge. As described in Phase W either G EW or G E is solved.

Algorithm

Before presenting formally our algorithm, we first describe the set of variables of each robot. We recall that each robot r knows R, n and id r as constants.

In addition to the variable dir r (initialized to right), each robot r possesses seven variables described below. Variable state r allows the robot r to know which phase of the algorithm it is performing and (partially) indicates which movement the robot has to execute. The possible values for this variable are righter, dumb-Searcher, awareSearcher, potentialM in, waitingW alker, minW aitingW alker, headW alker, tailW alker, minT ailW alker and lef tW alker. Initially, state r is equal to righter. Initialized with 0, rightSteps r counts the number of steps done by r in the right direction when state r ∈ {righter, potentialM in}. The next variable is idP otentialM in r . Initially equals to -1, idP otentialM in r contains the identifier of the robot that possibly possesses the minimum identifier (a positive integer) of the system. This variable is especially set when R -1 righter are located on a same node. In this case, the variable idP otentialM in r of each robot r that is involved in the tower of R -1 robots is set to the value of the minimum identifier possessed by these robots. The variable idM in r indicates the identifier of the robot that possesses the actual minimum identifier among all the robots of the system. This variable is initially set to -1. Let walkerM ate r be the set of all the identifiers of the R -2 robots that initiate the Phase W. Initially this variable is set to ∅. The counter walkSteps r , initially 0, maintains the number of steps done in the right direction while r performs the Phase W. Finally, the variable idHeadW alker r contains the identifier of the robot that plays the part of Head during the Phase W.

Moreover, we assume the existence of a specific instruction: terminate. By executing this instruction, a To ease the writing of our algorithm, we define a set of predicates (presented in Algorithm 1) and functions (presented in Algorithm 2), that are used in our gracefully degrading algorithm GDG. Recall that, during the Compute phase, only the first rule whose guard is true in the view of an enabled robot is executed.

Proofs of correctness of GDG

In this section, we first prove, in Subsection 5.1, that GDG solves G EW in COT rings. Then, in Subsection 5.2, we consider AC, RE, BRE and ST rings and for each of these classes of dynamic rings, we give the problem GDG solves in it.

We want to prove that, while executing GDG, at least R -1 robots terminate their execution on the same node. Therefore, in the proofs of correctness, we show that our algorithm forces the robots to execute either Rule Term 1 or Rule Term 2 whatever the harsh situation. Hence, the proofs are given in the case where these rules are not executed accidentally.

In the following, for ease of reading, we abuse the various values of the variable state to qualify the robots. For instance, if the current value of variable state of a robot is righter, then we say that the robot is a righter robot. Let us call min a robot such that its variable state is equal either to minW aitingW alker or to minT ailW alker.

GDG solves G EW in COT rings

In this subsection, we prove that GDG solves G EW in COT rings. Since GDG is divided into four phases, we prove each of these phases hereafter.

Proofs of Correctness of Phase M

We recall that the goal of Phase M of our algorithm is to make the robot with the minimum identifier aware that it possesses the minimum identifier among all the robots of the system. In our algorithm a robot is aware that it possesses the minimum identifier when it is min. Therefore, in this section we have to prove that only r min can become min, and that r min effectively becomes min in finite time. We prove this respectively in Lemmas 3 and 5.

First we give two observations that help us all along the proves of each phase.

Observation 1. By the rules of GDG, a robot whose state is not either righter or potentialM in cannot become a righter or a potentialM in.

Observation 2. By the rules of GDG, a robot whose state is not righter cannot become a righter robot.

While executing GDG, once a robot knows that it possesses the minimum identifier, it remembers this information. In other words, once a robot becomes min it stays min during the rest of the execution. We prove this statement in the following lemma.

Lemma 1. min is a closed state under GDG.

Proof. A robot is a min when its state is either equal to minW aitingW alker or to minT ailW alker. A min-T ailW alker robot can only execute the rules T 3 and W 1 that do not update the variable state. A minW aiting-W alker robot can only execute the rules K 1 and K 2 that respectively makes it become a minT ailW alker and does not change its state.

In the following lemma, we prove that righter and potentialM in are robots that always consider the right direction. This lemma helps us to prove the correctness of Phase M, as well as the correctness of Phase K. Lemma 2. If, at a time t, a robot is a righter or a potentialM in, then it considers the right direction from the beginning of the execution until the Look phase of time t.

Proof. Robots that are righter robots in a configuration γ i at time i and that are still righter in the configuration γ i+1 , consider the right direction during the move Phase of time i (Rule M 8 ). Moreover, by Observation 2 and since initially all the robots are righter robots and consider the right direction, if a robot is a righter during the Look phase of a time t, this implies that it considers the right direction from the beginning of the execution until the Look phase of time t.

Similarly, robots that are potentialM in robots in a configuration γ i at time i and that are still potential-M in in the configuration γ i+1 , consider the right direction during the move Phase of time i (Rule M 8 ). The only way for a robot to become a potentialM in is to be a righter and to execute Rule M 6 . While executing Rule M 6 , a righter that becomes potentialM in does not change the direction it considers. Therefore, by Observations 1 and 2, and by the arguments of the first paragraph, this implies that if a robot is a potential-M in during the Look phase of a time t, then it considers the right direction from the beginning of the execution until the Look phase of time t. Now we prove one of the two main lemmas of this phase: we prove that only r min can be aware that it possesses the minimum identifier among all the robots of the system. Lemma 3. Only r min can become min.

Proof. Assume that there exists a robot r = r min that becomes min. Assume also that r is the first robot different from r min that becomes min. By definition of r min , id r > id rmin .

A robot that is a min is a robot such that its variable state is either equal to minW aitingW alker or to minT ailW alker. A robot becomes minT ailW alker only if it executes Rule K 1 . A robot can execute Rule K 1 only if it is a minW aitingW alker. A robot becomes minW aitingW alker only if it executes Rule M 1 . Only righter robots or potentialM in robots can execute Rule M 1 (refer to predicate P otentialM inOrRighter()).

Then by Observation 1, we conclude that each robot can execute Rule M 1 at most once. ( * )

In the following, let us consider the different conditions of the predicate M inDiscovery() of Rule M 1 that permits r to become min.

Case 1: r becomes min because the condition "state r = potentialMin ∧ ∃r ∈ NodeMate(), (state r = righter ∧ id r < id r )" is true.

The only way for a robot to have its variable state set to potentialM in is to execute Rule M 6 . This rule is executed when R -1 righter robots are on a same node. Among these R -1 righter robots, the one with the minimum identifier sets its variable state to potentialM in while the other robots set their variables state to dumbSearcher. By Observation 1, a robot that becomes a dumbSearcher robot after the execution of Rule M 6 can never become righter robot or potentialM in robot. Moreover, by Observation 2, a robot that becomes a potentialM in can never become a righter. Since R -1 righter are needed to execute Rule M 6 , this rule can be executed only once during the execution. Therefore if r is a potentialM in, it is necessarily the robot that possesses the minimum identifier among the R -1 robots that execute Rule M 6 . Moreover, if there exists a righter robot r when r is potentialM in, this implies that r has not executed Rule M 6 . Hence if id r < id r , this necessarily implies that r = r min , therefore there is a contradiction with the fact that r = r min .

Case 2: r becomes min because the condition "∃r ∈ NodeMate(), idMin r = id r " is true.

By ( * ), r is not yet min at the time of its meeting with r . A robot r can update its variable idM in with the identifier (other than its) of a robot that is not min only when it executes Rules M 5 , M 7 , M 9 or M 10 . Among these rules only the rules M 7 (in the case a righter is located with a dumbSearcher) and M 9 permit a robot to update its variable idM in with the identifier of a robot without copying the value of the variable idM in of another robot. Therefore at least one of these rules is necessarily executed at a time, since initially the variables idM in of the robots are equal to -1. To execute Rule M 7 (in the case a righter is located with a dumbSearcher) or Rule M 9 , a dumbSearcher robot must be present in the execution. Only the execution of Rule M 6 permits to have dumbSearcher robots in the execution. This rule is executed when R -1 righter robots are on a same node. The R -1 robots that execute this rule, set their variables idP otentialM in to the identifier of the robot that becomes potentialM in while executing this rule. Moreover if a robot is a dumbSearcher in a configuration γ t at time t and is still a dumbSearcher in the configuration γ t+1 then it does not update its variable idP otentialM in during time t (since it executes Rule M 11 ).

In the case Rule M 7 is executed because a righter r r is located with a dumbSearcher r d necessarily id rr > idP otentialM in r d , otherwise it is not possible for r r to execute Rule M 7 , since it would have executed Rule M 1 at the same round (since the predicate M inDiscovery() is true because (state r d ∈ {dumbSearcher, potentialM in} ∧ id rr < idP otentialM in r d )). Therefore if Rule M 7 is executed at round t because a righter r r is located with a dumbSearcher r d , this implies, by the predicate DumbSear-cherM inRevelation() of Rule M 9 , that Rule M 9 is also executed at round t. Indeed, r r executes Rule M 7 , while r d executes Rule M 9 . The reverse is also true: if a dumbSearcher r d executes Rule M 9 at round t, then necessarily a righter r r , such that id rr > idP otentialM in r d , executes Rule M 7 at round t. While executing respectively these rules the two robots update their variables idM in with the value of the variable idP otentialM in of the dumbSearcher. By using the same arguments as the one used in case 1, we know that idP otentialM in is the identifier of r min . Therefore the variables idM in are either set with the identifier of r min while Rules M 7 and M 9 are executed, or copied from another robots while Rules M 5 or M 10 are executed. However whatever the rule executed the value of idM in is set with the identifier of r min .

Case 3: r becomes min because the condition "∃r ∈ NodeMate(), (state r ∈ {dumbSearcher, potentialMin} ∧ id r < idPotentialMin r )" is true.

Only the execution of Rule M 6 permits to have dumbSearcher or potentialM in in the execution. This rule is executed when R-1 righter robots are on a same node. When executing this rule, the R-1 robots set their variables idP otentialM in to the identifier of the robot that possesses the minimum identifier among them. Moreover among the R -1 robots that execute Rule M 6 , one robot becomes potential-M in while the other become dumbSearcher. Besides if a robot is a dumbSearcher (resp. a potentialM in) in a configuration γ t at time t and is still a dumbSearcher (resp. a potentialM in) in the configuration γ t+1 then it does not update its variable idP otentialM in during time t since it executes Rule M 11 (resp. M 8 ). As Rule M 6 can only be executed once (see the arguments of case 1), if r meets a dumbSearcher or a potentialM in r , such that id r < idP otentialM in r , this necessarily implies that r is issued of the execution of Rule M 6 while r has not executed this rule, and therefore r = r min , which is a contradiction.

Case 4: r becomes min because rightSteps r = 4 * id r * n.

At the time where r becomes min, r min is either a righter robot, a potentialM in robot or min, otherwise this implies that there already exists a min (other than r min ) in the execution, which is a contradiction with the fact that r is the first robot different from r min that becomes min.

By the predicate P otentialM inOrRighter() of Rule M 1 , only righter robots or potentialM in robots can become min. By Lemma 2, if, at a time t, a robot is a righter or a potentialM in, then it considers the right direction from the beginning of the execution until the Look phase of time t. Robots that are righter robots or potentialM in robots in a configuration γ t at time t and that are either righter or potentialM in in the configuration γ t+1 increase from 1 their variables rightSteps each time an adjacent edge in the right direction to their positions is present (Rules M 6 and M 8 ). Therefore, by the predicate M inDiscovery() of Rule M 1 a robot r" moves at most during 4 * id r" * n steps in the right direction before being min.

By Lemma 1, from the time a robot becomes min, it is either a minW aitingW alker or a minT ailW alker.

Therefore it can only execute Rules Term 1 , Term 2 , K 1 , K 2 , W 1 and T 3 . This implies that once a robot is min, it considers only either the right or the ⊥ direction, and can move during at most n steps in the right direction before stopping to move definitively (by executing the following rules in the order: K 2 , K 1 , W 1 and T 3 ). Therefore by the previous paragraph, a min r" considers the right or the ⊥ direction from the beginning of the execution until the end of the execution, and can move during at most 4 * id r" * n + n steps in the right direction during the whole execution.

Because of the dynamism of the ring, by Observation 1 and since when a righter or a potentialM in robot stops to be a righter or a potentialM in robot, it stops to update the value of its variable rightSteps, we have:

∀r 1 , r 2 ∈ R 2 , state r1 , state r2 ∈ {righter, potentialM in} 2 , |rightSteps r1 -rightSteps r2 | ≤ n.
Because it takes one round for a robot to update its variable state to min, a righter or a potential-M in can be located with a robot r just the round before r becomes min. Therefore this righter or potentialM in can move again in the right direction during at most n steps without meeting the min.

We know that id rmin < id r , therefore we have 4 * id rmin * n + n + n + n < 4 * id r * n. Hence there exists a time at which r meets r min while r min is min and r is not yet min. At this time, by the rules of GDG, r stops being a righter or a potentialM in robot, and hence by Observation 1, r cannot be anymore a righter robot or a potentialM in robot and therefore it cannot become min, which leads to a contradiction.

The following lemma helps us to prove the Lemma 5. This lemma is true only if there is no min in the execution. In other words, it is true only if all the robots are executing Phase M. Lemma 4. If there is no min in the execution, if, at time t, a robot r is such that state r ∈ {dumb-Searcher, awareSearcher}, then, during the Move phase of time t -1, it does not consider the ⊥ direction.

Proof. Consider a robot r such that, at time t, state r ∈ {dumbSearcher, awareSearcher}.

While executing GDG, since initially all the robots are righter, if there is no min, only righter, potential-M in, dumbSearcher and awareSearcher robots can be present in the execution.

Consider then the two following cases.

Case 1: At time t -1, r is neither a dumbSearcher nor an awareSearcher.

Whatever the state of r at time t -1 (righter or potentialM in), to have its variable state at time t equals either to dumbSearcher or to awareSearcher, r executes at time t -1 either Rule M 5 , M 6 or M 7 .

Consider first the case where r executes Rule M 6 at time t -1. Only righter robots can execute Rule M 6 . While executing Rule M 6 , r becomes a dumbSearcher (since while executing this rule a righter can become either a dumbSearcher or a potentialM in). Moreover, while executing Rule M 6 , a righter that becomes dumbSearcher does not change the direction it considers. By Lemma 2, during the Look phase of time t -1, r considers the right direction and since r does not change its direction during the Compute phase of time t -1, this implies that the lemma is proved in this case.

Consider now the case where r executes either Rule M 5 or M 7 . While executing these rules the function Search is called. While executing the function Search, if there are multiple robots on the current node of r at time t -1, it considers either the right or the left direction. Therefore, in this case the lemma is proved.

In the case r is alone on its node at time t -1, while executing the function Search it does not change its direction. Moreover, while executing Rules M 5 or M 7 , before calling the function Search the robot calls the function BecomeAwareSearcher that sets its direction to the right direction. Therefore, in these cases, even if r is alone on its node, it considers a direction different from ⊥ during the Move phase of time t -1, hence the lemma is proved.

Case 2: At time t -1, r is a dumbSearcher or an awareSearcher.

Whatever the state of r at time t -1 (dumbSearcher or awareSearcher), to have its variable state at time t equals either to dumbSearcher or to awareSearcher, r executes at time t -1 either Rule M 9 , M 10 or M 11 . While executing these rules the function Search is called.

As highlighted in the case 1, if there are multiple robots on the current node of r at time t -1, the lemma is proved.

Moreover, while executing Rules M 9 and M 10 , before calling the function Search the robot calls the function BecomeAwareSearcher that sets its direction to the right direction. Therefore, in these cases, even if r is alone on its node, it considers a direction different from ⊥ during the Move phase of time t -1, hence the lemma is proved.

It remains the case where r executes Rule M 11 at time t -1 while it is alone on its node. In this case, while executing Rule M 11 , r does not change its direction (refer to the function Search). Since at time t -1, r is already a dumbSearcher or an awareSearcher, and since initially all the robots are righter, by recurrence on all the cases treated previously (Case 1 and 2), the direction r considers during the Move phase of time t -1 cannot be equal to ⊥.

Finally, we prove the other main lemma of this phase: we prove that r min is aware, in finite time, that it possesses the minimum identifier among all the robots of the system. Lemma 5. In finite time r min becomes min.

Proof. Assume that r min does not become min. By Lemma 3, only r min can be min. While executing GDG, since initially all the robots are righter, if there is no min, only righter, potentialM in, dumbSearcher and awareSearcher robots can be present in the execution.

Initially all the robots are righter. In the case where there is no min in the execution, by the rules of GDG, from a configuration γ t at a time t where there are only righter robots, it is not possible to have aware-Searcher in the configuration γ t+1 . A robot can become a dumbSearcher or a potentialM in only when Rule M 6 is executed. This rule is executed when R -1 righter robots are on a same node (refer to predicate AllButOneRighter()).

Let us now consider the three following cases that can occur in the execution.

Case 1: Rule M 6 is never executed.

In this case all the robots are righter robots during the whole execution, and execute therefore Rule M 8 at each instant time. While executing Rule M 8 , a robot always considers the right direction and increments its variable rightSteps by one each time there exists an adjacent right edge to its location. Since by assumption r min does not become min, then by Rule M 1 and predicate M inDiscovery(), r min cannot succeed to have its variable rightSteps equals to 4 * id rmin * n, otherwise the lemma is true. Therefore it exists a time at which r min is on a node such that its adjacent right edge is missing forever. Since it can exist at most one eventual missing edge in a COT ring, and since all the robots always move in the right direction when there is an adjacent right edge to their location (since they execute Rule M 8 ), it exists a time at which R -1 righter robots are on a same node, cases 2 and 3 are then considered.

Case 2: Rule M 6 is executed but r min is not among the R -1 righter robots that execute it.

While executing Rule M 6 , among the R -1 righter located on a same node that execute this rule, the robot with the minimum identifier r p becomes potentialM in while the other robots become dumb-Searcher, and all update their variables idP otentialM in to id rp . By definition we have id rp > id rmin . By Observation 1, a robot that becomes a dumbSearcher can never become righter robot or potential-M in robot. Moreover, by Observation 2, a robot that becomes a potentialM in can never become a righter. Since R -1 righter are needed to execute Rule M 6 , this rule can be executed only once. Note that if a robot is a dumbSearcher (resp. a potentialM in) in a configuration γ t at time t and is still a dumbSearcher (resp. a potentialM in) in the configuration γ t+1 then it does not update its variable idP otentialM in during time t since it executes Rule M 11 (resp. M 8 )

At the time of the execution of Rule M 6 , r min is a righter, since it is not among the robots that execute this rule. After the execution of this rule r min , as a righter, cannot meet a potentialM in robot. Indeed the only way for a robot to become potentialM in is to execute Rule M 6 . Therefore only r p can be po-tentialM in, and we know that idP otentialM in rp = id rp > id rmin . Hence if r min meets a potentialM in, then by Rule M 1 and predicate M inDiscovery() the lemma is true, which is a contradiction.

Similarly, r min as a righter cannot meet a dumbSearcher r d . Indeed, only Rule M 6 permits a robot to become a dumbSearcher. Therefore, since idP otenialM in r d = id rp > id rmin , if r min meets a dumbSearcher, then by Rule M 1 and predicate M inDiscovery() the lemma is true, which is a contradiction.

Moreover it cannot exist awareSearcher in this execution. Indeed, as said previously, from a configuration γ t at a time t where there are only righter robots, it is not possible to have awareSearcher in the configuration γ t+1 . Therefore awareSearcher can be present in the execution only after the execution of Rule M 6 . In the case where there is not yet awareSearcher, a robot can become an awareSearcher only if a righter meets a dumbSearcher (Rules M 9 and M 7 ). However after the execution of Rule M 6 , only r min is a righter, and as explained in the previous paragraph, if r min as a righter meets a dumbSearcher there is a contradiction.

Since there is no awareSearcher and since r min as a righter cannot meet neither potentialM in nor dumbSearcher, this implies that r min stays a righter during the whole execution and therefore executes Rule M 8 at each instant time. By the same arguments as the one used in case 1, necessarily it exists a time at which r min is on node such that its adjacent right edge is missing forever, otherwise the lemma is true. However since there is no min is the execution, and there is no awareSearcher, r p stays a potential-M in and executes Rule M 8 at each instant time, therefore it always considers the right direction. Since it can only exist one eventual missing edge and since this edge is the adjacent right edge to the position of r min , all the other edges are infinitely often present. Therefore, in finite time, the potentialM in is located on the same node as r min , which is a contradiction.

Case 3: Rule M 6 is executed and r min is among the R -1 righter robots that execute it.

We use the same arguments as the one used in case 2. Therefore we know that while executing Rule M 6 , r min becomes potentialM in, since r min possesses the minimum identifier among all the robots of the system.

Moreover, since r min does not become min, as a potentialM in, it cannot meet a righter robot otherwise by Rule M 1 and predicate M inDiscovery() the lemma is true.

Similarly, r min as a potentialM in cannot meet awareSearcher. Indeed in the case there is not yet aware-Searcher, a robot can become an awareSearcher only if a righter meets a dumbSearcher (Rules M 9 and M 7 ). While executing these rules a robot that becomes an awareSearcher sets its variable idM in to the identifier of the variable potentialM in of the dumbSearcher, which is in this case id rmin . An aware-Searcher never updates the value of its variable idM in. Once there is at least one awareSearcher in the execution, it is possible to have other robots that become awareSearcher thanks to the execution of Rule M 10 . However while executing this rule, a robot that becomes awareSearcher copies the value of the variable idM in of the awareSearcher it is located with. Therefore if r min , as a potentialM in, meets an awareSearcher, by Rule M 1 and predicate M inDiscovery(), the lemma is true, which is a contradiction.

Therefore, as a potentialM in, r min executes Rule M 8 at each instant time. By the same arguments as the one used in case 1, necessarily it exists a time at which r min is on node such that its adjacent right edge is missing forever, otherwise the lemma is true.

By Observation 1, dumbSearcher and awareSearcher robots cannot become righter or potentialM in.

As explained, if there is no meeting between a dumbSearcher robot and a righter robot, it cannot exist awareSearcher robots in the execution. As seen previously, no righter robot can meet r min . At the time where Rule M 6 is executed there is a righter robot r in the execution. In the case r never meets a dumb-Searcher robot, it executes Rule M 8 at each instant time. Hence, using the arguments as the one used in case 2, in finite time, r can be located on the same node as r min , which is a contradiction. This implies that there exists a time at which r, as a righter robot, meets at least a dumbSearcher robot r . In this case r executes Rule M 7 (refer to the predicate RighterW ithSearcher()) and all the dumbSearcher robots located with r including r execute Rule M 9 (by the predicate DumbSearcherM inRevelation() and since id r > id rmin ). Hence r and all the dumbSearcher robots located with r become awareSearcher robots and execute the function Search. When a robot executes the function Search while there are multiple robots on its node, if it possesses the maximum identifier among the robots of its node, it considers the left direction, otherwise it considers the right direction. Therefore, once M 7 and M 9 are executed, there are at least two awareSearcher considering two opposite directions. Moreover once M 7 and M 9 are executed, except r min there are only dumbSearcher and awareSearcher robots in the execution. When a dumbSearcher robot meets an awareSearcher robot, it executes Rule M 10 and therefore becomes awareSearcher robot and executes the function Search. An awareSearcher executes Rule M 11 at each instant time, therefore it calls the function Search at each instant time. While executing the function Search, if an awareSearcher robot is alone on its node, it considers the last direction it considers (this direction cannot be equal to ⊥ by Lemma 4). All this implies that in finite time an awareSearcher robot is located on the same node as r min . Therefore by Rule M 1 and predicate M inDiscovery(), r min becomes min.

By Lemmas 3 and 5, we can deduce the following corollary which proves the correctness of Phase M.

Corollary 4. Only r min becomes min in finite time.

Proofs of Correctness of Phase K

Once r min completes Phase M, it stops to move and waits for the completion of Phase K. We recall that, during Phase K of GDG, R -3 robots must join r min on the node where it is waiting. More precisely, while executing GDG, Phase K is achieved when R -3 waitingW alker robots are located on the node where r min , as min, is waiting. In the previous subsection, we prove that, in finite time, only r min becomes min (Corollary 4) and that once r min is min it stays min for the rest of the execution (Lemma 1). Note that, by the rules of GDG, the min is necessarily a minW aitingW alker robot before being a minT ailW alker (since only a minW aitingW alker can become a minT ailW alker while executing Rule K 1 ). Moreover, by Rule K 2 , r min , as a minW aitingW alker, does not move until R -3 waitingW alker robots are on its node. Therefore, as minW aitingW alker, r min is, as expected, always on the same node. Let u be the node on which r min , as a minW aitingW alker, is located. Let t min be the time at which r min becomes a minW aitingW alker robot. In this subsection, we consider the execution from time t min .

To simplify the proofs, we introduce the notion of towerM in as follows.

Definition 1 (towerM in). A towerM in corresponds to a configuration of the execution in which R-3 waiting-W alker robots are located on the same node as the minW aitingW alker.

To prove the correctness of Phase K, we hence have to prove that, in finite time, a towerM in is formed. As noted previously, by the rules of GDG, as long as there is no towerM in, r min stays a minW aiting-W alker robot.

The following observation is useful to prove the correctness of this phase.

Observation 3. There exists no rule in GDG permitting a robot that stops being either minW aitingW alker or waitingW alker robot to be again a minW aitingW alker or waitingW alker robot.

To prove the correctness of this phase, we prove, first, that if a potentialM in is present in the execution then, in finite time, a towerM in is present in the execution, next, we prove that if there is no potentialM in in the execution then, in finite time, a towerM in is also present in the execution. We prove this respectively in Lemmas 15 and 16. To simplify the proofs of these two lemmas, we need to prove the nine following lemmas.

In the following lemma we prove that it can exist at most one towerM in in the whole execution.

Lemma 6. It can exist at most one towerM in in the whole execution.

Proof. By definition a towerM in is composed of one minW aitingW alker and R -3 waitingW alker robots. Once a towerM in is formed, the R -2 (R -2 ≥ 2) robots involved in the towerM in execute Rule K 1 .

While executing this rule the robot with the maximum identifier among the R -2 robots involved in the towerM in becomes headW alker while the minW aitingW alker becomes minT ailW alker and the other robots involved in the towerM in become tailW alker.

Then by Observation 3 and since by Corollary 4 only r min can be minW aitingW alker, the lemma is proved.

In the following lemma, we prove that all the waitingW alker as well as the minW aitingW alker are located on node u and do not move. This is important to prove that, in finite time, a towerM in is formed. Lemma 7. All waitingW alker robots are located on the same node as r min when state rmin = minW aiting-W alker and neither the waitingW alker robots nor r min , as a minW aitingW alker, move.

Proof. By the rules of GDG, as long as there is no towerM in, r min is minW aitingW alker. While r min is the minW aitingW alker, it executes Rule K 2 at each instant time. While executing this rule, r min considers the ⊥ direction and therefore does not move.

Only Rule K 3 permits a robot r to become a waitingW alker robot. For this rule to be executed r must be located with a minW aitingW alker (refer to predicate P otentialM inOrSearcherW ithM in()). By Corollary 4, only r min can be minW aitingW alker. While executing Rule K 3 , r considers the ⊥ direction and therefore at the time of the execution of this rule, r does not move and is on the node where r min , as a minW aitingW alker, is located.

While r is a waitingW alker robot, as long as there is no towerM in in the execution, it executes Rule K 2 at each instant time. Therefore r does not move. As noted previously, the location where r stops moving is the location where r min , as the minW aitingW alker, is located.

Once a towerM in is present in the execution the waitingW alker robots and the minW aitingW alker composing this towerM in execute Rule K 1 . While executing this rule the robots do not change the direction they consider and stop being waitingW alker/minW aitingW alker robots. Therefore, by Observation 3 and since by Corollary 4 only r min can be minW aitingW alker, all waitingW alker robots are located on the same node as r min when state rmin = minW aitingW alker and neither the waitingW alker robots nor r min , as a minW aitingW alker, move. Now we prove a property on potentialM in. Lemma 8. It can exist at most one potentialM in robot in the whole execution.

Proof. Only the execution of Rule M 6 permits a robot to become a potentialM in robot. Rule M 6 is executed when R -1 righter robots are located on a same node. When these R -1 righter robots execute Rule M 6 , one becomes a potentialM in, and the others become dumbSearcher. Therefore, by Observations 1 and 2 this rule can be executed only once. Moreover, by the rules of GDG, once a potentialM in stops to be a potentialM in, it cannot be again a potentialM in. Hence the lemma is proved.

The following lemma demonstrates a property on min. Lemma 9. Before being min, r min is either a righter robot or a potentialM in robot.

Proof. A robot that is a min is a robot such that its variable state is either equal to minW aitingW alker or to minT ailW alker. The only way to be a minT ailW alker robot is to be a minW aitingW alker robot and to execute Rule K 1 . The only way to be a minW aitingW alker is to execute Rule M 1 . Only righter robots or potentialM in robots can execute Rule M 1 (refer to predicate P otentialM inOrRighter()).

The three following lemmas give properties on the execution, when r min is min. Indeed, they indicate the presence or absence of righter/potentialM in in the execution while r min is min.

Lemma 10. In the suffix of the execution starting from the time where r min is min, it is not possible to have a potentialM in robot and a righter robot present at the same time.

Proof. By Lemma 9, r min is either a righter or a potentialM in before being min. In the case where r min is a potentialM in before being min, then by Lemma 8, it cannot exist a potentialM in in the execution after r min becomes min. Therefore the lemma is proved in this case.

Consider now the case where r min is a righter before being min. For a robot to become a potential-M in Rule M 6 must be executed. This rule is executed when R -1 righter are located on a same node. While executing Rule M 6 , among the R -1 righter located on a same node, the one with the minimum identifier becomes potentialM in while the others become dumbSearcher. By Observation 2, r min cannot be among the R -1 righter that execute Rule M 6 , otherwise it cannot be a righter before being min. Similarly thanks to Observation 2, the R -1 robots that execute Rule M 6 , cannot be righter anymore after the execution of this rule. therefore, it is not possible to have a potentialM in and a righter in the execution once r min is min. Lemma 11. If there exists a time t at which a righter, a robot r (r = r min ) such that state r = righter and r min , as min, are present in the execution, then there is no more potentialM in in the suffix of the execution starting from t.

Proof. By Lemma 10, since there is a righter at time t, there is no potentialM in in the execution at time t.

Since at time t, r min and r are not righter and can never be righter anymore (refer to Observation 2), it is not possible to have R -1 righter located on a same node after time t. However, in order to have a potentialM in in the execution, Rule M 6 must be executed. This rule is executed only if R -1 righter are located on a same node. Therefore there is no potentialM in in the execution after time t. Lemma 12. If there is a potentialM in at a time t, and if before being min, r min is a righter, then there is no more righter in the suffix of the execution starting from time t = max{t, t min }.

Proof. Assume that before being min, r min is a righter. Moreover assume that there is a potentialM in in the execution at time t.

( * ) For a robot to become a potentialM in Rule M 6 must be executed. This rule is executed when R -1 righter are located on a same node. While executing Rule M 6 , among the R -1 righter located on a same node, the one with the minimum identifier becomes potentialM in while the others become dumbSearcher. By Observation 2 none of these R -1 robots can become righter anymore after time t.

Consider then the two following cases.

Case 1: t > t min .

By Observation 2, r min cannot be a righter after time t min . Therefore r min is not among the R -1 robots that execute Rule M 6 , and hence, by ( * ), after time t, there is no more righter in the execution.

Case 2: t ≤ t min .

By ( * ), r min cannot be among the R -1 righter that execute Rule M 6 , otherwise it cannot be a righter before being min. Therefore, by ( * ) and since after time t min , by Observation 2, r min cannot be a righter anymore, there is no more righter in the execution after time t min .

The following lemma is an extension of Lemma 4. While Lemma 4 is true only when all the robots are executing Phase M, the following lemma is true whether the robots are executing Phase M or Phase K. Lemma 13. If there is no towerM in in the execution, if, at time t, a robot r is such that state r ∈ {potential-M in, dumbSearcher, awareSearcher}, then, during the Move phase of time t -1, it does not consider the ⊥ direction.

Proof. Consider a robot r such that at time t, state r = potentialM in. By Lemma 2, r considers the right direction during the Move phase of time t -1. Hence the lemma is proved in this case.

Consider now a robot r such that, at time t, state r ∈ {dumbSearcher, awareSearcher}. Since there is no towerM in in the execution, by the rules of GDG and knowing that initially all the robots are righter, there are only righter, potentialM in, dumbSearcher, awareSearcher, waitingW alker and minW aitingW alker robots in the execution. Note that there is no rule in GDG permitting a waitingW alker or a minW aitingW alker to become either a dumbSearcher or an awareSearcher.

Consider then the two following cases.

Case 1: At time t -1, r is neither a dumbSearcher nor an awareSearcher.

Whatever the state of r at time t -1 (righter or potentialM in), to have its variable state at time t equals either to dumbSearcher or to awareSearcher, r executes at time t -1 either Rule K 4 , M 5 , M 6 or M 7 .

When a robot executes Rule K 4 , it calls the function BecomeAwareSearcher. When a robot executes the function BecomeAwareSearcher, it sets its direction to the right direction, therefore the lemma is also true in this case.

Then, we can use the arguments of the proof of Lemma 4 to prove that the current lemma is true for the remaining cases. Indeed, even if in Lemma 4 the context is such that there is no min in the execution, the arguments used in its proof are still true in the context of the current lemma.

Case 2: At time t -1, r is a dumbSearcher or an awareSearcher.

Whatever the state of r at time t -1 (dumbSearcher or awareSearcher), to have its variable state at time t equals either to dumbSearcher or to awareSearcher, r executes at time t -1 either Rule M 9 , M 10 or M 11 . Similarly as for the case 1, we can use the arguments of the proof of Lemma 4 to prove that the current lemma is true in these cases.

The following lemma proves that in the case where there are at least 3 robots in the execution such that they are either potentialM in, dumbSearcher or awareSearcher, then, in finite time, at least one of this kind of robots is located on node u. A potentialM in, a dumbSearcher or an awareSearcher located with the minW aitingW alker becomes a waitingW alker (Rule K 3 ). Therefore, this lemma permits to prove that in the case where there are at least 3 robots in the execution (after time t min ) such that they are either potentialM in, dumbSearcher or awareSearcher, then, in finite time, a supplementary waitingW alker is located on node u.

To prove the following lemma, we need to introduce a new notion. We call Seg(u, v) the set of nodes (of the footprint of the dynamic ring) between node u not included and v not included considering the right direction. Lemma 14. If there is no towerM in in the execution but there exists at a time t at least 3 robots such that they are either potentialM in, dumbSearcher or awareSearcher, then it exists a time t ≥ t at which at least a potentialM in, a dumbSearcher or an awareSearcher, reaches the node u.

Proof. Assume that there is no towerM in in the execution. By the rules of GDG and knowing that initially all the robots are righter, this implies that there are only righter, potentialM in, dumbSearcher, awareSearcher, waitingW alker and minW aitingW alker robots in the execution. Since there is no towerM in, r min is minW aitingW alker and is located on node u. By Lemma 7, we know that all the waitingW alker robots (if any) are on node u and r min as well as the waitingW alker robots do not move. This implies that among the robots that are not on node u there are only righter, potentialM in, dumbSearcher and awareSearcher.

Assume by contradiction that at a time t, there are at least 3 robots such that they are either potentialM in, dumbSearcher or awareSearcher and such that for all time t ≥ t none of these kinds of robots succeed to reach the node u at time t . We consider the execution from time t.

Consider a robot r such that at time t, state r ∈ {potentialM in, dumbSearcher, awareSearcher}.

(i) If r is an awareSearcher, since it cannot reach u, it executes Rule M 11 , and hence it executes the function Search. The variable state of r is not updated while r executes this function, therefore r is an awareSearcher and executes Rule M 11 and the function Search at each instant time from time t. Thus by Lemma 13, r always considers a direction different from ⊥ after time t included.

(ii) If r is a dumbSearcher, since it cannot reach u, it can execute either Rule M 10 (if it is on the same node as an awareSearcher) and hence becomes an awareSearcher robot and executes the function Search, Rule M 9 (if it is on the same node as a righter) and hence becomes an awareSearcher and executes the function Search, or Rule M 11 and hence stays a dumbSearcher and executes the function Search. By Lemma 13 and by (i), r always considers a direction different from ⊥ after time t included.

(iii) If r is a potentialM in, by Lemma 10, there is no righter in the execution at time t and therefore by Observation 2 there is no righter in the execution after time t included. Therefore, since r cannot reach u, it can execute either Rule M 5 (if it is on the same node as an awareSearcher) and hence becomes an aware-Searcher and executes the function Search, or Rule M 8 and hence stays a potentialM in and considers the right direction. Therefore by Lemma 13 and by (i), r always considers a direction different from ⊥ after time t included.

(iv) If there is a righter robot in the execution after time t, then by Lemma 11, there is no potential-M in robot in the execution after time t included. If a righter robot is on the same node as a dumbSearcher or as an awareSearcher, it executes Rule M 7 and hence becomes an awareSearcher and executes the function Search.

(v) While executing the function Search if a robot is isolated it considers the last direction it considered. While executing the function Search if a robot is not isolated, if it possesses the maximum identifier among all the robots of its current location it considers the left direction otherwise it considers the right direction.

(vi) Note that if there is a potentialM in while r min is minW aitingW alker, then it possesses the minimum identifier among all the robots not located on node u. Indeed, only Rule M 6 permits a robot to become a potentialM in. For this rule to be executed, R -1 righter robots must be located on a same node. While executing this rule the robot with the minimum identifier among the R -1 robots located on a same node becomes potentialM in. Since, by Lemma 8, there is only one potentialM in in the whole execution and since by definition r min possesses the minimum identifier among all the robots of the system, r min does not execute Rule M 6 . Therefore, while r min is minW aitingW alker, the potentialM in possesses the minimum identifier among all the robots not located on node u. Thus, when a potentialM in executes Rule M 8 and hence considers the right direction it possesses the same behavior as if it was executing the function Search.

Case 1: There is no eventual missing edge.

Call d the direction of r during the Look phase of time t, and let v be the node where r is located during the Look phase of time t. Call w the adjacent node of v in the direction d. Call e the edge between v and w. As proved in cases (i), (ii) and (iii), d is either equal to right or lef t.

We want to prove that it exists a time t (t ≥ t) such that a robot r (it is possible to have r = r) with state r ∈ {potentialM in, dumbSearcher, awareSearcher} considers the direction d and is located on w during the Look phase of time t . Call t" (t" ≥ t) the first time after time t included where there is an adjacent edge to v. If during the Move phase of time t", r does not consider the direction d, by (i) -(vi) this necessarily implies that when r executes the function Search (or a function that behaves like the function Search) there is at least another robot on its node. Moreover by (i) -(vi) the other robot(s) with r also executes the function Search (or a function that behaves like the function Search) and is or becomes potentialM in, dumb-Searcher or awareSearcher. Therefore, since all the robots possess distinct identifiers and by (v), during the Move phase of time t", a robot among {potentialM in, dumbSearcher, awareSearcher} on node v considers the direction d.

Since all the edges are infinitely often present we can repeat these arguments on each instant time until the time t e where e is present. At time t e a robot (either potentialM in, dumbSearcher, awareSearcher) considers the direction d and hence crosses e. Since the direction considered by a robot can be updated only during Compute phases, we succeed to prove that t exists.

Applying these arguments recurrently we succeed to prove that in finite time a robot r" such that state r" ∈ {potentialM in, dumbSearcher, awareSearcher} is on node u.

Case 2: There is an eventual missing edge.

Call e the eventual missing edge. Consider the execution after the time greater or equal to t where e is missing forever. Call v the node such that its adjacent right edge is e. Call w the adjacent right node of v.

At least two robots that are either potentialM in, dumbSearcher or awareSearcher are either on nodes in Seg(u, v) ∪ {v} or on nodes in Seg(w, u) ∪ {w}.

Assume that there are at least two robots that are either potentialM in, dumbSearcher or awareSearcher which are on nodes in Seg(u, v) ∪ {v}. The reasoning when there are at least two robots that are either potentialM in, dumbSearcher or awareSearcher which are on nodes in Seg(w, u) ∪ {w} is similar.

The edge e is an eventual missing edge. It can exist only one eventual missing edge in COT ring. Therefore all the edges between the nodes in {u} ∪ Seg(u, v) ∪ {v} are infinitely often present. Thus, if there exists a robot (either potentialM in, dumbSearcher or awareSearcher) that considers the left direction then we can apply the arguments of case 1 to prove that in finite time a robot r", such that state r" ∈ {potential-M in, dumbSearcher, awareSearcher}, is on node u.

Therefore consider that all the robots, that are either potentialM in, dumbSearcher or awareSearcher and that are located on nodes in Seg(u, v) ∪ {v}, consider the right direction. In this case a robot either po-tentialM in, dumbSearcher or awareSearcher cannot be located on the same node as a robot either righter, potentialM in, dumbSearcher or awareSearcher, otherwise during the Move phase of the time of this meeting, by (i) -(vi), it exists a robot either potentialM in, dumbSearcher or awareSearcher that considers the left direction.

Since e is an eventual missing edge, and since there are at least two robots either potentialM in, dumb-Searcher or awareSearcher that consider the right direction, applying the arguments of case 1 on two of these robots, we succeed to prove that in finite time two of these robots are located on v. Therefore, by the previous paragraph, in finite time a robot r", such that state r" ∈ {potentialM in, dumbSearcher, aware-Searcher}, is on node u. Now, we prove one of the two main lemmas of this phase: we prove that if a potentialM in is present in the execution, then, in finite time, a towerM in is present in the execution. While proving this lemma, we also prove that, at the time when the towerM in is formed, among the two robots not involved in this towerM in, it can exit at most one righter. This information is useful to prove Phase T. Lemma 15. If there is a potentialM in in the execution, then there exists a time t at which a towerM in is present and among the robots not involved in the towerM in there is at most one righter robot at time t.

Proof. Assume that there exists a time t at which a potentialM in robot is present in the execution. Assume by contradiction that there is no towerM in in the execution. In the following, we consider the execution from time t = max{t, t min }.

Since there is no towerM in, by the rules of GDG and knowing that initially all the robots are righter, there are in the execution only righter, potentialM in, dumbSearcher, awareSearcher, waitingW alker and minW aitingW alker robots. By Lemma 7, all the waitingW alker are located on the same node as r min , when state rmin = minW aitingW alker, and both r min , as a minW aitingW alker, and the waitingW alker robots do not move. By Corollary 4, only r min can be a minW aitingW alker. We recall that r min as minW aiting-W alker is located on node u. Therefore the minW aitingW alker and all the waitingW alker (if any) are located on node u.

By Lemma 9 we know that, before being min, r min is either a righter robot or a potentialM in robot. We can then consider the two following cases.

Case 1: Before being min, r min is a righter robot. By Lemma 12, at time t there are only potentialM in, dumbSearcher, awareSearcher, waitingW alker and minW aitingW alker robots in the execution. Moreover, in this case, all the robots that are not on node u are necessarily either potentialM in, dumbSearcher or awareSearcher.

When a potentialM in, a dumbSearcher or an awareSearcher robot meets the minW aitingW alker, it executes Rule K 3 , hence it becomes a waitingW alker and stops to move.

Then each time there are at least 3 robots in the execution such that they are either potentialM in, dumb-Searcher and/or awareSearcher, using Lemma 14, we succeed to prove that at least one potentialM in, dumbSearcher or awareSearcher succeeds to join the node u and therefore becomes a waitingW alker. Therefore, by Lemma 7, a towerM in is formed in finite time.

Case 2: Before being min, r min is a potentialMin.

For a robot to become a potentialM in, Rule M 6 must be executed. This rule is executed when R -1 righter are located on a same node. While executing this rule, among the R -1 righter located on a same node, one becomes potentialM in while the other become dumbSearcher. By Observation 2, none of these R -1 robots can become righter anymore. Therefore, by Lemma 8, once r min is min, there are only dumbSearcher, awareSearcher, waitingW alker, minW aitingW alker robots and at most one righter robot in the execution. Moreover, in this case, among the robots that are not on node u, there are only dumbSearcher and awareSearcher and at most one righter. By the rules of GDG, as long as a dumbSearcher or an awareSearcher is not on node u, its variable state stays in {dumbSearcher, aware-Searcher}.

Once r min is min, if there exists a time at which there is no more righter robot in the execution, then, using the arguments of case 1, we succeed to prove that a towerM in is formed in finite time. Therefore assume that there is always a righter robot r in the execution.

When a dumbSearcher or an awareSearcher robot is located on the same node as the minW aiting-W alker, it executes Rule K 3 , hence it becomes a waitingW alker and stops to move. Then, using multiple times Lemma 14 and Lemma 7, we know that in finite time there are in the execution only one righter and only 2 robots r and r" such that state r , state r" ∈ {awareSearcher, dumbSearcher} 2 (all the other robots are minW aitingW alker and waitingW alker robots and are located on node u). Note that r (resp. r") cannot be located on node u, otherwise, by Rule K 3 , a towerM in is formed. Therefore, r and r" always have their variable state in {dumbSearcher, awareSearcher}.

When a righter robot is located on the same node as an awareSearcher or as a dumbSearcher, it executes Rule M 7 and becomes an awareSearcher. Similarly, if a righter is on the same node as a min-W aitingW alker while the adjacent right edge to its position is present, then the righter robot executes Rule K 4 and becomes an awareSearcher. Therefore, as highlighted previously, these situations cannot happen, otherwise a towerM in is formed in finite time. This implies that, as long as the robot r is not on node u, it must be isolated. Since r and r" cannot be located on node u, if r succeeds to join the node u in the case there is no present adjacent right edge to u, then r executes Rule M 8 and therefore stays a righter and considers the right direction. Therefore, since an isolated righter robot always executes Rule M 8 , hence always considers the right direction, this implies that either r is on a node v (v = u) such that the adjacent right edge of v is an eventual missing edge at least from the time where r is on node v (case 2.1) or r succeeds to reach u but the adjacent right edge of u is an eventual missing edge at least from the time where r is on node u (case 2.2).

( * ) When an awareSearcher or a dumbSearcher is isolated it executes Rule M 11 , hence executes the function Search, therefore it considers the last direction it considered. By Lemma 13, this direction cannot be equal to ⊥.

( * * ) Since only r and r" have their variable state in {dumbSearcher, awareSearcher} 2 , and since r and r" cannot be located on node u and cannot be located with r, if a dumbSearcher is located on the same node as an awareSearcher or if an awareSearcher (resp. a dumbSearcher) is located on the same node as another awareSearcher (resp. dumbSearcher), necessarily this means that r and r" are located on a same node, and there is no other robot on the same node as them. When a dumbSearcher is on the same node as an awareSearcher it executes Rule M 10 , hence it becomes an awareSearcher and executes the function Search. When an awareSearcher is on the same node as a dumbSearcher it executes Rule M 11 and hence executes the function Search. Since r and r" have distinct identifiers, when an aware-Searcher and a dumbSearcher are on a same node, they both execute the function Search, therefore one considers the right direction, while the other one considers the left direction. Similarly, if two aware-Searcher (resp. dumbSearcher) robots are on the same node, they both execute Rule M 11 and hence the function Search, therefore one considers the right direction, while the other one considers the left direction.

Case 2.1: Let w be the adjacent node of v in the right direction. It can exist only one eventual missing edge, which is the adjacent right edge of node v. Therefore, if a robot, in Seg(u, v) or in Seg(w, u), considers a direction d and does not change this direction, it eventually succeeds to move in this direction. Similarly, if a robot is on node w and always considers the right direction, it eventually succeeds to move in this direction ( * * * ). Firstly, assume that only r (resp. r") is on a node in Seg(u, v). By ( * ) and ( * * * ), r (resp. r") cannot consider the right direction, otherwise it reaches r in finite time. Therefore r (resp. r") considers the left direction. By ( * ) and ( * * * ), in finite time, r (resp. r") succeeds to reach u, implying that a towerM in is formed. Secondly, assume that r and r" are on nodes in Seg(u, v). By ( * ), ( * * ) and ( * * * ), they cannot meet otherwise one of them reaches u in finite time. Moreover, if they do not meet none of them can consider the left direction otherwise, by ( * ) and ( * * * ), they reach u in finite time. Therefore, they cannot meet and must consider the right direction. By ( * ) and ( * * * ), in finite time one robot among r and r" succeeds to reach r, implying that a towerM in is formed. Thirdly, assume that r and r" are on nodes in Seg(v, u). By ( * ), ( * * ) and ( * * * ), they cannot meet otherwise one of them reaches u in finite time. Moreover, if they do not meet none of them can consider the right direction otherwise, by ( * ) and ( * * * ), they reach u in finite time. Therefore, they cannot meet and must consider the left direction. However, by ( * ) and ( * * * ), since the adjacent right edge of v is missing forever, in finite time r and r" reach w, which is a contradiction with the fact that they do not meet.

Case 2.2: Applying the arguments used in the case 2.1, when r and r" are on nodes in Seg(v, u), to r and r" when there are on nodes in Seg(u, u), we succeed to prove that in finite time at least one of them reaches node u, making Rule Term 2 true, which leads to a contradiction.

Finally, we prove the other main lemma of this phase: we prove that even if there is no potentialM in in the execution, then, in finite time, a towerM in is present in the execution. While proving this lemma, we also prove that, at the time when the towerM in is formed, among the two robots not involved in this towerM in, it can exit at most one righter. This information is useful to prove Phase T. Lemma 16. If there is no potentialM in in the execution, then there exists a time t at which a towerM in is present and among the robots not involved in the towerM in there is at most one righter robot at time t.

Proof. Assume, by contradiction, that there is no towerM in in the execution. By the rules of GDG and knowing that initially all the robots are righter, this implies that there are only righter, potentialM in, dumbSearcher, awareSearcher, waitingW alker and minW aitingW alker robots in the execution.

Assume that there is no potentialM in in the execution. If there is no potentialM in in the execution, it cannot exist dumbSearcher in the execution. Indeed, the only way for a robot to become dumbSearcher is to execute Rule M 6 . However, when this rule is executed, a robot becomes potentialM in. Therefore, there are in the execution only righter, awareSearcher, waitingW alker and minW aitingW alker robots.

Before time t min , by the rules of GDG, there are only righter in the execution. Indeed, by Corollary 4, only r min can be minW aitingW alker and it becomes minW aitingW alker at time t min . Moreover, the only way for a robot to become waitingW alker is to execute Rule K 3 . In the case where there is no potentialM in in the execution, only an awareSearcher located with r min , as a minW aitingW alker, can execute this rule. Besides, the only ways for a robot to become an awareSearcher is either to be a righter and to be located with an awareSearcher (refer to Rule M 7 ), or to be a righter and to be located with r min , as a minW aitingW alker, while an adjacent right edge to their location is present (refer to Rule K 4 ). Since initially all the robots are righter, the first awareSearcher of the execution can be present only thanks to the execution of Rule K 4 .

All this implies that, even after time t min , as long as no righter robot is on node u with r min , as a min-W aitingW alker, while there is a present adjacent right edge to u, it cannot exist neither awareSearcher nor waitingW alker in the execution: there is at most one minW aitingW alker and there are at least R -1 righter. Moreover, this implies that as long as the situation described has not happened, all the righter robots only execute Rule M 8 , hence always consider the right direction.

Consider the execution just after time t min . In this context, necessarily, in finite time, there exists a righter robot r that succeeds to reach u (while r min is minW aitingW alker). Indeed, if this is not the case, this implies that there exists an eventual missing edge e. Since all the righter robots always consider the right direction and since it can exist at most one eventual missing edge, this implies that R -1 righter robots reach in finite time the same extremity of e. Thus, Rule M 6 is executed, which leads to a contradiction with the fact that there is no potentialM in in the execution.

Similarly, necessarily, in finite time, there exists an adjacent right edge to u while r is on u. Indeed, if this is not the case, this implies that the adjacent right edge of u is an eventual missing edge. Since all the righter robots always consider the right direction and since it can exist at most one eventual missing edge, in finite time all the righter succeed to be located on node u. This implies that Rule Term 1 is executed, which leads to a contradiction.

Therefore there exists a time t at which r executes Rule K 4 . At this time r becomes an awareSearcher robot and considers the right direction. We then consider the execution from time t .

( * ) From this time t , as long as there exists righter in the execution, it always exists an awareSearcher robot r considering the right direction, such that there is no righter robots on Seg(u, v), where v is the node where r is currently located. This can be proved by analyzing the movements of the different kinds of robots that we describe in (i) -(vii).

(i) By Lemma 7, all the minW aitingW alker and waitingW alker (if any) are on a same node (which is the node u) and do not move.

(ii) If an awareSearcher is located on node u, therefore if it is located with r min , as a minW aitingW alker, it executes Rule K 3 and becomes a waitingW alker robot.

(iii) If an awareSearcher is on a node different from the node u, the only rule it can execute is Rule M 11 , in which the function Search is called. While executing this function, an isolated awareSearcher considers the direction it considers during its last Move phase. By Lemma 13, this direction cannot be ⊥.

(iv) If a righter robot is located only with other righter robots or if it is located on node u, therefore if it is located with r min , as a minW aitingW alker, such that there is no adjacent right edge to u, it executes Rule M 8 , hence it stays a righter and considers the right direction.

(v) If a righter robot is with r min , as a minW aitingW alker, such that there is an adjacent right edge to u, then it executes Rule K 4 and hence becomes an awareSearcher.

(vi) If a righter robot is on a node different from node u with an awareSearcher, it executes Rule M 7 and therefore becomes awareSearcher and executes the function Search.

(vii) Note that by the movements described in (i) to (vi), if a robot executes the function Search, then all the robots that are on the same node as it also execute this function. While executing the function Search, if multiple robots are on the same node, one considers the left direction, while the others consider the right direction.

Applying these movements on r and recursively on the robots that r meet that consider the right direction after their meeting with r and so on, we succeed to prove the property ( * ).

( * * ) Note that if there exists a time at which there is no more righter in the execution, then by applying (ii), Lemma 7 and Lemma 14 multiple times we succeed to prove that a towerM in is formed. Therefore at least one robot is always a righter during the whole execution. Call S r the set of righter robots that stay righter during the whole execution.

Let us consider the following cases.

Case 1: There does not exist an eventual missing edge.

None of the robots of S r can be located on the same node as an awareSearcher, otherwise, by (vi), they become awareSearcher. Therefore, all the robots of S r that are not on node u can only consider the right direction (refer to (iv)). Since all the edges are infinitely often present, for each robot r" of S r , it exists a time at which r" is on node u. Moreover, once on node u, as long as there is no adjacent right edge to u, r" considers the right direction (refer to (iv)), and therefore stays on node u. Thus, since all the edges are infinitely often present, for each robot r" of S r , it exists a time at which r" is on node u such that an adjacent right edge to u is present. Therefore, by (v), in finite time, all the robots of S r are awareSearcher robots. Hence, by ( * * ), the lemma is proved.

Case 2: There exists an eventual missing edge.

Call x the node such that its adjacent right edge is the eventual missing edge. Consider the execution after time t such that the eventual missing edge is missing forever.

Case 2.1: x = u. None of the robots of S r can be located on the same node as an awareSearcher, otherwise, by (vi), they become awareSearcher. Therefore, all the robots of S r that are not on node u can only consider the right direction (refer to (iv)). Since it can exist at most one eventual missing edge, in finite time the robots of S r succeed to reach node u, and stay on node u (refer to (iv)). Necessarily, |S r | < R-2, otherwise Rule Term 2 is executed. At the time at which all the robots of S r are on node u, by ( * ), we know that at least one awareSearcher, on a node v, considers the right direction. By (vi), none of the righter of S r can be located on node v. Therefore, this awareSearcher is not on node u. By the movements described in (iii) and (vii), we know that in finite time an awareSearcher succeeds to reach node u. Then all the righter of S r become awareSearcher, hence by ( * * ), the lemma is proved.

Case 2.2: x = u. None of the robots of S r can be located on the same node as an awareSearcher, otherwise, by (vi), they become awareSearcher. Therefore, none of the robots of S r can be located on Seg(u, x) ∪ {x}, otherwise, in finite time, by (iv) they are located on node x. However, once all the robots of S r are on node x, by ( * ), and the movements described in (iii) and (vii) an awareSearcher succeeds to be located on node u in finite time, which leads to a contradiction. Therefore all the robots of S r are on nodes in Seg(x, u). Since it can exist only one eventual missing edge, and since this edge is the adjacent right edge of x, for each robot r" of S r , by (iv), it exists a time at which r" is on node u while there is a present adjacent right edge to u. Therefore, by (v), in finite time all the robots of S r are awareSearcher robots. Hence, by ( * * ), the lemma is proved.

We just proved that it exists a time t tower at which a towerM in is present in the execution. We now prove that, at time t tower , among the robots not involved in the towerM in, there is at most one righter. By Lemma 6, there is only one towerM in in the whole execution. Necessarily, as explained above when there is no potential-M in in the execution, in order to have a towerM in, a righter must become an awareSearcher while executing Rule K 4 . The property ( * ) is then true. By definition of a towerM in, only two robots are not involved in the towerM in. Assume, by contradiction, that there are two righter not involved in the towerM in at time t tower . By ( * ), this implies that there is an awareSearcher at time t tower . However, by definition, a towerM in is composed of one minW aitingW alker and R -3 waitingW alker, therefore, since there are R robots in the system and among them, at time t tower , two are righter and one is an awareSearcher, there is a contradiction with the fact that there is a towerM in at time t tower .

By Lemmas 15 and 16, we can deduce the following corollary which proves the correctness of Phase K.

Corollary 5. There exists a time t in the execution at which a towerM in is present and among the robots not involved in the towerM in there is at most one righter robot at time t.

Proofs of Correctness of Phases W and T

The combination of Phases W and T of GDG permit to solve G EW in COT rings. Since G EW is divided into a safety and a liveness property, to prove the correctness of Phases W and T, we have to prove each of these two properties. We recall that, to satisfy the safety property of the gathering problem, all the robots that terminate their execution have to do so on the same node, and to satisfy the liveness property of G EW , at least R -1 robots must terminate their execution in finite time. In this subsection, we, first, prove that GDG solves the safety of the gathering problem in COT rings, and then, we prove that GDG solves the liveness of G EW in COT rings. We prove this respectively in Lemmas 19 and 21. To prove these two lemmas, we need to prove some other lemmas.

By Corollary 5, we know that, in finite time, a towerM in is formed. By Lemma 6, there is at most one towerM in in the execution. Therefore, there is one and only one towerM in in the execution. Call T such a towerM in. Let t tower be the time at which T is formed. By definition, a towerM in is composed of R -2 robots. Call r 1 and r 2 the two robots that are not involved in T .

In the previous subsection, we prove that, at time t tower , at most one of the robots among r 1 and r 2 is a righter. In the following lemma, we go farther and give the set of possible values for the variable state at time t tower of each of these robots.

Lemma 17. At time t tower , state r1 ∈ {righter, potentialM in, dumbSearcher, awareSearcher} and state r2 ∈ {dumbSearcher, awareSearcher}.

Proof. Until the Look phase of time t tower , by the rules of GDG and knowing that all the robots are initially righter, there are only righter, potentialM in, dumbSearcher, awareSearcher, waitingW alker and min-W aitingW alker robots in the execution.

By Corollary 4, only r min can be min, therefore only r min can be minW aitingW alker. By definition of a towerM in, a minW aitingW alker is involved in T . Since r 1 and r 2 are not involved in T , this implies that neither r 1 nor r 2 can be minW aitingW alker at time t tower .

By definition of a towerM in, at time t tower , the R -2 robots involved in T are on a same node. This node is the node u. Therefore, at time t tower neither r 1 nor r 2 can be located on node u, otherwise Rule Term 2 is executed. By Lemma 7, this implies that neither r 1 nor r 2 can be a waitingW alker at time t tower . By Corollary 5, at time t tower , only one robot among r 1 and r 2 can be a righter robot. Assume without lost of generality that r 1 is a righter at time t tower . In this case by Corollary 5, r 2 cannot be a righter at time t tower . Moreover, in this case, by Lemma 10, r 2 cannot be a potentialM in at time t tower . Now assume without lost of generality that r 1 is a potentialM in robot at time t tower . By Lemmas 8 and 10, r 2 can neither be a potentialM in nor a righter at time t tower .

This prove the lemma.

In the following lemma, we prove a property on Rules Term 1 and Term 2 that helps us to prove that GDG solves G EW in COT rings.

Lemma 18. If a robot r, on a node x, at a time t, executes Rule Term 1 (resp. Term 2 ), then there are R (resp. R -1) robots on node x at time t and they all execute Rule Term 1 (resp. Term 2 ) at time t (if they are not already terminated).

Proof. If a robot r, on a node x, executes Rule Term 1 (resp. Term 2 ) at a time t, by the predicate G E () (resp. G EW ()), there are R (resp. R -1) robots on x at time t. Moreover, if the predicate G E () (resp. G EW ()) is true for r at time t, since the robots are fully-synchronous, it is necessarily true for all the robots (not already terminated) located on node x at time t. This implies that all the robots (not already terminated) located on x at time t, execute Rule Term 1 (resp. Term 2 ) at time t. Now we prove one of the two main lemmas of this subsection: we prove that GDG solves the safety property of the gathering problem in COT rings.

Lemma 19. GDG solves the safety of the gathering problem in COT rings.

Proof. We want to prove that, while executing GDG, all robots that terminate their execution terminate it on the same node. While executing GDG, the only way for a robot to terminate its execution is to execute either Rule Term 1 or Rule Term 2 .

By Lemma 18, if a robot r, on a node x, at a time t, executes Rule Term 1 , then there are R robots on node x at time t and they all execute Rule Term 1 at time t (if they are not already terminated). Therefore, in the case where r executes Rule Term 1 at time t, all the robots of the system are terminated on x at time t, hence the lemma is proved in this case.

By Lemma 18, if a robot r, on a node x, at a time t, executes Rule Term 2 , then there are R -1 robots on node x at time t and they all execute Rule Term 2 at time t (if they are not already terminated). Therefore, in the case where r executes Rule Term 2 at time t, R -1 robots of the system are terminated on x at time t. Call r the robot that is not on the node x at time t. Let y (y = x) be the node where r is located at time t. To prove the lemma, it stays to prove that r is not terminated at time t, and that after time t, r either terminates its execution on node x or never terminates its execution.

Assume, by contradiction, that at time t, r is terminated. This implies that there exists a time t ≤ t at which r executes either Rule Term 1 or Rule Term 2 . By Lemma 18, this implies that at least R -2 other robots are terminated on node y at time t . Therefore, there is a contradiction with the fact that r executes Rule Term 2 at time t on node x. Indeed, to execute Rule Term 2 at time t on node x, R -1 robots must be located on node x at time t, since R ≥ 4, it is not possible to have R -1 robots on node x at time t.

Moreover, after time t, by Lemma 18, r can terminate its execution only on node x (since it is the only node where R -1 robots are located). Therefore, the lemma is proved.

The following lemma is an extension of Lemma 13. While Lemma 13 is true when the robots are either executing Phase M or Phase K, the following lemma is true whatever the phase of the algorithm the robots are executing.

Lemma 20. If, at time t, an isolated robot r is such that state r ∈ {dumbSearcher, awareSearcher}, then, during the Move phase of time t -1, it does not consider the ⊥ direction.

Proof. By the rules of GDG, minW aitingW alker, waitingW alker, minT ailW alker, tailW alker, headW alker and lef tW alker cannot become dumbSearcher or awareSearcher.

Consider an isolated robot r such that, at a time t, state r ∈ {dumbSearcher, awareSearcher}.

Consider then the two following cases.

Case 1: At time t -1, r is neither a dumbSearcher nor an awareSearcher.

Whatever the state of r at time t -1 (righter or potentialM in), to have its variable state at time t equals either to dumbSearcher or to awareSearcher, r executes at time t -

1 either Rule K 4 , M 2 , M 3 , M 5 , M 6 or M 7 .
When a robot executes Rule M 2 , it calls the function BecomeAwareSearcher. When a robot executes the function BecomeAwareSearcher, it sets its direction to the right direction, therefore the lemma is true in this case.

A robot executes Rule M 3 only if it is located with a headW alker on a node x. Necessarily there is no present adjacent right edge to x at time t -1, otherwise the robot would have executed Rule M 2 . By the rules of GDG, a headW alker only considers the ⊥ direction or the right direction. Indeed, a headW alker can only execute Rules T 2 , T 3 and W 1 . While executing Rule T 2 , a headW alker becomes a lef tW alker and considers the ⊥ direction. While executing Rule T 3 , a headW alker considers the ⊥ direction. Finally, while executing Rule W 1 , a headW alker considers either the right direction or the ⊥ direction. Therefore, even if, after the execution of Rule M 3 , r considers the ⊥ direction, it is not isolated at time t, hence the lemma is not false in this case.

Then, we can use the arguments of the proof of Lemma 13 (in the case where the robot r is a dumbSearcher or an awareSearcher at time t) to prove that the current lemma is true for the remaining cases. Indeed, even if in Lemma 13 the context is such that there is no towerM in in the execution, the arguments used in its proof are still true in the context of the current lemma.

Case 2: At time t -1, r is a dumbSearcher or an awareSearcher.

Whatever the state of r at time t -1 (dumbSearcher or awareSearcher), to have its variable state at time t equals either to dumbSearcher or to awareSearcher, r executes at time t -

1 either Rule M 2 , M 3 , M 9 , M 10 or M 11 .
We can use the arguments of Case 1 to prove that while executing Rule M 2 or M 3 , the lemma is proved.

Then, similarly as for the Case 1, we can use the arguments of the proof of Lemma 13 (in the case where the robot r is a dumbSearcher or an awareSearcher at time t) to prove that the current lemma is true in the remaining cases of Case 2.

Finally, we prove the other main lemma of this subsection: we prove that GDG solves the liveness of G EW in COT rings. In the following proof, we consider that there exists an eventual missing edge while GDG is executed, otherwise, during the execution, the ring is a RE ring (we treat the case of RE rings in subsection 5.2). Lemma 21. GDG solves the liveness of G EW in COT rings.

Proof. By contradiction, assume that GDG does not solve the liveness of G EW in COT rings. Since the execution of Rules Term 1 and Term 2 permits a robot to terminate its execution, by Lemma 18, this implies that there exists a COT ring such that, during the execution of GDG, neither Rule Term 1 nor Rule Term 2 is executed. Consider the execution of GDG on that ring.

By Corollary 5, there exists a time t at which a towerM in is formed. Note that R-2 ≥ 2 robots are involved in a towerM in. Once a towerM in is formed the R -3 waitingW alker and the minW aitingW alker involved in this towerM in execute Rule K 1 . While executing this rule, the robot r with the maximum identifier among the R -2 robots involved in this towerM in becomes headW alker, the minW aitingW alker becomes minT ail-W alker and the other robots involved in this towerM in become tailW alker. Note that, by Corollary 4, only r min can be min, and therefore, since r min is the robot with the minimum identifier among all the robots of the system and since at least 2 robots are involved in the towerM in, r min cannot become headW alker. By Lemma 6 and by the rules of GDG, only r can be headW alker and only r min can be minT ailW alker during the execution.

There is no rule in GDG permitting a tailW alker or a minT ailW alker robot to become another kind of robot. A tailW alker and a minT ailW alker can only execute Rules T 3 and W 1 . By the rules of GDG, the minT ailW alker and the tailW alker execute the same movements at the same time starting from the same node, therefore, they are on a same node at each instant time. Hence, call tail the set of all of these robots.

A headW alker can become a lef tW alker. However, since we assume that the liveness of G EW cannot be solved, then it is not possible for r to become a lef tW alker. Indeed, a headW alker can only execute Rules T 2 , T 3 and W 1 . Note that, by the rules of GDG, after the execution of Rule K 1 , the headW alker and the tail both execute Rule W 1 . Therefore, since the headW alker and the tail start the execution of Rule W 1 on the same node at the same time, by the rules of GDG, while the headW alker is executing Rule T 3 or Rule W 1 , if the tail is not on the same node as the headW alker, it is either executing Rule W 1 or it is terminated. Moreover, by the same arguments, in the remaining of the execution, the headW alker and the tail are either on a same node or the tail is on the left adjacent node (on the footprint of the dynamic ring) of the node where the headW alker is located. Hence, if at a time t , the headW alker executes Rule T 2 , and therefore becomes a lef tW alker, then this implies that during time t -1 it is executing either Rule T 3 or Rule W 1 while there is an adjacent left edge to its position and at time t the tail is not on its node. Therefore, necessarily the tail is terminated, otherwise as explained the tail would have join the headW alker on its node (Rule W 1 ). Since only Rules Term 1 and Term 2 permit a robot to terminate its execution, by Lemma 18, this implies that the tail has executed Rule Term 2 , which leads to a contradiction with the fact that GDG does not solve the liveness of G EW .

Therefore, during the whole execution (after the execution of Rule K 1 ), the headW alker, tailW alker and minT ailW alker stay respectively headW alker, tailW alker and minT ailW alker and can only execute Rule W 1 until their variables walkSteps reach n, and then they can only execute Rule T 3 .

Call r 1 and r 2 the two robots that are not involved in the towerM in at time t. Since, by contradiction, neither Rule Term 1 nor Rule Term 2 are true, neither r 1 nor r 2 can meet the headW alker or the tail while they (the headW alker and the tail) are on a same node. Therefore, we assume that this event never happens. By Lemma 17, at time t, state r1 ∈ {righter, potentialM in, dumbSearcher, awareSearcher} and state r2 ∈ {dumbSearcher, awareSearcher}.

Let us first consider all the possible interactions between only r 1 and r 2 while state r1 ∈ {righter, potential-M in, dumbSearcher, awareSearcher} and state r2 ∈ {dumbSearcher, awareSearcher}.

An isolated potentialM in or a potentialM in that is located only with a dumbSearcher stays a potential-M in and considers the right direction (Rule M 8 ).

If a potentialM in is located only with an awareSearcher, it becomes an awareSearcher and it executes the function Search (Rule M 5 ).

An isolated righter stays a righter and considers the right direction (Rule M 8 ). If a righter is located only with a dumbSearcher (resp. an awareSearcher), it becomes an awareSearcher and executes the function Search (Rule M 7 ).

If a dumbSearcher is located only with a righter, it becomes an awareSearcher and executes the function Search (RuleM 9 ).

If a dumbSearcher is located only with a potentialM in it stays a dumbSearcher and executes the function Search (Rule M 11 ). In this case, while executing the function Search, a dumbSearcher considers the lef t direction, since it possesses a greater identifier than the one of the potentialM in. Indeed, only Rule M 6 permits a robot to become potentialM in or dumbSearcher. This rule is executed when R -1 righter are located on a same node. While executing Rule M 6 , among the R -1 righter, the one with the minimum identifier becomes potentialM in while the others become dumbSearcher. By Observation 2, Rule M 6 can be executed only once. Therefore, a dumbSearcher necessarily possesses an identifier greater than the one of the potentialM in.

An isolated dumbSearcher or a dumbSearcher located only with another dumbSearcher stays a dumbSearcher and executes the function Search (Rule M 11 ).

If a dumbSearcher is located only with an awareSearcher, it becomes an awareSearcher and it executes the function Search (Rule M 10 ).

An isolated awareSearcher or an awareSearcher located only with a righter, a potentialM in, a dumb-Searcher or an awareSearcher stays an awareSearcher and executes the function Search (Rule M 11 ).

When r 1 and r 2 are on a same node without any other robot, executing the function Search, since all the robots possess distinct identifiers, one considers the right direction, while the other one considers the lef t direction.

While executing the function Search at time i, a robot that is an isolated dumbSearcher or an isolated awareSearcher considers during the Move phase of time i the same direction it considers during the Move phase of time i -1. By Lemma 20, this direction cannot be equal to ⊥.

By the previous movements described, note that, as long as r 1 and r 2 are not located with the headW alker or the tail, they are always such that state r1 ∈ {righter, potentialM in, dumbSearcher, awareSearcher} and state r2 ∈ {dumbSearcher, awareSearcher}. Now, consider the possible interactions between the headW alker and r 1 and/or r 2 when state r1 ∈ {righter, potentialM in, dumbSearcher, awareSearcher} and state r2 ∈ {dumbSearcher, awareSearcher}.

If r 1 and/or r 2 , as a righter, potentialM in, dumbSearcher or awareSearcher is on the same node as the headW alker such that there is no adjacent right edge to their location, then it executes Rule M 3 , hence it becomes an awareSearcher and stops to move.

( * ) If r 1 and/or r 2 , as a righter, potentialM in, dumbSearcher or awareSearcher is on the same node as the headW alker such that there is an adjacent right edge to their location, then it executes Rule M 2 , hence it becomes an awareSearcher considering the right direction and therefore crosses the adjacent right edge to its node.

This implies that, as long as r 1 and r 2 are not located with the tail they are always such that state r1 ∈ {righter, potentialM in, dumbSearcher, awareSearcher} and state r2 ∈ {dumbSearcher, awareSearcher}.

Finally, consider the possible interaction between the tail and r 1 and/or r 2 . If r 1 and/or r 2 , as a righter, potentialM in, dumbSearcher or awareSearcher is on the same node as the minT ailW alker, then it executes Rule M 4 and becomes a tailW alker. From this time, by the function BecomeTailWalker and the rules of GDG, the robot belongs to the tail.

We assume that there exists an eventual missing edge. Call t" the time after the execution of Rule K 1 and after the time when the eventual missing edge is missing forever. Consider the execution from t". Since Rule K 1 is executed before time t", then there are headW alker, tailW alker and minT ailW alker in the execution after time t" included.

Recall that, while executing Rules W 1 and T 3 , the headW alker and the tail are either on a same node or on two adjacent nodes (the tail is on the adjacent left node on the footprint of the dynamic ring of the node where the headW alker is located).

Case 1: There is an eventual missing edge e between the node where the headWalker is located and the node where the tail is located.

As explained previously, since the headW alker and the tail are not on the same node, this necessarily implies that the headW alker either executes Rule W 1 or Rule T 3 at time t", and the tail executes Rule W 1 at time t". Therefore, after time t", the headW alker does not move either because it waits for the tail to join it on its node (Rule W 1 ), or because it executes the function StopMoving (Rule T 3 ). Similarly, after time t", the tail does not move, since it tries to join the headW alker considering the right direction (Rule W 1 ), but the edge is missing forever.

Since there is at most one eventual missing edge in a COT ring, all the edges, except e, are infinitely often present in the execution after time t". Considering the movements of the robots described previously, whatever the direction considered by r 1 and r 2 at time t" both of them succeed eventually to reach the node where the tail is located, making the liveness of G EW solved.

Case 2: The eventual missing edge is not between the node where the headWalker is located and the node where the tail is located.

This implies that there exists a time from which the headW alker and the tail are located on a same node and do not move, either because they are executing Rule T 3 , or because they are executing Rule W 1 but the adjacent right edge the headW alker tries to cross is the eventual missing edge. In the second case, by the movements of the robots described previously, we succeed to prove that, eventually at most one of the robots among r 1 and r 2 can be stuck on the extremity of the eventual missing edge where the headW alker and the tail are not located, and that at least one of them succeeds to reach the node where the headW alker and the tail are located, making the liveness of G EW solved.

Consider now the first case. Call t n the first time at which the headW alker and the tail are on a same node and both execute Rule T 3 . If r 1 and r 2 consider the same direction at time t n , then by the movements of the robots described previously, whatever the place of the eventual missing edge, we succeed to prove that, eventually at most one of them can be stuck on one of the extremity of the eventual missing edge, and that at least one of them succeeds to reach the node where the headW alker and the tail are located, making the liveness of G EW solved. Similarly, if the headW alker and the tail are located, at time t n , on one of the extremity of the eventual missing edge, then, by the movements of the robots described previously, we succeed to prove that, eventually at most one of the robots among r 1 and r 2 can be stuck on the extremity of the eventual missing edge where the headW alker and the tail are not located, and that at least one of them succeeds to reach the node where the headW alker and the tail are located, making the liveness of G EW solved. Now consider the first case, when r 1 and r 2 consider opposed directions at time t n and such that, at time t n , the headW alker and the tail are not located on one of the extremity of the eventual missing edge. It is not possible for both r 1 and r 2 to be eventually stuck on two different extremities of the eventual missing edge. Indeed, if r 1 and r 2 consider two opposed directions at time t n , this is because, between times t i and t n (with t i the time at which the headW alker and the tail both execute Rule W 1 for the first time), they are located on a same node (without any other robot on their node). We prove this by contradiction. Assume, by contradiction, that r 1 and r 2 are never located on a same node (without any other robot on their node) between times t i and t n . Consider the execution from time t i until time t n . Whatever the direction considered by r 1 (resp. r 2 ), it cannot be located with the tail, otherwise, since there is no eventual missing edge between the headW alker and the tail and by the movements of the robots described previously, Rule Term 2 is eventually executed. Therefore, r 1 (resp. r 2 ) can only be located with the headW alker. When r 1 (resp. r 2 ) is located with the headW alker, it necessarily exists an adjacent right edge to their position before the adjacent left edge to their position appears, otherwise, the tail join them and Rule Term 2 is executed. By ( * ), after r 1 (resp. r 2 ) is on the same node as the head-W alker while there is an adjacent right edge to their location, it becomes an awareSearcher considering the right direction. At time t n , the headW alker and the tail execute Rule T 3 , therefore they succeed to execute Rule W 1 until their variables walkSteps is equal to n. This implies that, if r 1 (resp. r 2 ) considers the left direction at time t i , necessarily, since it cannot be located with r 2 (resp. r 1 ), by the movements of the robots described previously, it exists a time t meet ≥ t i at which the headW alker and the tail execute Rule W 1 and either the headW alker or the tail is located with it. As explained previously, r 1 (resp. r 2 ) cannot be located with the tail, this implies that, at time t meet , r 1 (resp. r 2 ) is located with the headW alker. Therefore, whatever the direction considered by r 1 (resp. r 2 ) at time t i , if r 1 and r 2 are never located on a same node (without any other robot on their node) between times t i and t n , it necessarily considers the right direction at time t n . Indeed, r 1 (resp. r 2 ) considers the right direction at time t n either because it meets the headW alker that makes it consider the right direction or because at time t i it considers the right direction and it is never located with the headW alker and, by the movements of the robots described previously, it has not change its direction between times t i and time t n . Hence, there is a contradiction with the fact that r 1 and r 2 consider opposite directions at time t n . Therefore, r 1 and r 2 consider two opposite directions at time t n because they are located on a same node (without any other robot on their node) between times t i and t n .

Consider the last time t l between times t i and t n at which r 1 and r 2 are located on a same node (without any other robot on their node). At time t l , since the two robots are located on a same node, by the movements of the robots described, during the Move phase of time t l one considers the right direction while the other one considers the left direction. By assumption, between times t l + 1 and t n , r 1 and r 2 are not located on a same node. Moreover, as explained previously, between times t l + 1 and t n , neither r 1 nor r 2 can be located with the tail, otherwise Rule Term 2 is eventually executed. Besides, between times t l + 1 and t n the robot that considers the left direction during the Move phase of time t l cannot be located with the headW alker, otherwise, as noted previously, it considers the right direction at time t n . Similarly, it is not possible for the robot that considers the right direction during the Move phase of time t l to be located with the headW alker between times t l + 1 and t n , otherwise, by the movements of the robots described previously, this necessarily implies that either it is also located on the same node as the tail and therefore the liveness of G EW is solved or r 1 and r 2 are on a same node and therefore the robot that considers the left direction during the Move phase of time t l is located with the headW alker. Therefore, from time t l + 1 to time t n , r 1 and r 2 are isolated, hence, by the movements of the robots, they consider the same respective directions from the Move phase of time t l to time t n .

Assume, without lost of generality, that this is r 1 that considers the right direction from the Move phase of time t l to time t n . Call v 1 (resp. v 2 ) the node on which r 1 (resp. r 2 ) is located at time t n . The explanations of the previous paragraph imply that v 1 = v 2 , and that, at time t n , the node where the headW alker and the tail are located is in Seg(v 1 , v 2 ). Therefore, since r 1 (resp. r 2 ) considers the right (resp. the left) direction at time t n , by the movements of the robots and since it exists only one eventual missing edge, this is not possible for these two robots to be eventually stuck on each of the extremities of the eventual missing edge. Hence, at least one succeeds to reach the node where the headW alker and the tail are located, making the liveness of G EW solved.

By Lemmas 19 and 21, we can deduce the following theorem which proves the correctness of Phases W and T.

Theorem 2. GDG solves G EW in COT rings. [START_REF] Braud-Santoni | The next 700 impossibility results in timevarying graphs[END_REF].2 What about GDG executed in AC, RE, BRE and ST rings?

In the previous subsection we prove that GDG solves G EW in COT rings. In this subsection, we consider AC, RE, BRE and ST rings. For each of these classes of dynamic rings, we give the version of gathering GDG solves in it.

First, we consider the case of AC rings. In the following theorem, we prove that GDG solves G W in AC rings.

Theorem 3. GDG solves G W in AC rings in O(id rmin * n 2 + R * n) rounds.
Proof. By Corollary 2, GDG solves G EW in COT rings, since AC ⊂ COT , this implies that GDG also solves G EW in AC rings. Therefore, to prove that GDG solves G W in AC rings, it stays to prove that each phase of GDG is bounded.

Phase M: By Corollary 4, only r min becomes min in finite time. By the rules of GDG, when r min becomes min, it is first minW aitingW alker before being minT ailW alker (since only a minW aitingW alker can become a minT ailW alker while executing Rule K 1 ). Therefore, since only Rule M 1 permits a robot to become minW aitingW alker, by the predicate M inDiscovery() of this rule, r min becomes min either because it moves during 4 * n * id rmin steps in the right direction or because it meets a robot that permits it to deduce that it is min. In this last case, note that, either r min is potentialM in, or r min meets a potentialM in or a dumbSearcher or a robot whose variable idM in is different from -1. Therefore, in this last case, either r min possesses a variable idP otentialM in different from -1, or r min meets a robot r such that idP otentialM in r is different from -1 (since a potentialM in and a dumbSearcher have their variable idP otentialM in different from -1 (Rule M 6 ) and since, while executing GDG, each time the variable idM in of a robot is set with a variable different from -1, this is also the case for its variable idP otentialM in).

Taking back the arguments used in the proof of Lemma 5, let us consider the following cases.

Case 1.1: Rule M 6 is never executed.

By the rules of GDG, this implies that, before the time when r min is min, there are only righter in the execution. First, this implies that r min becomes min because it moves during 4 * n * id rmin steps in the right direction (since righter robots have their variables idP otentialM in equal to -1). Second, in this context, as long as r min is not min, all the righter always consider the right direction (Rule M 8 ). This implies that, as long as r min is not min, each time a robot wants to move in the right direction it can be stuck during at most n rounds, otherwise, since in an AC ring at most one edge can be missing at each instant time, Rule M 6 is executed. Therefore in case 1.1 r min becomes min in at most 4 * id rmin * n * n rounds. Now let consider the case where Rule M 6 is executed at a time t. In the following, we consider the execution from time t. After time t, while it is not yet min, if r min is stuck more than 4 * n consecutive rounds on a same node then it becomes min. We prove this considering the two following cases. In each of these cases we assume that r min is not yet min and that it is stuck more than n rounds on a same node.

Case 1.2: Rule M 6 is executed but r min is not among the R -1 righter robots that execute it.

Taking back the arguments of the proof of Lemma 5, we know that Rule M 6 can be executed only once, and that the robots that execute this rule can never be righter anymore. Moreover, since r min does not execute Rule M 6 , since, by Corollary 4, r min necessarily becomes min, since, by Lemma 9, only righter and potentialM in can be min, and since only Rule M 6 permits robots to become po-tentialM in, before becoming min, r min is a righter. By the proof of Lemma 5, as long as r min is not min it cannot exist awareSearcher. Hence, by the rules of GDG, as long as r min is not min, there are only one righter, one potentialM in and R -2 dumbSearcher in the execution. Therefore, by the rules of GDG, the potentialM in is potentialM in at least until r min becomes min. Hence, the potentialM in executes Rule M 8 and thus considers the right direction at least until r min becomes min. We have assumed that, while it is not yet min, r min is stuck more than 4 * n consecutive rounds on a same node. Since r min is a righter before being min, it is stuck because the adjacent right edge to its position is missing (Rule M 8 ). Therefore, since in an AC ring of size n at least n -1 edges are present at each instant time, either the potentialM in (or a dumbSearcher) meets r min in at most n rounds. When r min meets a potentialM in (or a dumbSearcher), it becomes min by definition of the predicate M inDiscovery() in Rule M 1 . Therefore, if it is stuck more than 4 * n rounds, r min becomes min in at most n rounds.

Case 1.3: Rule M 6 is executed and r min is among the R -1 righter robots that execute it. In this case, by Rule M 6 , r min becomes potentialM in. By Observations 2 and 1, by Corollary 4 and by Lemma 9 r min is potentialM in until it becomes min. Therefore, r min , while it is not yet min, can be stuck only because the adjacent right edge to its position is missing (Rule M 8 ). First, consider that at the time when r min , as a potentialM in, is stuck more than 4 * n rounds, there does not exist righter in the execution. By Observation 2, there is no more righter in the execution. However, at the time when Rule M 6 is executed, the robot r that is not among the robots that execute this rule is a righter. Therefore, necessarily r, as a righter, meets at least one dumbSearcher at a time t . Indeed, it cannot meet the potentialM in, otherwise r min is min (Rule M 1 ), and thus it is not anymore potentialM in at the time at which it is stuck. Moreover, r cannot be isolated forever after time t, otherwise it stays a righter (Rule M 8 ). Hence, at time t , r becomes an awareSearcher (Rule M 7 ). Consider an awareSearcher r a of the execution. By Lemma 4, r a cannot consider the ⊥ direction. Moreover, by the rules of GDG, as long as there is no min, an awareSearcher executes the function Search (rule M 11 ). Besides, by the proof of Lemma 5 if a robot is not isolated and executes the function Search, then all the robots of its node are or become awareSearcher and execute the function Search. While executing the function Search, an isolated robot does not change its direction. When a robot executes the function Search while there are multiple robots on its node, if it possesses the maximum identifier among the robots of its node, it considers the left direction, otherwise it considers the right direction. In an AC ring of size n, at least n -1 edges are present at each instant time. Therefore, if r a considers the right direction, either it, as an awareSearcher or a robot that is or becomes an awareSearcher is located, in at most n rounds, on the node where r min , as a potentialM in, is stuck. In the case where r a considers the lef t direction then, by the same arguments, in at most 4 * n rounds an awareSearcher is located on the node where r min , as a potentialM in, is stuck. Indeed, at most n rounds are needed for an awareSearcherto reach the extremity of the missing edge where r min is not located. Then, at most 2 * n other rounds are needed for a dumbSearcher (execution of the function Search, rule M 11 ) or an awareSearcher to reach also this node. These 2 * n rounds are especially needed for a dumbSearcher that may take n rounds (considering the left direction) to reach the node where r min is stuck and then again n rounds (considering the right direction) to reach the other extremity of the missing edge. From this time there is in the execution an awareSearcher that considers the right direction. Finally, at most n supplementary rounds are needed for an awareSearcher to reach the node where r min , as a potentialM in, is stuck. Note that R > 4, and there are R -1 dumbSearcher/awareSearcher in the execution as long as r min is not min. Now we consider Phase K of GDG. In this phase r min is min and waits for a towerM in to be formed. We take back the arguments used in the proofs of Lemmas 15 and 16 to prove that this phase is bounded.

Phase K: Case 2.1: There is a potentialMin in the execution.

For this case we take back the arguments of the proof of Lemma 15.

If before being min, r min is a righter, then all the robots that are not located on node u are poten-tialM in, dumbSearcher, and awareSearcher. As long as it is not on node u, a potentialM in either executes Rule M 8 , or it becomes an awareSearcher (Rule M 5 ). While executing Rule M 8 , a poten-tialM in stays a potentialM in and has the same behavior as if it was executing the function Search. Moreover, as long as they are not on node u, dumbSearcher and awareSearcher robots stay either dumbSearcher or awareSearcher and execute the function Search. Therefore, by definition of the function Search (refer to Phase M case 1.3 of this proof) and by Lemma 13, at most 3 * n rounds are needed (in AC rings) for a robot r such that state r ∈ {potentialM in, dumbSearcher, awareSear-cher} to be located on node u. Indeed, these 3 * n rounds are needed especially when a potentialM in, dumbSearcher or awareSearcher moves in one direction during n steps and then is stuck on the adjacent node of u, then n steps are needed for a robot of this kind to be also located on this node and thus to consider the opposite direction, then in at most n additional steps a robot of this kind is located on u. By Rule K 3 , this implies that at most 3 * n rounds are necessary for a supplementary waitingW alker to be located on node u. Therefore, at most (R -3) * 3 * n rounds are needed for a towerM in to be formed. Now consider the case where before being min, r min is a potentialM in.

In this case among the robots that are not on node u, there are dumbSearcher, awareSearcher and at most one righter. For all the cases of Case 2.1 of the proof of Lemma 15, at most (R -4) * 3 * n rounds are needed for R -4 waitingW alker to be located on u (for the same reasons as the one explained in the previous paragraph). Then among the robots that are not on node u, it exists at most one righter, and 2 robots that are either dumbSearcher or awareSearcher. At most n rounds are needed for the righter to be stuck on the node called v in the proof of Lemma 15, and then at most n rounds are needed for a dumbSearcher or an awareSearcher to be also located on node v (and thus, by Rule M 7 , for all the robots that are not on node u to be either dumbSearcher or awareSearcher), and then at most n additional rounds are needed for one of the robot to reach node u. Therefore, for all the cases of Case 2.1 of the proof of Lemma 15, at most (R -4) * 3 * n + 3 * n rounds are needed for a towerM in to be formed. If we consider Case 2.2 of the proof of Lemma 15, similarly as in the previous case, at most (R -4) * 3 * n + 3 * n rounds are needed for Rule Term 2 to be executed.

Case 2.2:

There is no potentialMin in the execution.

For this case we take back the arguments of the proof of Lemma 16. Just after r min becomes min, it takes at most n * n rounds for a robot r to join the node where r min is located. Indeed, as long as no robot is on node u with r min , as a minW aitingW alker, all the robots except r min are righter. By the same arguments as the one used in Phase M Case 1.1 of this proof, a righter cannot be stuck more than n rounds on the same node, otherwise Rule M 6 is executed, which is a contradiction with the fact that there is no potentialM in. Moreover, a righter can move from at most n steps in the right direction to reach u. Once r is on node u an adjacent right edge to u is present in at most n rounds, otherwise Rule Term 1 is executed. Therefore, once r is on node u, in at most n rounds it becomes an awareSearcher. From this time, either it is possible for all the righter to become awareSearcher or it exists at least one righter that is stuck on node u. In the first case at most 2 * n rounds are needed for all the righter to become awareSearcher (either because an awareSearcher meets them, or because they are located on u such that there is an adjacent right edge to u). By the arguments above, we know that if all the robots that are not located on node u are awareSearcher, and if there are more than 3 such robots, then in a most 3 * n rounds one robot of this kind reaches node u. Therefore, for R -3 waitingW alker to be located on node u, with r min , at most (R -3) * 3 * n supplementary rounds are needed. In the second case, at most 2 * n rounds are needed for some of the righter to reach node u (and to be stuck on this node). Since the robots that are not on node u are awareSearcher and since at least one righter is stuck on node u, by the same arguments as above, at most (R - phase T: Using similar arguments as the one used in Phase W, once the headW alker and the minT ailW alker / tailW alker stop to move forever, if they are located on a same node, at most 3 * n rounds are necessary for Rule Term 2 to be executed. In the case where the headW alker and the minT ailW alker / tail-W alker stop to move forever, if they are located on different nodes, at most 2 * n + 2 * n rounds are necessary for Rule Term 2 to be executed. Indeed, at most 2 * n rounds are necessary for each of the two robots that are not involved in T at time t tower to be located on the node where the minT ail-W alker /tailW alker is located. This is true whatever the interactions between r 1 and r 2 and whatever the interactions between r 1 (resp. r 2 ) and the headW alker since in an AC ring there is at most one edge missing at each instant time (and in this precise case the missing edge is between the node where the headW alker is located and the node where the minT ailW alker / tailW alker are located). Therefore, Phase T is bounded and is in O(n) rounds.

In conclusion each of the four phases of algorithm GDG are bounded when executed in an AC ring, therefore GDG solves G W in AC rings. Moreover, GDG solves G W in AC rings in O(id rmin * n 2 + R * n) rounds. Now, we consider the case of RE rings. In the following theorem, we prove that GDG solves G E in RE rings. Proof. By Corollary 2, GDG solves G EW in COT rings, therefore it solves the safety and the liveness of G EW in COT rings. Since RE ⊂ COT , GDG also solves the safety and the liveness of G EW in RE rings. This implies that all robots that terminate their execution terminate it on the same node and it exists a time at which at least R -1 robots terminate their execution. Call t the first time at which at least R -1 robots terminate their execution.

By contradiction, assume that GDG does not solve G E in RE rings, this implies that it exists a robot r that never terminates its execution.

Call towerT ermination the R -1 robots that, at time t, are located on a same node and are terminated. While executing GDG, the only way for a robot to terminate its execution is to execute either Rule Term 1 or Rule Term 2 . By Lemma 18, for a towerT ermination to be formed at time t, Rule Term 2 has to be executed at this time.

( * ) By the predicate of Rule Term 2 , r min belongs to the towerT ermination. By Lemma 18, all the robots that are located on the same node as r min at time t belong to the towerT ermination.

Call w the node where the towerT ermination is located at time t. Note that r cannot be located on node w after time t included, otherwise it executes Rule Term 1 and the lemma is proved.

Since r min belongs to the towerT ermination, and since by Corollary 4, only r min can be minW aiting-W alker or a minT ailW alker, r is neither minW aitingW alker nor minT ailW alker.

At time t, r cannot be a tailW alker. Indeed, to become a tailW alker, a robot must either execute Rule K 1 or Rule M 4 . To execute Rule K 1 a robot must be a waitingW alker. By Lemma 7, all waitingW alker are located on the same node as the minW aitingW alker. Moreover, when a waitingW alker executes Rule K 1 , by the predicate AllButT woW aitingW alker(), the minW aitingW alker also executes this rule becoming a min-T ailW alker. Then by the rules of GDG, the robot that becomes tailW alker while executing Rule K 1 and the minT ailW alker execute the same movements (refer to Rules W 1 and T 3 ), and therefore are always on a same node. Besides, to execute Rule M 4 a robot must be located on the same node as the minW aitingW alker (refer to the predicate N otW alkerW ithT ailW alker(r )). Then, thanks to the function BecomeTailWalker and by the rules of GDG, the robot that becomes tailW alker while executing Rule M 4 cannot be on a node different from the one where the minT ailW alker is located (refer to Rules W 1 and T 3 ). Therefore, by ( * ), r cannot be a tailW alker at time t, otherwise, at time t, it is on the same node as the minT ailW alker (thus, by Corollary 4, it is on the same node as r min ) and hence it terminates its execution.

At time t, r cannot be a waitingW alker robot. Indeed by the rules of GDG and the previous remarks, it cannot exists waitingW alker if there is no minW aitingW alker in the execution, and by Lemma 7 all the waitingW alker and minW aitingW alker are located on a same node. Therefore, by ( * ), r cannot be a waiting-W alker at time t, otherwise, at time t, it is on the same node as the minW aitingW alker (thus, by Corollary 4, it is on the same node as r min ) and hence it terminates its execution.

Therefore, at time t, r can be either a righter, a potentialM in, a dumbSearcher, an awareSearcher, a headW alker or a lef tW alker robot.

As long as r is not on node w, it is isolated. An isolated righter or an isolated potentialM in only executes Rule M 8 . While executing this rule, a robot considers the right direction and stays a righter or a potentialM in. Since all the edges are infinitely often present, such a robot is infinitely often able to move in the right direction until reaching the node w.

An isolated dumbSearcher or an isolated awareSearcher only executes Rule M 11 . While executing this rule, an isolated robot stays a dumbSearcher or an awareSearcher, and considers the direction it considers during the previous Move phase. By Lemma 20, this direction cannot be equal to ⊥. Therefore, an isolated dumbSearcher or an isolated awareSearcher always considers the same direction d (either right or lef t). Since all the edges are infinitely often present, such a robot is infinitely often able to move in the direction d until reaching the node w. Now assume that, at time t, r is a lef tW alker. A lef tW alker only executes Rule T 1 . While executing this rule, a robot considers the lef t direction and stays a lef tW alker. Since all the edges are infinitely often present, such a robot is infinitely often able to move in the lef t direction until reaching the node w. Now assume that, at time t, r is a headW alker. A headW alker can execute either Rule T 2 or Rule T 3 or Rule W 1 . While executing Rule T 2 , a headW alker becomes a lef tW alker, then, by the previous paragraph, r reaches the node w in finite time. Consider now the cases where, at time t, r executes either Rule T 3 or Rule W 1 . In these cases, after time t, it necessarily exists a time at which r executes Rule T 2 . Assume, by contradiction, that this is not true. The only way for a robot to become a headW alker is to execute Rule K 1 . Rule K 1 is executed when R -2 robots are located on a same node. While executing this rule, a robot sets its variable walkerM ate with the identifiers of the robots that are located on its node. Only Rule K 1 permits a robot to update its variable walkerM ate. Note that, since R -2 ≥ 2, the variable walkerM ate of r, after time t, contains at least one identifier i different from the identifier of r. The robot of identifier i necessarily belongs to the towerT ermination, since only r does not terminate. (1) Hence, at time t, the robot of identifier i is terminated on node w, thus it does not move, and therefore, after time t, r is never on the same node as i. (2) All the edges are infinitely often present. While executing Rule T 3 at time t, r considers the ⊥ direction and does not update its other variables. (3) Hence, by the rules of GDG, since r cannot execute Rule T 2 , after time t, r can only execute Rule T 3 , and therefore only considers the ⊥ direction. Hence, necessarily by (1), ( 2) and (3), this implies that, after time t, it exists a time at which the predicate HeadW alkerW ithoutW alkerM ate() is true, thus at this time Rule T 2 is executed. Similarly, if at time t, r executes Rule W 1 , since r can never be located on the same node as i, while executing Rule W 1 , it considers the ⊥ direction and does not update its other variables. (4) Hence, by the rules of GDG, since r cannot execute Rule T 2 , after time t, r can only execute Rule W 1 , and therefore always considers the ⊥ direction. Thus, by (1), ( 2) and (4), necessarily, after time t, it exists a time at which the predicate HeadW alkerW ithoutW alkerM ate() is true, hence at this time Rule T 2 is executed. Therefore, even in the cases where, at time t, r executes either Rule T 3 or Rule W 1 , it exists a time greater than t at which r becomes a lef tW alker and hence, by the previous paragraph, r succeeds to reach the node w in finite time.

Therefore whatever the kind of robot r is, it is always able to reach the node w. Once r reaches the node w it executes Rule Term 1 making G E solved. Now, we consider the case of BRE rings. We prove, in Theorem 5, that GDG solves G in BRE rings. To prove this, we first need to prove the following lemma that it useful to bound Phase K of GDG in BRE rings.

Lemma 22. If the ring is a BRE ring and if there is no towerM in in the execution but there exists at a time t at least 3 robots such that they are either potentialM in, dumbSearcher or awareSearcher, then at least a potentialM in, a dumbSearcher or an awareSearcher reaches the node u between time t and time t + n * δ included, with δ ≥ 1.

Proof. We prove this lemma using the arguments of the proof of Lemma 14 and the fact that in a BRE ring each edge appears at least once every δ units of time. Proof. By Lemma 4, GDG solves G E in RE rings. Therefore, since BRE ⊂ RE, then GDG also solves G E in BRE rings. We want to prove that GDG solves G in BRE rings. Therefore, we have to prove that each phase of the algorithm is bounded.

Phase M: By Corollary 4, we know that only r min becomes min in finite time. By Lemma 9, before being min, r min is either a righter or a potentialM in robot. By Lemma 2, if, at a time t, a robot is a righter or a potentialM in robot, then it considers the right direction from the beginning of the execution until the Look phase of time t. Since initially all the robots are righter, and since, by the rules of GDG, only righter can become potentialM in (refer to Rule M 6 ), then by Observations 2 and 1, a robot that is a righter (resp. potentialM in) is a righter (resp. is either a righter or a potentialM in) since the beginning of the execution. Besides, each time r min , as a righter or as a potentialM in, crosses an edge in the right direction, it increases its variable rightSteps of one (refer to Rules M 8 and M 6 ). Therefore, since each edge of the footprint of a BREring is present at least once every δ units of time, by definition of min and of the predicate M inDiscovery() of Rule M 1 , r min becomes min in at most 4 * n * id rmin * δ rounds.

Hence, Phase M is bounded and is in O(id rmin * n * δ).

Phase K: Now, consider the execution when r min just becomes min. Therefore, we consider the execution once r min is minW aitingW alker. By Corollary 5, we know that in finite time a towerM in is formed. By Lemma 6, there is only one towerM in in the whole execution. Therefore, before a towerM in is formed, by the rules of GDG and since initially all the robots are righter, there are only righter, potentialM in, dumbSearcher, awareSearcher, minW aitingW alker and waitingW alker robots. By Lemma 7, we know that all the minW aitingW alker and waitingW alker robots are located on a same node and do not move. By Rule K 3 , if a potentialM in, a dumbSearcher or an awareSearcher is located on the same node as a minW aitingW alker, it becomes waitingW alker ( * ). If there is no more righter robot in the execution, we use Lemma 22 and ( * ) multiple times to prove that it takes at most n * δ * (R -3) rounds for a towerM in to be formed. To prove that Phase K is bounded, we hence have to prove that the number of rounds that are necessary to stop to have righter in the execution is bounded.

If a righter is located on the same node as the minW aitingW alker while there is an adjacent right edge to its location, then by Rule K 4 , the righter becomes an awareSearcher and moves on the right. If a righter is located only with R -2 other righter, they all execute Rule M 6 , hence one becomes potential-M in while the others become dumbSearcher. If a righter is located either with a dumbSearcher or with an awareSearcher, then it becomes an awareSearcher (Rule M 7 ). Note that, by Lemma 10, since we consider the execution once r min is min, it cannot exist a righter and a potentialM in in the execution. Therefore, a righter cannot meet a potentialM in. In all the other cases, (a righter that is isolated, a righter that is only with other righter on its node such that |N odeM ate()| < R -2, and a righter that is located on the same node as the minW aitingW alker while there is no adjacent right edge to its location) a righter stays a righter and considers the right direction (Rule M 8 ). Therefore, by Observation 2 and since each edge of the footprint of a BRE ring is present at least once every δ units of time, it takes at most n * δ rounds in order to stop having righter robots in the execution. Indeed, even if a righter does not execute Rule M 7 or Rule M 6 , at most n * δ rounds are needed for it to be located on the node where the minW aitingW alker is located while there is an adjacent right edge to its position. Hence, Phase K is bounded and is in O(n * R * δ).

Once a towerM in is present in the execution, the robots forming this towerM in execute Rule K 1 . While executing this rule, the robot r with the maximum identifier among the robots involved in this towerM in becomes headW alker while the minW aitingW alker becomes minT ailW alker and the other robots involved in this towerM in become tailW alker. Note that, by Corollary 4, only r min can be min, and therefore, since r min is the robot with the minimum identifier among all the robots of the system and since at least 2 robots are involved in a towerM in, r min cannot become headW alker. By Lemma 6 and by the rules of GDG, only r can be headW alker during the execution.

There is no rule in GDG permitting a tailW alker or a minT ailW alker robot to become another kind of robot. A headW alker can become a lef tW alker. Let then consider the two following cases.

Case 1: r is a headWalker during the whole execution.

Phase W: A headW alker can execute Rules T 2 , T 3 and W 1 . Since r does not become a lef tW alker, it cannot execute Rule T 2 . Moreover, since we consider the worst case execution in terms of time, this implies that r is able to execute Rule W 1 entirely. This means that r is able to execute Rule W 1 until its variable walkSteps reaches the value n. In other words, r is able to execute Rule W 1 until it executes Rule T 3 .

In this case, the tailW alker and minT ailW alker are also able to execute Rule W 1 entirely. Indeed, if, at a time t , while executing Rule W 1 or Rule T 3 , the headW alker is waiting on its node for the tailW alker and the minT ailW alker to join it while there is an adjacent left edge to its position, and if at time t + 1 the tailW alker and the minT ailW alker have not join it on its node, this necessarily implies that they stop their execution, otherwise by Rule W 1 they would have join it. Moreover, if such an event happens, r executes Rule T 1 and therefore becomes a lef tW alker, which leads to a contradiction.

If the headW alker and the minT ailW alker/tailW alker execute Rule W 1 entirely, this implies that they move alternatively in the right direction during n steps. Since each edge of the footprint of a BRE ring is present at least once every δ units of time, this takes at most 2 * n * δ rounds. Phase W being composed only of the execution of Rule W 1 , this phase is bounded.

Phase T: Call t v the time at which the headW alker and minT ailW alker/tailW alker robots finish to execute Rule W 1 entirely. Since the headW alker and minT ailW alker/tailW alker start the execution of Rule W 1 on the same node, at time t v , they are on the same node v.

Call r 1 and r 2 the two robots that are not involved in the towerM in at time t tower .

If at time t v , r 1 and r 2 are on node v, then Rule Term 1 is executed at time t v . In this case, by Lemma 18, Phase T last 0 round, hence it is bounded. If at time t v , only one robot among r 1 and r 2 is located on node v, then Rule Term 2 is executed at time t v . Hence, by Lemma 18, R -2 robots are terminated on node v at time t v . By Lemma 17, at time t tower , r 1 and r 2 are such that state r1 ∈ {righter, potentialM in, awareSearcher, dumbSear-cher} and state r2 ∈ {awareSearcher, dumbSearcher}. By the movements of the robots given in the proof of Lemma 21, and since each edge of the footprint of a BRE ring is present at least once every δ units of time, it takes at most n * δ rounds for the last robot to reach node v. Therefore, it takes at most n * δ rounds for Rule Term 1 to be executed, and thus, by Lemma 18, for all the robots to be terminated on node v. Hence, in this case Phase T last at most n * δ rounds, therefore it is bounded. Now, consider that at time t v neither r 1 nor r 2 is located on node v. In this case, at time t v , the headW alker and minT ailW alker/tailW alker execute Rule T 3 . While executing Rule T 3 , the headW alker (resp. minT ailW alker/tailW alker) stays a headW alker (resp. minT ailW alker/tail-W alker) and considers the ⊥ direction. Then, by the rules of GDG, they can only execute Rule T 3 until they terminate. Therefore, they remain on node v from time t v until the end of their execution. Moreover, as noted previously, by Lemma 17, at time t tower , r 1 and r 2 are such that state r1 ∈ {righter, potentialM in, awareSearcher, dumbSearcher} and state r2 ∈ {awareSearcher, dumbSearcher}. By the movements of the robots given in the proof of Lemma 21, since each edge of the footprint of a BRE ring is present at least once every δ units of time, it takes at most 2 * n * δ rounds for r 1 and r 2 to both reach the node v (in case r 1 and r 2 meet on an adjacent node of v after at most n * δ rounds of movements in the same direction). In the case the two robots reach node v at the same time, then Rule Term 1 is executed, hence, by Lemma 18, all the robots terminate at that time. In the case the two robots do not reach node v at the same time, then the first one that reaches v permits the execution of Rule Term 2 (hence, by Lemma 18, permits the termination of R -2 robots on node v) and the second that reaches v permits the execution of Rule Term 1 . Hence, Phase T last at most 2 * n * δ rounds, therefore it is bounded.

Case 2: It exists a time at which r is a leftWalker.

By the explanations given in the Case 1, Phase W, at most 2 * n * δ rounds are needed for r to become lef tW alker and for the R -2 other robots to terminate their execution on a node v.

Figure 1 :

 1 Figure 1: Construction of G i+1 from G i .

  8 :: P otentialM inOrRighter() -→ MoveRight() M 9 :: DumbSearcherM inRevelation() -→ BecomeAwareSearcher(r); Search() M 10 :: ∃r ∈ N odeM ate(), DumbSearcherW ithAwareSearcher(r ) -→ BecomeAwareSearcher(r'); Search() M 11 :: Searcher() -→ Search() robot stops executing the cycle Look-Compute-Move forever.

Theorem 4 .

 4 GDG solves G E in RE rings.

Theorem 5 .

 5 GDG solves G in BRE rings in O(n * δ * (id rmin + R)) rounds.

Table

  Impossible (Cor. 2 & 3) Impossible (Cor. 1) Impossible (Cor. 3) Possible (Th. 2)

	AC	Impossible (Cor. 2)	Impossible (Th. 1)	Possible (Th. 3)	-
	RE	Impossible (Cor. 3)	Possible (Th. 4)	Impossible (Cor. 3)	-
	BRE	Possible (Th. 5)	-	-	-
	ST	Possible (Cor. 6)	-	-	-

  Algorithm 1 Predicates used in GDG

	LeftWalker() ≡
	stater = lef tW alker
	HeadOrTailWalkerEndDiscovery() ≡
	stater ∈ {headW alker, tailW alker, minT ailW alker} ∧ walkStepsr = n
	HeadOrTailWalker() ≡
	stater ∈ {headW alker, tailW alker, minT ailW alker}
	AllButTwoWaitingWalker() ≡
	|N odeM ate()| = R -3 ∧ ∀r ∈ {r} ∪ N odeM ate(), state r ∈ {waitingW alker, minW aitingW alker}
	WaitingWalker() ≡
	stater ∈ {waitingW alker, minW aitingW alker}
	PotentialMinOrSearcherWithMinWaiting(r') ≡

MinDiscovery() ≡

(stater = potentialM in ∧ ∃r ∈ N odeM ate(), (state r = righter ∧ idr < id r ))∨ ∃r ∈ N odeM ate(), idM in r = idr∨ ∃r ∈ N odeM ate(), (state r ∈ {dumbSearcher, potentialM in}

∧ idr < idP otentialM in r )∨ rightStepsr = 4 * idr * n G E () ≡ |N odeM ate()| = R -1 G EW () ≡ |N odeM ate()| = R -2 ∧

∃r ∈ {r} ∪ N odeM ate(), state r ∈ {minW aitingW alker, minT ailW alker} HeadWalkerWithoutWalkerMate() ≡ stater = headW alker ∧ ExistsEdge(lef t, previous) ∧ ¬HasM oved() ∧ N odeM ateIds() = walkerM ater stater ∈ {potentialM in, dumbSearcher, awareSearcher} ∧ state r = minW aitingW alker RighterWithMinWaiting(r') ≡ stater = righter ∧ state r = minW aitingW alker NotWalkerWithHeadWalker(r') ≡ stater ∈ {righter, potentialM in, dumbSearcher, awareSearcher} ∧ state r = headW alker NotWalkerWithTailWalker(r') ≡ stater ∈ {righter, potentialM in, dumbSearcher, awareSearcher} ∧ state r = minT ailW alker PotentialMinWithAwareSearcher(r') ≡ stater = potentialM in ∧ state r = awareSearcher AllButOneRighter() ≡ |N odeM ate()| = R -2 ∧ ∀r ∈ {r} ∪ N odeM ate(), state r = righter RighterWithSearcher(r') ≡ stater = righter ∧ state r ∈ {dumbSearcher, awareSearcher} PotentialMinOrRighter() ≡ stater ∈ {potentialM in, righter} DumbSearcherMinRevelation() ≡ stater = dumbSearcher ∧ ∃r ∈ N odeM ate(), (state r = righter ∧ id r > idP otentialM inr) DumbSearcherWithAwareSearcher(r') ≡ stater = dumbSearcher ∧ state r = awareSearcher Searcher() ≡ stater ∈ {dumbSearcher, awareSearcher}

  Algorithm 2 Functions used in GDG

	Function StopMoving()
	dirr := ⊥
	Function MoveLeft()
	dirr := lef t
	Function BecomeLeftWalker()
	(stater, dirr) := (lef tW alker, ⊥)
	Function Walk()
	dirr :=	 	⊥	if (idr = idHeadW alkerr ∧ walkerM ater = N odeM ateIds())∨ (idr = idHeadW alkerr ∧ idHeadW alkerr ∈ N odeM ateIds())
			right	otherwise
	walkStepsr := walkStepsr + 1 if dirr = right ∧ ExistsEdge(right, current)
	Function InitiateWalk()
	idHeadW alkerr := max({idr} ∪ N odeM ateIds())
	walkerM ater := N odeM ateIds()
	stater :=	 	headW alker minT ailW alker	if idr = idHeadW alkerr if stater = minW aitingW alker
				tailW alker	otherwise
	Function BecomeWaitingWalker(r')
	(stater, idP otentialM inr, idM inr, dirr) := (waitingW alker, id r , id r , ⊥)
	Function BecomeMinWaitingWalker()
	(stater, idP otentialM inr, idM inr, dirr) := (minW aitingW alker, idr, idr, ⊥)
	Function BecomeAwareSearcher(r')
	(stater, dirr) := (awareSearcher, right)
	(idP otentialM inr, idM inr) :=	(idP otentialM in r , idP otentialM in r ) (idM in r , idM in r )	if state r = dumbSearcher otherwise
	Function BecomeTailWalker(r')
	(stater, idP otentialM inr, idM inr) := (tailW alker, idP otentialM in r , idM in r )
	(idHeadW alkerr, walkerM ater, walkStepsr) := (idHeadW alker r , walkerM ate r , walkSteps r )
	Function MoveRight()
	dirr := right
	rightStepsr := rightStepsr + 1 if ExistsEdge(dir, current)
	Function InitiateSearch()
	idP otentialM inr := min({idr} ∪ N odeM ateIds())
	stater :=		potentialM in dumbSearcher	if idr = idP otentialM inr otherwise
	rightStepsr := rightStepsr + 1 if stater = potentialM in ∧ ExistsEdge(dir, current)
	Function Search()
	dirr :=	 	lef t right	if |N odeM ate()| ≥ 1 ∧ idr = max({idr} ∪ N odeM ateIds()) if |N odeM ate()| ≥ 1 ∧ idr = max({idr} ∪ N odeM ateIds())
			dirr	otherwise

  Therefore, the previous scenario can effectively happen. When r min meets an awareSearcher, it becomes min by definition of the predicate M inDiscovery() of rule M 1 . Therefore, r min becomes min in at most 4 * n rounds if it is stuck more than 4 * n rounds. Second, consider that at the time when r min , as a potentialM in, is stuck more than 4 * n rounds, there exists a righter. In this case, since an isolated righter considers the right direction (Rule M 8 ), and by the arguments of the previous paragraph, either a righter or a robot that is an awareSearcher or that becomes an awareSearcher(Rules M 7 , M 9 or M 10 ) meets r min in at most n rounds. When r min meets a righter or an awareSearcher, it becomes min by definition of the predicate M inDiscovery() of Rule M 1 . Therefore, r min becomes min in at most n rounds if it is stuck more than 4 * n rounds. Now, we give the worst number of rounds needed for r min to become min, in the case where there exists a time t at which Rule M 6 is executed. By Case 1.1, before time t, r min , while it is not yet min, can be stuck min becomes min because it moves during 4 * id rmin * n steps in the right direction. This function is maximal when nb = 0, therefore in at most 16 * id rmin * n 2 rounds r min becomes min because it moves during 4 * id rmin * n steps in the right direction. Now consider the case where r min becomes min because it meets a robot that permits it to deduce that it is min. Once r min is stuck more than 4 * n rounds after time t, we have seen that it becomes min. Since we consider the worst case such that r min does not become min because it moves during 4 * id rmin * n steps in the right direction, this implies that in at most (4 * id rmin * n -1) * 4 * n rounds r min becomes min. Therefore, whatever the situation, Phase M is bounded.Moreover, by Case 1.1 and the previous paragraph, we can conclude that Phase M is in O(id rmin * n 2 ) rounds.

at most n rounds each time it moves from one step in the right direction. Similarly, by the two previous cases (Case 1.2 and 1.3), after time t, r min , while it is not yet min, can be stuck at most 4 * n rounds each time it moves from one step in the right direction. Let nb be the number of steps in the right direction moved by r min before time t. As proved previously, r min is either a righter or a potentialM in before being min. By Lemma 2, this implies that before being min, r min always considers the right direction. Therefore, by the predicate M inDiscovery() of Rule M 1 , in at most nb * n + ((4 * id rmin * n) -nb) * 4 * n rounds, r

  3) * 3 * n additional rounds are needed for Rule Term 2 to be executed. Therefore, in this case, at most n * n + n + 2 * n + (R -3) * 3 * n rounds are needed for either Phase K to be achieved or Rule Term 2 to be executed. Therefore Phase K is bounded. Moreover, by the two previous cases, we can conclude that Phase K is in O(R * n + n 2 ) rounds. Now we consider Phase W of GDG. In this purpose we take back the arguments used in the proof of Lemma 21.Phase W: Here we consider the worst execution in terms of times. Therefore, we consider that Rules Term 1 and Term 2 are executing at the very last moment. The robots r 1 and r 2 that are not involved in T at time t tower are such that state r1 ∈ {righter, potentialM in, dumbSearcher, awareSearcher} and state r2 ∈ {dumbSearcher, awareSearcher}. Therefore, as explained previously, each time the headW alker, or the minT ailW alker / tailW alker robots move from one steps in the right direction, they can be stuck at most during 3 * n rounds, otherwise either Rule Term 1 or Rule Term 2 is executed. Indeed, this is especially the case when the headW alker and the minT ailW alker / tailW alker are stuck on the same node. In fact, it takes at most n rounds for r 1 to be stuck on the other extremity the missing edge. At most n supplementary rounds are needed for r 2 to reach the node where r 1 is stuck (and therefore for one robot to change its direction), and then n other rounds are needed for one of these robots to reach the node where the headW alker and the minT ailW alker / tailW alker are stuck (and thus for Rule Term

2 to be executed). Therefore, Phase W is achieved in at most 2 * n * (3 * n) rounds since the headW alker and the minT ailW alker / tailW alker robots have to move alternatively during n steps to complete Phase W. In other words, Phase W is bounded and is in O(n 2 ) rounds. Now we consider Phase T of GDG. In this purpose we take back the arguments used in the proof of Lemma 21.

By the rules of GDG, a lef tW alker only executes Rule T 1 . While executing this rule, a robot considers the lef t direction and stays a lef tW alker. Since each edge of the footprint of a BRE ring is present at least once every δ units of time, such a robot reaches the node v in at most n * δ rounds. Hence, in this case, Phases W and T take at most 3 * n * δ rounds, hence they are bounded.

By the two previous cases, phase W and Phase T take O(n * δ) rounds. Whatever the BRE ring considered, each phase of GDG is bounded, therefore, GDG solves G in BRE rings. Moreover, GDG solves G in BRE rings in O(n * δ * (id rmin + R)) rounds. Now, we consider the case of ST rings. We know that ST rings are BRE rings such that δ = 1, hence, by Lemma 5, we can deduce the following corollary. Corollary 6. GDG solves G in ST rings in O(n * (id rmin + R)) rounds.

Conclusion

In this paper, we apply for the first time the gracefully degrading approach to robot networks. This approach consists in circumventing impossibility results in highly dynamic systems by providing algorithms that adapt themselves to the dynamics of the graph: they solve the problem under weak dynamics and only guarantee that some weaker but related problems are satisfied whenever the dynamics increases and makes the original problem impossible to solve.

Focusing on the classical problem of gathering a squad of autonomous robots, we introduce a set of weaker variants of this problem that preserves its safety (in the spirit of the indulgent approach that shares the same underlying idea). Motivated by a set of impossibility results, we propose a gracefully degrading gathering algorithm (refer to Table 1 for a summary of our results). We highlight that it is the first gracefully degrading algorithm dedicated to robot networks and the first algorithm focusing on the gathering problem in COT , the class of dynamic graphs that exhibits the weakest recurrent connectivity.

A natural open question arises on the optimality of the graceful degradation we propose. Indeed, we prove that our algorithm provides for each class of dynamic graphs the best specification among the ones we proposed. We do not claim that another algorithm could not be able to satisfy stronger variants of the original gathering specification. Aside gathering in robot networks, defining a general form of degradation optimality seems to be a challenging future work.