Marjorie Bournat

Swan Dubois

Franck Petit

Computability of Perpetual Exploration in Highly Dynamic Rings *

Keywords: Highly dynamic graphs, evolving graphs, perpetual exploration, fully-synchronous robots

We consider systems made of autonomous mobile robots evolving in highly dynamic discrete environment i.e., graphs where edges may appear and disappear unpredictably without any recurrence, stability, nor periodicity assumption. Robots are uniform (they execute the same algorithm), they are anonymous (they are devoid of any observable ID), they have no means allowing them to communicate together, they share no common sense of direction, and they have no global knowledge related to the size of the environment. However, each of them is endowed with persistent memory and is able to detect whether it stands alone at its current location. A highly dynamic environment is modeled by a graph such that its topology keeps continuously changing over time. In this paper, we consider only dynamic graphs in which nodes are anonymous, each of them is infinitely often reachable from any other one, and such that its underlying graph (i.e., the static graph made of the same set of nodes and that includes all edges that are present at least once over time) forms a ring of arbitrary size.

In this context, we consider the fundamental problem of perpetual exploration: each node is required to be infinitely often visited by a robot. This paper analyzes the computability of this problem in (fully) synchronous settings, i.e., we study the deterministic solvability of the problem with respect to the number of robots. We provide three algorithms and two impossibility results that characterize, for any ring size, the necessary and sufficient number of robots to perform perpetual exploration of highly dynamic rings.

Introduction

We consider systems made of autonomous robots that are endowed with visibility sensors and motion actuators. Those robots must collaborate to perform collective tasks, typically, environmental monitoring, large-scale construction, mapping, urban search and rescue, surface cleaning, risky area surrounding, patrolling, exploration of unknown environments, to quote only a few.

Exploration belongs to the set of basic task components for many of the aforementioned applications. For instance, environmental monitoring, patrolling, search and rescue, and surface cleaning are all tasks requiring that robots (collectively) explore the whole area. To specify how the exploration is achieved, the so-called "area" is often considered as "zoned area" (e.g., a building, a town, a factory, a mine, etc.) modeled by a finite graph where (anonymous) nodes represent locations that can be sensed by the robots, and edges represent the possibility for a robot to move from one location to the other.

To fit various applications and environments, numerous variants of exploration have been studied in the literature, for instance, terminating exploration -the robots stop moving after completion of the exploration of the whole graph [START_REF] Devismes | Optimal torus exploration by oblivious robots[END_REF][START_REF] Devismes | Optimal probabilistic ring exploration by semi-synchronous oblivious robots[END_REF][START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF]-, exclusive perpetual exploration -every node is visited infinitely often, but no two robots collide at the same node [START_REF] Baldoni | On the solvability of anonymous partial grids exploration by mobile robots[END_REF][START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF]-, exploration with return -each robot comes back to its initial location once the exploration is completed [START_REF] Diks | Tree exploration with little memory[END_REF] -, etc.. Clearly, some of these variants may be mixed (e.g., exclusive perpetual exploration vs. non exclusive terminating exploration) and either weakened or strengthened (weak perpetual exploration -every node is visited infinitely often by at least one robot [START_REF] Bonnet | Discovering and assessing fine-grained metrics in robot networks protocols[END_REF]-vs. strong perpetual exploration -every node is visited infinitely often by each robot-, etc.). Note that all these instances of exploration are different problems in the sense that, in most of the cases, solutions for any given instance cannot be used to solve another instance. Also, some solutions are designed for specific graph topologies, e.g., ring-shaped [START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF], line-shaped [START_REF] Flocchini | How many oblivious robots can explore a line[END_REF], tree-shaped [START_REF] Flocchini | Remembering without memory: Tree exploration by asynchronous oblivious robots[END_REF], and other for arbitrary network [START_REF] Chalopin | Network exploration by silent and oblivious robots[END_REF]. In this paper, we address the (non-exclusive weak version of the) perpetual exploration problem, i.e., each node is visited infinitely often by a robot.

Robots operate in cycles that include three phases: Look, Compute, and Move (L-C-M). The Look phase consists in taking a snapshot of the (local) environment of robots using the visions capabilities offered by the sensors they are equipped with. The snapshot depends on the sensor capabilities with respect to environment. During the Compute phase, a robot computes a destination based on the previous observation. The Move phase simply consists in moving to this destination. Using L-C-M cycles, several models has been proposed in the literature, capturing various degrees of synchrony between robots [START_REF] Flocchini | Distributed Computing by Oblivious Mobile Robots[END_REF]. They are denoted by FSYN C, SSYN C, and ASYN C, from the stronger to the weaker. In FSYN C (fully synchronous), all robots execute the L-C-M cycle synchronously and atomically. In SSYN C (semi-synchronous), robots are asynchronously activated to perform cycles, yet at each activation, a robot executes one cycle atomically. In ASYN C (asynchronous), robots execute L-C-M in a fully independent manner.

We assume robots having weak capabilities: they are uniform -meaning that all robots follow the same algorithm-, they are anonymous -meaning that no robot can distinguish any two other robots-, they are disoriented -they have no coherent labeling of direction-, and they have no global knowledge related to the size of the environment. Furthermore, the robots have no (direct) means of communicating with each other. However, each of them is endowed with persistent memory and is able to detect whether it stands alone at its current location.

All the aforementioned contributions assume a static environment, i.e., the graph topology explored by the robots does not evolve in function of the time. In this paper, we consider dynamic environments that may change over time, for instance, a transportation network, a building in which doors are closed and open over time, or streets that are closed over time due to work in process or traffic jam in a town. More precisely, we consider dynamic graphs in which edges may appear and disappear unpredictably without any stability, recurrence, nor periodicity assumption. However, to ensure that the problem is not trivially unsolvable, we made the assumption that each node is infinitely often reachable from any other one through a temporal path (a.k.a. journey [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF]). The dynamic graphs satisfying this topological property are known as connected-over-time (dynamic) graphs [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF].

Related work. Recent work [START_REF] Luna | Live exploration of dynamic rings[END_REF][START_REF] Flocchini | Exploration of periodically varying graphs[END_REF][START_REF] Ilcinkas | Exploration of constantly connected dynamic graphs based on cactuses[END_REF][START_REF] Ilcinkas | On the power of waiting when exploring public transportation systems[END_REF][START_REF] Ilcinkas | Exploration of the T-interval-connected dynamic graphs: The case of the ring[END_REF] deal with the terminating exploration of dynamic graphs. This line of work restricts the dynamicity of the graph with various assumptions. In [START_REF] Flocchini | Exploration of periodically varying graphs[END_REF] and [START_REF] Ilcinkas | On the power of waiting when exploring public transportation systems[END_REF], the authors focus on periodically varying graphs, i.e., the presence of each edge of the graph is periodic. In [START_REF] Luna | Live exploration of dynamic rings[END_REF][START_REF] Ilcinkas | Exploration of constantly connected dynamic graphs based on cactuses[END_REF][START_REF] Ilcinkas | Exploration of the T-interval-connected dynamic graphs: The case of the ring[END_REF], the authors assume that the graph is connected at each time instant and that there exists a stability of this connectivity in any interval of time of length T (such assumption is known as T -interval-connectivity [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF]). In [START_REF] Ilcinkas | Exploration of the T-interval-connected dynamic graphs: The case of the ring[END_REF] and [START_REF] Luna | Live exploration of dynamic rings[END_REF] (resp. [START_REF] Ilcinkas | Exploration of constantly connected dynamic graphs based on cactuses[END_REF]), the authors restrict their study to the case where the underlying graph (i.e., the static graph that includes all edges that are present at least once in the lifetime of the graph) forms a ring (resp. a cactus) of arbitrary size.

In [START_REF] Luna | Live exploration of dynamic rings[END_REF], the authors examine the impact of various factors (e.g., at least one node is not anonymous, knowledge of the exact number of nodes, knowledge of an upper bound on the number of nodes, sharing of a common orientation, etc.) on the solvability of the terminating exploration. In particular, they show that the degree of synchrony among the robot has a major impact. Indeed, they prove that, independently of other assumptions, exploration is impossible in SSYN C model (without extra synchronization assumptions). The proof of this result relies on the possibility offered to the adversary to wake up each robot independently and to remove the edge that the robot wants to traverse at this time. Note that, by its simplicity, this impossibility result is applicable to any variante of the exploration problem. It is also independent of dynamicity assumptions.

The first attempt to solve exploration in the most general dynamicity scenario (i.e., connectedover-time assumption) has been proposed in [START_REF] Bournat | Self-stabilizing robots in highly dynamic environments[END_REF]. The authors provide a protocol that deterministically solves the perpetual exploration problem. This protocol operates in any connected-over-time ring with three synchronous robots (accordingly to the aforementioned impossibility result in [START_REF] Luna | Live exploration of dynamic rings[END_REF]). Further, the proposed protocol has the nice extra property of being self-stabilizing, meaning that regardless their arbitrary initial configuration, the robots eventually behave according to their specification, i.e., eventually, they explore the whole network infinitely often. Note that the necessity of the assumption on the number of robots is left as an open question by this work.

Our contribution. The main contribution of this paper is to close this question. Indeed, we analyze the computability of the perpetual exploration problem in connected-over-time (dynamic) rings, i.e., we study the deterministic solvability of the problem with respect to the number of robots. According to the impossibility result in [START_REF] Luna | Live exploration of dynamic rings[END_REF], we restrict this study to the FSYN C model. As we do not consider self-stabilization (contrarily to [START_REF] Bournat | Self-stabilizing robots in highly dynamic environments[END_REF]), we assume that no pair of robots have a common initial location. Moreover, to ensure that the problem is not trivially solved in the initial configuration, we consider that, k, the number of robots, is strictly smaller than n, the number of nodes of the dynamic graph. In this context, we establish the necessary and sufficient number of robots to solve the perpetual exploration for any size of connected-over-time rings (see TABLE 1 for a summary). Note that a connected-over-time chain can be seen as a connected-over-time ring with a missing edge. So, our results are also valid on connected-over-time chains. In more details, we first provide an algorithm that perpetually explores, using a team of k ≥ 3 robots, any connected-over-time ring of n > k nodes. Then, we give two non-trivial impossibility results. We first show that two robots are not sufficient to perpetually explore a connected-overtime ring with a number of nodes strictly greater than three. Next, we show that a single robot cannot perpetually explore a connected-over-time ring with a number of nodes strictly greater than two. Finally, we close the problem by providing an algorithm for each remaining cases (one robot in a 2-node connected-over-time ring and two robots in a 3-node connected-over-time ring).

Outline of the paper. In Section 2, we present formally the model considered in the remainder of the paper. Section 3 presents the algorithm to explore connected-over-time rings of size n > k nodes with k ≥ 3 robots. The impossibility result and the algorithm for two robots are both presented in Section 4. The ones assuming a single robot are given in Section 5. We conclude in Section 6.

Model

In this section, we present our formal model. This model is borrowed from the one of [START_REF] Bournat | Self-stabilizing robots in highly dynamic environments[END_REF] that proposes an extension of the classical model of robot networks in static graphs introduced in [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF] to the context of dynamic graphs.

Dynamic graphs

In this paper, we consider the model of evolving graphs introduced in [START_REF] Xuan | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF]. We hence consider the time as 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 have G i = (V, E i ). We say that the edges of E i are present in G at time i. The underlying graph of G, denoted 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 G such that there exists a time after which this edge is never present in G. A recurrent edge is an edge of E G 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). In this paper, we chose to make minimal assumptions on the dynamicity of our graph since we restrict ourselves on connected-over-time evolving graphs. The only constraint we impose on evolving graphs of this class is that their eventual underlying graph is connected [START_REF] Dubois | Enabling minimal dominating set in highly dynamic distributed systems[END_REF] (this is equivalent with the assumption that each node is infinitely often reachable from another one through a journey). In the following, we consider only connected-over-time evolving graphs whose underlying graph is an anonymous and unoriented ring of arbitrary size. Although the ring is unoriented, to simplify the presentation, we, as external observers, distinguish between the clockwise and the counter-clockwise (global) direction in the ring.

We introduce here some definitions that are used for proofs only. From an evolving graph G = {(V, E 0 ), (V, E 1 ), (V, E 2 ), . . .}, we define the evolving graph G\{(e 1 , τ 1 ), . . . (e k , τ k )} (with for any i ∈ {1, . . . , k}, e i ∈ E and τ i ⊆ N) as the evolving graph {(V, E 0 ), (V, E 1 ), (V, E 2 ), . . .} such that: ∀t ∈ N, ∀e ∈ E G , e ∈ E t ⇔ e ∈ E t ∧ (∀i ∈ {1, . . . , k}, e = e i ∨ t / ∈ τ i ). A node u satisfies the property OneEdge(u, t, t ) if and only if an adjacent edge of u is continuously missing from time t to time t while the other adjacent edge of u is continuously present from time t to time t . We define the distance between two nodes u and v (denoted d(u, v)) by the length of a shortest path between u and v in the underlying graph.

Robots

We consider systems of 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 representing connections through which robots may move from a location to another one at time i. Robots are uniform (they execute the same algorithm), anonymous (they are indistinguishable from each other), and have a persistent memory (they can store local variables). The state of a robot at time t corresponds to the value of its variables at time t. Robots are unable to directly communicate with each other by any means. Robots are endowed with local weak multiplicity detection meaning that they are able to detect if they are alone on their current node or not, but they cannot know the exact number of co-located robots. When a robot is alone on its current node, we say that it is isolated. A tower T is a couple (S, θ), where S is a set of robots (|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 have no a priori knowledge about the ring they explore (size, diameter, dynamicity. . . ). Finally, each robot has its own stable 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 but two different robots may not agree on this labeling). We assume that each robot has a variable dir that stores a direction (either left or right). Initially, this variable is set to lef t. At any time, we say that a robot points to left (resp. right) if its dir variable is equal to this (local) direction. Through misuse of language, we say that a robot points to an edge when this edge is connected to the current node of the robot by the port labeled with its current direction. We say that a robot considers the clockwise (resp. counter-clockwise) direction if the (local) direction pointed to by this robot corresponds to the (global) direction seen by an external observer.

Execution

A configuration γ of the system captures the position (i.e., the node where the robot is currently located) and the state of each robot at a given time. Given an evolving graph G = {G 0 , G 1 , . . .}, an algorithm A, and an initial configuration γ 0 , the execution E of A on G starting from γ 0 is the infinite sequence (G 0 , γ 0 ), (G 1 , γ 1 ), (G 2 , γ 2 ), . . . where, for any i ≥ 0, the configuration γ i+1 is the result of the execution of a synchronous round by all robots from (G i , γ i ) as explained below.

The round that transitions the system from (G i , γ i ) to (G i+1 , γ i+1 ) is composed of three atomic and synchronous phases: Look, Compute, Move. During the Look phase, each robot gathers information about its environment in G i . More precisely, each robot updates the value of the following local predicates: (i) ExistsEdge(dir) returns true if there is an adjacent edge at the current location of the robot on its direction dir, false otherwise; (ii) ExistsOtherRobotsOnCurrentN ode() returns true if there is strictly more than one robot on the current node of the robot, false otherwise. We define the local environment of a robot at a given time as the combination of the values of ExistsEdge(dir), ExistsEdge(dir) (where dir is the opposite direction to dir), and ExistsOtherRobotsOnCurrentN ode() of this robot at this time. The view of the robot at this time gathers its state and its local environment at this time. During the Compute phase, each robot executes the algorithm A that may modify its variable dir depending on its current state and on the values of the predicates updated during the Look phase. Finally, the Move phase consists of moving each robot through one edge in the direction it points to if there exists an edge in that direction, otherwise (i.e., the edge is missing at that time) the robot remains at its current node.

Specification

We define a well-initiated execution as an execution (G 0 , γ 0 ), (G 1 , γ 1 ), (G 2 , γ 2 ), . . . such that γ 0 contains strictly less robots than the number of nodes of G and is towerless (i.e., there is no tower in this configuration).

Given a class of evolving graphs C, an algorithm A satisfies the perpetual exploration specification on C if and only if, in every well-initiated execution of A on every evolving graph G ∈ C, every node of G is infinitely often visited by at least one robot (i.e., a robot is infinitely often located at every node of G). Note that this specification does not require that every robot visits infinitely often every node of G.

With Three or More Robots

This section is dedicated to the more general result: the perpetual exploration exploration of connected-over-time rings of size greater than k with a team of k ≥ 3 robots.

Presentation of the Algorithm

We first describe intuitively the key ideas of our algorithm. Remind that an algorithm controls the move of the robots through their variable direction. Hence, designing an algorithm consists in choosing when we want a robot to keep its direction and when we want it to change its direction (in other words, turn back). The first idea of our algorithm is to require that a robot keeps its direction when it is not involved in a tower (Rule 1). Using this idea, some towers are necessarily formed when there exists an eventual missing edge. Our algorithm reacts as follows to the formation of towers. If at a time t a robot does not move and forms a tower at time t + 1, then the algorithm keeps the direction of the robot (Rule 2). In the contrary case (that is, at time t, the robot moves and forms a tower at time t+1) it changes the direction of the robot (Rule 3).

Let us now explain how the algorithm (Rules 1, 2, and 3) enables the perpetual exploration of any connected-over-time ring. First, note that Rule 1 alone is sufficient to perpetually explore connected-over-time rings without eventual missing edge provided that the robots never meet. The main property induced by Rules 2 and 3 is that any tower is broken in a finite time and that at least one robot of the tower considers each possible direction. This property implies (combined with

Algorithm 1 PEF 3+ 1: if HasM ovedP reviousStep ∧ ExistsOtherRobotsOnCurrentN ode() then 2: dir ← dir 3: end if 4: HasM ovedP reviousStep ← ExistsEdge(dir)
Rule 1) that (i) the algorithm is able to perpetually explore any connected-over-time ring without eventual missing edge (even if robots meet); and that (ii), when the ring contains an eventual missing edge, one robot is eventually located at each extremity of the eventual missing edge and considers afterwards the direction of the eventual missing edge.

Let us consider this last case. We call sentinels the two robots located at extremities of the eventual missing edge. The other robots are called explorers. By Rule 3, an explorer that arrives on a node where a sentinel is located changes its direction. Intuitively, that means that the sentinel signal to the explorer that it has reached one extremity of the eventual missing edge and that it has consequently to turn back to continue the exploration. Note that, by Rule 2, the sentinel keeps its direction (and hence its role). Once an explorer leaves an extremity of the eventual missing edge, we know, thanks to Rule 1 and the main property induced by Rules 2 and 3, that a robot reaches in a finite time the other extremity of the eventual missing edge and that (after the second sentinel/explorer meeting) all the nodes have been visited by a robot in the meantime. As we can repeat this scheme infinitely often, our algorithm is able to perpetually explore any connected-over-time ring with an eventual missing edge, that ends the informal presentation of our algorithm.

Refer to Algorithm 1 for the formal statement of our algorithm called PEF 3+ (standing for Perpetual Exploration in FSYNC with 3 or more robots). In addition of its dir variable, each robot maintains a boolean variable HasM ovedP reviousStep indicating if the robot has moved during its last Look-Compute-Move cycle. This variable is used to implement Rules 2 and 3.

Proof of Correctness

In this section, we prove the correctness of PEF 3+ with k ≥ 3 robots. In the following, we consider a connected-over-time ring G of size at least k + 1. Let ε = (G 0 , γ 0 ), (G 1 , γ 1 ), . . . be any execution of PEF 3+ on G. Lemma 3.1. If there exists an eventual missing edge in G, then at least one tower is formed in ε.

Proof. By contradiction, assume that e is an eventual missing edge of G (such that e is not present in G after time t) and that no tower is formed in ε.

Executing PEF 3+, a robot changes the global direction it considers only when it forms a tower with another robot. As, by assumption, no tower is formed in ε, each robot is always considering the same global direction. All the edges of G, except e, are infinitely often present in G. Hence, any robot reaches one of the extremity of e in finite time after t. As the robots consider a direction at each instant time and that there are at least 3 robots, at least 2 robots consider the same global direction at each instant time. Hence, at least two robots reach the same extremity of e. A tower is formed, leading to a contradiction. Lemma 3.2. If ε does not contain a tower, then every node is infinitely often visited by a robot in ε.

Proof. Assume that there is no tower formed in ε. By Lemma 3.1, if there is an eventual missing edge in G, then there is at least one tower formed. In consequence, all the edges of G are infinitely often present in G.

Executing PEF 3+, a robot changes the global direction it considers only when it forms a tower with another robot. Hence, none of the robots change the global direction it considers in ε. Since all the edges are infinitely often present, each robot moves infinitely often in the same global direction, that implies the result. Lemma 3.3. If a tower T of 2 robots is formed in ε, then these two robots consider two opposite global directions while T exists.

Proof. Assume that 2 robots form a tower at a time t in ε. Let us consider the 2 following cases: Case 1: The two robots consider the same global direction during the Move phase of time t -1. In this case, one robot (denoted r) does not move during the Move phase of time t, while the other (denoted r ) moves and joins the first one on its current node. During the Compute phase of time t, r still considers the same global direction, while r changes the global direction it considers by construction of PEF 3+. Then, the two robots consider two different global directions after the Compute phase of time t. Case 2: The two robots consider two opposite global directions during the Move phase of time t -1. In this case, the two robots move at time t -1. During the Compute phase of time t, the two robots change the global direction they consider by construction of PEF 3+. Hence they consider two different global directions after the Compute phase of time t.

A robot executing PEF 3+ changes its global direction only if it has moved during the previous step. So, the robots of the tower do not change the global direction they consider as long as they are involved in the tower. As the two robots consider two different global directions after the Compute phase of time t, we obtain the lemma. Proof. We prove this lemma by recurrence. As there is no tower in γ 0 by assumption, it remains to prove that, if γ t contains no tower with 3 or more robots, so is γ t+1 . Let us study the following cases: Case 1: γ t contains no tower. The robots can cross at most one edge at each step. Each node has at most 2 adjacent edges in G t , hence the maximum number of robots involved in a tower of γ t+1 is 3. If a tower involving 3 robots is formed in γ t+1 , one robot r has not moved during the Move phase of time t, while the two other robots (located on the two adjacent nodes of its location) have moved to its position. That implies that the two adjacent edges of the node where r is located are present in G t . As any robot considers a global direction at each instant time, r necessarily moves in step t, that is contradictory. Therefore, only towers of 2 robots can be formed in γ t+1 . Case 2: γ t contains towers of at most 2 robots. Let T be a tower involving 2 robots in γ t and u be the node where T is located in γ t . By Lemma 3.3, the 2 robots of T consider two opposite global directions in γ t .

Consider the 3 following sub-cases: (i) If there is no adjacent edge to u in G t , then no other robot can increase the number of the robots involved in the tower. (ii) If there is only one adjacent edge to u in G t , then only one robot may traverse this edge to increase the number of robots involved in T . Indeed, if there are multiple robots on an adjacent node to u, then these robots are involved in a tower T of 2 robots (by assumption on γ t ) and they are considering two opposite global directions in γ t . However, as an adjacent edge to u is present in G t and as the robots of T are considering two opposite global directions, then one robot of T leaves T at time t. In other words, even if a robot of T moves on u, one robot of T leaves u. Then, there is at most 2 robots on u in γ t+1 . (iii) If there are two adjacent edges to u in γ t , then, using similar arguments as above, we can prove that only one robot crosses each of the adjacent edges of u. Moreover, the robots of T move in opposite global directions and leave u, implying that at most 2 robots are present on u in γ t+1 . Lemma 3.5. If G has no eventual missing edge and ε contains towers then every node is infinitely often visited by a robot in ε.

Proof. Assume that G has no eventual missing edge and ε contains towers.

We want to prove the following property. If during the Look phase of time t, a robot r is located on a node u considering the global direction gd, then there exists a time t ≥ t such that, during the Look phase of time t , a robot is located on the node v adjacent to u in the global direction gd and considers the global direction gd.

Let t" ≥ t be the smallest time after time t where the adjacent edge of u in the global direction gd is present in G. As all the edges of G are infinitely often present, t" exists. (i) If r crosses the adjacent edge of u in the global direction gd during the Move phase of time t", then the property is verified. (ii) If r does not cross the adjacent edge of u in the global direction gd, this implies that r changes the global direction it considers during the Look phase of time t. While executing PEF 3+, a robot changes its global direction when it forms a tower with another robot. Therefore, at time t, r forms a tower with a robot r . By Lemmas 3.4 and 3.3, two robots involved in a tower consider two opposite global directions. Hence, after the Compute phase of time t, r considers the global direction gd. A robot executing PEF 3+ does not change the global direction it considers until it moves. So, r considers the global direction gd during the Move phase of time t". Hence, during the Look phase of time t" + 1, r is on node v and considers the global direction gd.

By applying recurrently this property to any robot, we prove that all the nodes are infinitely often visited. Lemma 3.6. If G has an eventual missing edge e (such that e is missing forever after time t) and, during the Look phase of a time t ≥ t, a robot considers a global direction gd and is located on a node at a distance d = 0 in U ω G from the extremity of e in the global direction gd, then it exists a time t" ≥ t such that, during the Look phase of time t", a robot is on a node at distance d -1 in U ω G from the extremity of e in the global direction gd and considers the global direction gd.

Proof. Assume that G has an eventual missing edge e (such that e is missing forever after time t) and that, during the Look phase of time t ≥ t, a robot r considers a global direction gd and is located on a node u at distance d = 0 in U ω G from the extremity of e in the global direction gd. Let v be the adjacent node of u in the global direction gd.

Let t" ≥ t be the smallest time after time t where the adjacent edge of u in the global direction gd is present in G. As all the edges of G except e are infinitely often present and as u is at a distance d = 0 in U ω G from the extremity of e in the global direction gd, then the adjacent edge of u in the global direction gd is infinitely often present in G. Hence, t" exists. (i) If r crosses the adjacent edge of u in the global direction gd during the Move phase of time t", then the property is verified. (ii) If r does not cross the adjacent edge of u in the global direction gd, this implies that r changes the global direction it considers during the Look phase of time t. While executing PEF 3+ a robot changes the global direction it considers when it forms a tower with another robot. Therefore, at time t, r forms a tower with a robot r . By Lemmas 3.4 and 3.3, two robots involved in a tower consider two opposite global directions. Hence, after the Compute phase of time t, r considers the global direction gd. A robot executing PEF 3+ does not change the global direction it considers until it moves. Therefore, r considers the global direction gd during the Move phase of time t". Hence, during the Look phase of time t" + 1, r is on node v and considers the global direction gd.

Lemma 3.7. If G has an eventual missing edge e, then eventually one robot is forever located on each extremity of e pointing to e.

Proof. Assume that G has an eventual missing edge e such that e is missing forever after time t.

First, we want to prove that a robot reaches one of the extremities of e in a finite time after t and points to e at this time. If it is not the case at time t, then there exists at this time a robot considering a global direction gd and located on a node u at distance d = 0 in U ω G from the extremity of e in the global direction gd. By applying d times Lemma 3.6, we prove that, during the Look phase of a time t ≥ t, a robot (denote it r) reaches the extremity of e in the global direction gd from u (denote it v and let v be the other extremity of e), and that this robot considers the global direction gd. Let us consider the following cases: Case 1: r is isolated on v at time t . In this case, by construction of PEF 3+, r does not change, during the Compute phase of time t , the global direction that it considers during the Move phase of time t -1. Moreover, a robot can change the global direction it considers only if it moves during the previous step. All the edges of G except e are infinitely often present. As, at time t , r points to e, it cannot move. Therefore, from time t , r does not move and does not change the global direction it considers. Then, r remains located on v forever after t considering gd. Case 2: r is not isolated on v at time t . By Lemmas 3.4, r forms a tower with only one another robot r . By Lemmas 3.4 and 3.3, two robots that form a tower consider two opposite global directions. Hence, either r or r considers the global direction gd while the other one consider the global direction gd. As all the edges of G except e are infinitely often present, then in finite time either r or r leaves v. We can now apply the same arguments than in Case 1 to the robot that stays on v to prove that this robot remains located on v forever after t considering gd.

In both cases, a robot remains forever on v considering gd after t . Assume without loss of generality that it is r. Let us consider the two following cases: Case A: It exists r = r considering gd at time t . We can apply recurrently Lemma 3.6, and the arguments above to prove that a robot is eventually forever located on v considering gd. the execution of this algorithm on the evolving graph to which the sequence converges. This result is useful since it allows us to construct counter-example in the context of impossibility results. Indeed, it is sufficient to construct an evolving graphs sequence (with ever-growing common prefixes) and to prove that their corresponding execution violates the specification of the problem for ever-growing time to exhibit an execution that never satisfies the specification of the problem.

(i,a)=1 i 2 '=f 2 ' a 2 ' i 1 '=f 1 ' a 1 ' a G G' i 1 '=f 1 ' a 1 ' i 2 '=f 2 ' a 2 ' i f=a G G' a 1 '=f 1 ' i 1 ' a 2 '=f 2 ' i 2 ' f=a i G G' f 2 '=a 2 ' i 2 ' f 1 '=a 1 ' i 1 ' G G' i=f and d(i,a)=0 i=f i=f=a i 1 '=f 1 '=a 1 ' i 2 '=f 2 '=a 2 ' R R R R
In order to build the evolving graphs sequence suitable for the proof of our impossibility result, we need the following technical lemma. Lemma 4.1. Let A be a perpetual exploration algorithm in connected-over-time ring of size 4 or more using 2 robots. Any execution of A satisfies: For any time t and any robot state s, if, at time t, the robots have not explored the whole ring, have not formed a tower, and each robot has only visited at most two adjacent nodes, then there exists t ≥ t such that a robot located on a node u, on state s at time t, and satisfying OneEdge(u, t, t ) leaves u at time t .

Proof. Consider an algorithm A that deterministically solves the perpetual exploration problem for connected-over-time rings of size 4 or more using two robots. Let G = {G 0 = (V, E 0 ), G 1 = (V, E 1 ), . . .} be a connected-over-time ring (of size 4 or more). Let ε be an execution of A by two robots r 1 and r 2 on G.

By contradiction, assume that there exists a time t and a state s such that (i) the exploration of the whole ring has not been done yet; (ii) from time 0 to time t none of the robots have formed a tower; (iii) at time t each robot has only visited at most two adjacent nodes of G; and (iv) at time t one of the robot (without lost of generality, r 1 ) is in a state s such that, for any t ≥ t, if r 1 is on a node u of G satisfying OneEdge(u, t, t ), then it does not leave u at time t .

Let R be the set of nodes visited by r 1 from time 0 to time t. Note that, at time t, as each robot has only visited at most two adjacent nodes, then 1 ≤ |R| ≤ 2. Let i (resp. f ) be the node in G where r 1 is located at time 0 (resp. t). If |R| = 2, let a be the node of R such that a = i, otherwise (i.e., |R| = 1) let a = i. By assumption, either f = i or f is an adjacent node of i and in this later case a = f . We construct a connected-over-time ring G = {G 0 , G 1 , . . .} (with G i = (V , E i ) for any i ∈ N) such that the underlying graph of G contains 8 nodes in the following way. Let i 1 be an arbitrary node of G . Let us construct nodes i 2 , a 1 , a 2 , f 1 , and f 2 of G in function of i 1 and of nodes i, a, and f of G as explained by Figure 1. Note that this construction ensures that f 1 and f 2 are adjacent in G in any case.

We denote by r(k) (resp. l(k)) the adjacent edge in the clockwise (resp. counter clockwise) direction of a node k. For any j ∈ {0, . . . , t -1}, let E j be the set E G with the following set of additional constraints1 :

       r(i 1 ) ∈ E j and l(i 2 ) ∈ E j iff r(i) ∈ E j l(i 1 ) ∈ E j and r(i 2 ) ∈ E j iff l(i) ∈ E j r(a 1 ) ∈ E j and l(a 2 ) ∈ E j iff r(a) ∈ E j l(a 1 ) ∈ E j and r(a 2 ) ∈ E j iff l(a) ∈ E j
For any j ≥ t, let E j be the set E G \ {(f 1 , f 2 )}. Now, we consider the execution ε of A on G starting from the configuration where r 1 (resp. r 2 ) is on node i 1 (resp. on node i 2 ) such that the two robots have opposite chirality and that r 1 have the same chirality as in ε. The execution ε satisfies the following set of claims. Claim 1: Until time t, r 1 and r 2 execute the same actions in a symmetrical way in ε . Consider that, during the Look phase of time j, the two robots have the same view in ε . The two robots have not the same chirality and A is deterministic, then, during the Move phase of time j, they are executing the same action in a symmetrical way (either not move or move in opposite directions). This implies that, at time j + 1, r 1 and r 2 have again the same state. There are only two robots executing A on G . Hence, if a tower is formed, it is composed of r 1 and r 2 . If from time 0 to time t, the robots are executing the same actions in a symmetrical way, then, by construction of G and by the way we initially placed r 1 and r 2 on ε , the two robots see the same local environment at each instant time in {0, . . . , t}. At time 0, by construction of G and by the way we placed r 1 and r 2 on ε , the two robots have the same view. By recurrence and using the arguments of the two first paragraphs, we conclude that, from time 0 to time t, r 1 and r 2 execute the same actions in a symmetrical way in ε . Claim 2: Until time t, r 1 and r 2 never form a tower in ε . By construction of ε , the two robots are initially at an odd distance. By Claim 1, at a time 0 < j + 1 < t, the two robots are either at the same distance, at a distance increased of 2, or at a distance decreased of 2 with respect to their distance at time j. Moreover, since G possesses an even number of edges, this implies that, until time t, the robots are always at an odd distance from each other. Claim 3: Until time t, r 1 executes in ε the same sequence of actions than in ε. Consider that, during the Look phase of time j, r 1 has the same view in ε and in ε . As A is deterministic, then, during the Move phase of time j, r 1 executes the same action (either not move, or move in the same direction) in ε and in ε . This implies that, during the Look phase of time j + 1, r 1 possesses the same state in ε and in ε . By assumption, until time t, there is no tower in ε. By Claim 2, there is no tower in ε until time t. Hence, in the case where r 1 executes the same actions in ε and in ε from time 0 to time t, r 1 sees the same local environment in ε and in ε until time t (by construction of G and the initial location of r 1 in ε ). At time 0, r 1 has the same view in ε and in ε (by construction of G and the initial location of r 1 in ε ). By recurrence and using the arguments of the two first paragraphs, we conclude that, from time 0 to time t, r 1 executes the same actions in ε and in ε . Claim 4: At time t, r 1 and r 2 are on two adjacent nodes in ε and are both in state s. By Claims 1 and 3 and by construction of G , we know that at time t, r 1 is on node f 1 while r 2 is on node f 2 . These nodes are adjacent by construction of G . By Claim 1, as r 1 and r 2 have opposite chirality, they have the same state at time t in ε . By Claim 3, r 1 is in the same state at time t in ε and in ε . Since r 1 is in state s at time t in ε by assumption, we have the claim.

By construction of G , f 1 (resp. f 2 ) satisfies the property OneEdge(f 1 , t, +∞) (resp. OneEdge(f 2 , t, +∞)). Then, by assumption, r 1 (resp. r 2 ) does not leave node f 1 (resp. f 2 ) after time t. As G counts 8 nodes, we obtain a contradiction with the fact that A is a deterministic algorithm solving the perpetual exploration problem for connected-over-time rings using two robots. Theorem 4.1. There exists no deterministic algorithm satisfying the perpetual exploration specification on the class of connected-over-time rings of size 4 or more with two fully synchronous robots.

Proof. By contradiction, assume that there exists a deterministic algorithm A satisfying the perpetual exploration specification on any connected-over-time ring of size 4 or more with two robots r 1 and r 2 .

Consider the connected-over-time graph G whose underlying graph U G is a ring of size strictly greater than 3 such that all the edges of U G are present at each time.

Consider three nodes u, v and w of G, such that node v is the adjacent node of u in the clockwise direction, and w is the adjacent node of v in the clockwise direction. We denote respectively e ur and e ul the clockwise and counter clockwise adjacent edges of u, e vr and e vl the clockwise and counter clockwise adjacent edges of v, and e wr and e wl the clockwise and counter clockwise adjacent edges of w. Note that e ur = e vl and e vr = e wl .

Let ε be the execution of A on G starting from the configuration where r 1 (resp. r 2 ) is located on node u (resp. v).

We construct a sequence of connected-over-time graphs (G n ) n∈N such that G 0 = G and for any i ≥ 0, G i is defined as follows (denote by ε i the execution of A on G i starting from the same configuration as ε). We define inductively G i+1 , G i+2 , G i+3 , and G i+4 using Items 1-8 above (see also Figure 2) under the assumption that: (i) G i exists for a given i ∈ N multiple of 4; (ii) G i is a connected-over-time ring; (iii) there exists a time t i such that each robot has only visited at most two adjacent nodes among {u, v, w} in ε i ; (iv) before time t i , the two robots never form a tower in ε i ; and (v) at time t i , r 1 (resp. r 2 ) is located on node u (resp. v).

1. Due to assumptions (ii) to (v), Lemma 5.1 implies that there exists a time t i ≥ t i such that r 2 leaves v at time t i if r 2 is located on node v at time t i and v satisfies OneEdge(v, t i , t i ).

We then define G i+1 such that U G i+1 = U G i and G i+1 = G i \{(e ul , {t i , . . . , t i }), (e vl , {t i , . . . , t i })}.

Note that G i and G i+1 are indistinguishable for robots before time t i . This implies that, at time t i , r 1 (resp. r 2 ) is on node u (resp. v) in ε i+1 . By construction of t i , r 2 leaves v at time t i in ε i+1 . Since, at time t i , among the adjacent edges of v, only e vr is present in G i+1 , r 2 crosses this edge at this time in ε i+1 . Hence, at time t i + 1, r 2 is on node w in ε i+1 . Note that none of the adjacent edges of r 1 are present between time t i and time t i in G i . That implies that, at time t i + 1, r 1 is still on node u in ε i+1 . Moreover, this construction ensures us that assumptions (iii) and (iv) are satisfied in ε i+1 until time t i + 1. Finally, G i+1 is a connected-over-time ring (since it is indistinguishable from G after t i + 1) and hence satisfies assumption (ii).

2. Let t i+1 = t i + 1.

3. Using similar arguments as in Item 1, we prove that there exists a time t i+1 such that r 1 leaves u at time t i+1 if r 1 is on node u at time t i+1 and u satisfies OneEdge(u, t i+1 , t i+1 ). We define G i+2 such that U G i+2 = U G i+1 and G i+2 = G i+1 \{(e ul , {t i+1 , . . . , t i+1 }), (e wl , {t i+1 , . . . , t i+1 }), (e wr , {t i+1 , . . . , t i+1 })}.

That implies that, at time t i+1 +1, r 1 (resp. r 2 ) is on node v (resp. w) in ε i+2 and that assumptions (ii), (iii), and (iv) are satisfied in ε i+2 until time t i+1 + 1.

4. Let t i+2 = t i+1 + 1.

5. Using similar arguments as in Item 1, we prove that there exists a time t i+2 such that r 1 leaves v at time t i+2 if r 1 is on node v at time t i+2 and v satisfies OneEdge(v, t i+2 , t i+2 ). We define G i+3 such that U G i+3 = U G i+2 and such that G i+3 = G i+2 \{(e wl , {t i+2 , . . . , t i+2 }), (e wr , {t i+2 , . . . , t i+2 })}.

That implies that, at time t i+2 +1, r 1 (resp. r 2 ) is on node u (resp. w) in ε i+3 and that assumptions (ii), (iii), and (iv) are satisfied in ε i+3 until time t i+2 + 1.

6. Let t i+3 = t i+2 + 1.

7. Using similar arguments as in Item 1, we prove that there exists a time t i+3 such that r 2 leaves w at time t i+3 if r 2 is on node w at time t i+3 and w satisfies OneEdge(w, t i+3 , t i+3 ). We define G i+4 such that U G i+4 = U G i+3 and such that G i+4 = G i+3 \{(e ul , {t i+3 , . . . , t i+3 }), (e ur , {t i+3 , . . . , t i+3 }), (e wr , {t i+3 , . . . , t i+3 })}.

That implies that, at time t i+3 + 1, r 1 (resp. r 2 ) is on node u (resp. v) in ε i+4 and that assumptions (ii), (iii), and (iv) are satisfied in ε i+4 until time t i+3 + 1.

Let t

i+4 = t i+3 + 1.
Note that G 0 trivially satisfies assumptions (i) to (v) for t 0 = 0 (since ε 0 = ε by construction). Also, given a G i with i ∈ N multiple of 4, G i+4 exists and we proved that it satisfies assumptions (ii) to (v). In other words, (G n ) n∈N is well-defined.

We define the evolving graph G ω such that U Gω = U G 0 and Note that, for any edge of G ω , the intervals of times where this edge is absent (if any) are finite and disjoint. This edge is so infinitely often present in G ω . Therefore, G ω is a connected-over-time ring.

G ω = G 0 \{ (e ul ,
For any i ∈ N, G i and G ω have a common prefix until time t i . As the sequence (t n ) n∈N is increasing by construction, this implies that the sequence (G n ) n∈N converges to G ω .

Applying the theorem of [START_REF] Braud-Santoni | The next 700 impossibility results in time-varying graphs[END_REF], we obtain that, until time t i , the execution of A on G ω is identical to the one on G i . This implies that, executing A on G ω (of size strictly greater than 3), r 1 and r 2 only visit the nodes u, v, and w. This is contradictory with the fact that A satisfies the perpetual exploration specification on connected over time rings of size strictly greater than 3 using two robots.

Connected-over-time Rings of Size 3

In this section, we present PEF 2, a deterministic algorithm solving the perpetual exploration on connected-over-time rings of size 3 with two robots.

This algorithm works as follows. Each robot disposes only of its dir variable. If at a time t, a robot is isolated on a node with only one adjacent edge, then it points to this edge. Otherwise (i.e., none of the adjacent edge is present, both adjacent edges are present, or the other robot is present on the same node), the robot keeps its current direction. Theorem 4.2. PEF 2 is a perpetual exploration algorithm for the class of connected-over-time rings of 3 nodes using 2 fully synchronous robots.

Proof. Consider any execution of PEF 2 on any connected-over-time ring of size 3 with 2 robots. By the connected-over-time assumption, each node has at least one adjacent edge infinitely often present. This implies that any tower is broken in finite time (as robots meet only when they consider opposite directions and move as soon as it is possible). Two cases are now possible. Case 1: There exists infinitely often a tower in the execution. Note that, if a tower is formed at a time t, then the three nodes have been visited between time t -1 and time t. Then, the three nodes are infinitely often visited by a robot in this case. Case 2: There exists a time t after which the robots are always isolated. By contradiction, assume that there exists a time t such that a node u is never visited after t . As the ring has 3 nodes, that implies that, after time max{t, t }, either the robots are always switching their position or they stay on their respective nodes. In the first case, during the Look phase of each time greater than max{t, t }, the respective variables dir of the two robots contain the direction leading to u (since it previously move in this direction). As at least one of the adjacent edges of u is infinitely often present, a robot crosses it in a finite time, that is contradictory with the fact that u is not visited after t . The second case implies that both adjacent edges to the location of both robots are always absent after time t (since a robot moves as soon as it is possible), that is contradictory with the connectedover-time assumption.

In both cases, PEF 2 satisfies the perpetual exploration specification.

With One Robot

This section leads a similar study than the one of Section 4 but in the case of the perpetual exploration of rings of any size with a single robot. Again, we first prove a negative result since Theorem 5.1 states that a single robot is not able to perpetually explore connected-over-time rings of size strictly greater than 2. We then provide PEF 1 (see Theorem 5.2), an algorithm using a single robot that solves the perpetual exploration on connected-over-time rings of size 2.

Connected-over-time Rings of Size 3 and More

Similarly to the previous section, the proof of our impossibility result presented in Theorem 5.1 is based on the construction of an adequate sequence of evolving graphs and the application of the generic framework proposed in [START_REF] Braud-Santoni | The next 700 impossibility results in time-varying graphs[END_REF].

In order to build the evolving graphs sequence suitable for the proof of our impossibility result, we need the following technical lemma. Lemma 5.1. Let A be a perpetual exploration algorithm in connected-over-time ring of size 3 or more using one robot. Any execution of A satisfies: For any time t and any robot state s, there exists a time t ≥ t such that a robot located on a node u, on state s at time t, and satisfying OneEdge(u, t, t ) leaves u at time t .

Proof. Consider an algorithm A that solves deterministically the perpetual exploration problem for connected-over-time rings of size 3 or more using a single robot. Let G = {G 0 = (V, E 0 ), G 1 = (V, E 1 ), . . .} be a connected-over-time ring (of size 3 or more). Let ε be an execution of A on G by a robot r.

By contradiction, assume that it exists a time t and a state s such that, for any t ≥ t, a robot r located on a node u of G and in state s at time t with u satisfying OneEdge(u, t, t ) does not leave u at time t .

Let e be an arbitrary adjacent edge to u. Let us define the connected-over-time ring

G = {G 0 = (V, E 0 ), G 1 = (V, E 1 ), . . .} such that: E i = E i if i < t E i = E G \ {e} if i ≥ t
Let ε be the execution of A on G starting from the same configuration than ε.

As A is a deterministic algorithm, r is in the state s and is located on node u at time t in ε by construction of G . Note that the node u satisfies the property OneEdge(u, t, +∞) in G .

Then, by assumption, r does not leave u in ε after time t. This implies that, after time t, only u is visited in ε . As G counts 3 or more nodes, we obtain a contradiction with the fact that A is a deterministic algorithm solving the perpetual exploration problem for connected-over-time rings using a single robot. Theorem 5.1. There exists no deterministic algorithm satisfying the perpetual exploration specification on the class of connected-over-time rings of size 3 or more with a single fully synchronous robot.

Proof. By contradiction, assume that there exists a deterministic algorithm A satisfying the perpetual exploration specification on any connected-over-time ring of size 3 or more with a single robot r.

Consider the connected-over-time graph G whose underlying graph U G is a ring of size strictly greater than 2 such that all the edges of U G are present at each time. Consider any node u of G and denote respectively by e ur and e ul the clockwise and counter clockwise adjacent edges of u.

Let ε be the execution of A on G starting from the configuration where r is located on node u.

We construct a sequence of connected-over-time graphs (G n ) n∈N such that G 0 = G and for any i ≥ 0, G i is defined as follows (denote by ε i the execution of A on G i starting from the same configuration as ε). We define inductively G i+1 and G i+2 using Items 1-4 above (see also Figure 3) under the assumption that: (i) G i exists for a given i ∈ N even; (ii) G i is a connected-over-time ring; and (iii) there exists a time t i such that r is located on node u at time t in ε i .

1. Due to assumptions (ii) and (iii), Lemma 5.1 implies that there exists a time t i ≥ t i such that r leaves u at time t i if it is located on node u at time t i and u satisfies OneEdge(u, t i , t i ).

We then define G i+1 such that U G i+1 = U G i and G i+1 = G i \{(e ur , {t i , . . . , t i })}.

Note that G i and G i+1 are indistinguishable for r before time t i . This implies that, at time t i , r is located on node u in ε i+1 . By construction of t i , r leaves u at time t i in ε i+1 . Since, at time t i , among the adjacent edges of u, only e ul is present in G i+1 , r crosses this edge at this time in ε i+1 . Then, at time t i + 1, r is located on node v (the node adjacent to u in the counter clockwise direction) in ε i+1 . Finally, G i+1 is a connected-over-time ring (since it is indistinguishable from G after t i + 1) and hence satisfies assumption (ii). Denote respectively by e vr and e vl the clockwise and counter clockwise adjacent edges of v. We have e ul = e vr .

2. Let t i+1 = t i + 1.

3. Using similar arguments as in Item 1, we prove that there exists a time t i+1 such that r leaves v at time t i+1 if r is located on node v at time t i+1 and v satisfies OneEdge(v, t i+1 , t i+1 ). We define G i+2 such that U G i+2 = U G i+1 and G i+2 = G i+1 \{(e vl , {t i+1 , . . . t i+1 })}.

That implies that, at time t i+1 + 1, r is on node u in ε i+2 and that assumptions (ii) and (iii) are satisfied in ε i+2 until time t i+1 + 1.

Let t

i+2 = t i+1 + 1.
Note that G 0 trivially satisfies assumptions (i) to (iii) for t 0 = 0 (since ε 0 = ε by construction). Also, given a G i with i ∈ N even, G i+2 exists and we proved that it satisfies assumptions (ii) and (iii). In other words, (G n ) n∈N is well-defined.

We define the evolving graph G ω such that U Gω = U G 0 and G ω = G 0 \{(e ur , {t 2i , . . . t 2i }), (e vl , {t 2i+1 , . . . , t 2i+1 })|i ∈ N} Note that, for any edge of G ω , the intervals of times where this edge is absent (if any) are finite and disjoint. This edge is so infinitely often present in G ω . Therefore, G ω is a connected-over-time ring.

For any i ∈ N, G i and G ω have a common prefix until time t i . As the sequence (t n ) n∈N is increasing by construction, this implies that the sequence (G n ) n∈N converges to G ω .

Applying the theorem of [START_REF] Braud-Santoni | The next 700 impossibility results in time-varying graphs[END_REF], we obtain that, until time t i , the execution of A on G ω is identical to the one on G i . This implies that, executing A on G ω (of size strictly greater than 2), r only visits the nodes u and v. This is contradictory with the fact that A satisfies the perpetual exploration specification on connected over time rings of size strictly greater than 2 using one robot.

Connected-over-time Rings of Size 2

In this section, we present PEF 1, a deterministic algorithm solving the perpetual exploration on connected-over-time rings of size 2 with a single robot.

Note that a ring of size 2 can be defined in two different ways. If we consider that the graph must remain simple, such a ring is reduced to a 2-node chain (i.e., only one bidirectional edge links the two nodes). Otherwise (i.e., the graph may be not simple), the two nodes are linked by two bidirectional edges. In both cases, the following algorithm, PEF 1, trivially works as follow: As soon as at least one adjacent edge to the current node of the robot is present, its variable dir points arbitrarily to one of these edges.

Theorem 5.2. PEF 1 is a perpetual exploration algorithm for the class of connected-over-time rings of 2 nodes using a single fully synchronous robot.

Conclusion

We analyzed the computability of the perpetual exploration problem on highly dynamic rings. We proved that three (resp., two) robots with very few capacities are necessary to solve the perpetual exploration problem on connected-over-time rings that include strictly more than three (resp., two) nodes. For the completeness of our work, we provided three algorithms: One for a single robot evolving in a 2-node ring, one for two robots exploring three nodes, and one for three or more robots moving among at least four nodes. These three algorithms allow to show that the necessary number of robots is also sufficient to solve the problem.

Lemma 3 . 4 .

 34 No tower of ε involves 3 robots or more.

Figure 1 :

 1 Figure 1: Construction of G in proof of Lemma 4.1.

Figure 2 :

 2 Figure 2: Construction of G i+1 , G i+2 , G i+3 , and G i+4 in proof of Theorem 4.1.

Figure 3 :

 3 Figure 3: Construction of G i+1 and G i+2 in proof of Theorem 5.1.

Table 1 :

 1 Overview of the results

	Number of Robots Size of Rings	Results
	3 and more	≥ 4	Possible (Theorem 3.1)
	2	> 3 = 3	Impossible (Theorem 4.1) Possible (Theorem 4.2)
	1	> 2 = 2	Impossible (Theorem 5.1) Possible (Theorem 5.2)

  {t 4i , . . . , t 4i } ∪ {t 4i+1 , . . . t 4i+1 } ∪ {t 4i+3 , . . . , t 4i+3 }), (e vl , {t 4i , . . . , t 4i } ∪ {t 4i+3 , . . . , t 4i+3 }), (e wl ,{t 4i+1 , . . . , t 4i+1 } ∪ {t 4i+2 , . . . , t 4i+2 }), (e wr ,{t 4i+1 , . . . , t 4i+1 } ∪ {t 4i+2 , . . . , t 4i+2 } ∪ {t 4i+3 , . . . , t 4i+3 })|i ∈ N}

Note that the construction of i 1 , i

, a 1 , a 2 , f 1 , and f 2 ensures us that there is no contradiction between these constraints in all cases.

* This work was performed within Project ESTATE (Ref. ANR-16-CE25-0009-03), supported by French state funds managed by the ANR (Agence Nationale de la Recherche).

Case B: All robots r = r considers gd at time t. We can apply recurrently Lemma 3.6 to prove that, in finite time, a robot forms a tower with r on v. Then, by construction of PEF 3+, this robot consider gd after the Compute phase of this time (and hence during the Look phase of the next time). We then come back to Case A.

In both cases, the lemma holds.

Lemma 3.8. If G has an eventual missing edge and ε contains towers, then every node is infinitely often visited.

Proof. Assume that G has an eventual missing edge e that is missing forever after time t. By Lemma 3.7, there exists a time t ≥ t after which two robots r 1 and r 2 are respectively located on the two extremities of e and pointing to e. As there are at least 3 robots, let r be a robot (located on a node u considering a global direction gd) such that r = r 1 and r = r 2 . Let v be the extremity of e in the direction gd of u and v be the other extremity of e.

Applying recurrently Lemma 3.6, we prove that, in finite time, all the nodes between node u and v in the global direction gd are visited and that a robot reaches v. When this robot reaches v, it changes its direction (hence considers gd) by construction of PEF 3+ since it moves during the previous step and forms a tower.

We can then repeat this reasoning (with v and v alternatively in the role of u and with v and v alternatively in the role of v) and prove that all nodes are infinitely often visited. Lemmas 3.2, 3.5, and 3.8 directly imply the following result: Theorem 3.1. PEF 3+ is a perpetual exploration algorithm for the class of connected-over-time rings of arbitrary size strictly greater than the number of robots using an arbitrary number (greater than or equal to 3) of fully synchronous robots.

With Two Robots

In this section, we study the perpetual exploration of rings of any size with two robots. We first prove that two robots are not able to perpetually explore connected-over-time rings of size strictly greater than three (refer to Theorem 4.1). Then, we provide PEF 2 (see Theorem 4.2), an algorithm using two robots that solves the perpetual exploration on the remaining case, i.e., connected-over-time rings of size three.

Connected-over-Time Rings of Size 4 or More

The proof of our impossibility result presented in Theorem 4.1 makes use of a generic framework proposed in [START_REF] Braud-Santoni | The next 700 impossibility results in time-varying graphs[END_REF]. Note that, even if 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, its proof only relies on the determinism of algorithms and indistinguishability of dynamic graphs, these arguments being directly translatable in our model. We present briefly this framework here. The interested reader is referred to [START_REF] Braud-Santoni | The next 700 impossibility results in time-varying graphs[END_REF] for more details.

This framework is based on a theorem that ensures 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