Keywords: distributed computing, CORDA model, graph searching, gathering, graph exploration

A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled. We present a unified approach to solve three important problems in the field: the exclusive perpetual exploration, the exclusive perpetual graph searching and the gathering problems. In the first problem, each robot aims at visiting each node infinitely often; in perpetual graph searching, the team of robots aims at clearing all edges of the network infinitely often; and in the gathering problem, all robots must eventually occupy the same node. We investigate these tasks in the famous CORDA distributed computing model where the robots cannot communicate but can perceive the positions of other robots. More precisely, each robot is equipped with visibility sensors and motion actuators, and it operates in Look-Compute-Move asynchronous cycles. In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it eventually moves to this neighbor (Move). Moreover, robots are endowed with very weak capabilities. Namely, they are anonymous, oblivious, uniform (execute the same algorithm) and have no common sense of orientation. For the first two problems, the exclusivity constraint must also be satisfied, i.e., a node can be occupied by at most one robot. Finally, the robots have the local multiplicity detection capability which is required to solve the gathering problem. In this setting, we devise algorithms that, starting from any exclusive rigid (i.e. aperiodic and asymmetric) configuration, solve the three above mentioned problems in anonymous ring-topologies. Our main algorithms consist of two phases. The first phase is common to all problems and allows k > 2 robots to achieve a particular configuration in an n-node ring, k < n -2. The second phase consists of two distinct sub-procedures: one works for 5 ≤ k < n -3 robots, n ≥ 10 (but for k = 5 and n = 10), and solves both the exploration and graph searching problems and the second one solves the gathering problem for any n and 2 < k < n -2. For exploration and graph searching we also give a specific algorithm for the case of k = n -3. Besides being a unified approach for three different tasks, the given algorithms solve some open problems. Moreover, we provide some impossibility results for the perpetual graph searching problem, showing that it is impossible to solve it with k < n robots if n ≤ 9 or k ∈ {1, 2, 3, n -2, n -1}. All together, we obtain an almost full characterization of exclusive perpetual graph searching in rings, leaving only open the cases (k = 4, n > 9) and (k = 5, n = 10).

Approche unifiée pour réaliser diverses tâches dans un anneau grâce à des robots

Résumé : Des robots autonomes doivent collaborer pour accomplir une tâche dans un réseau en anneau dont ni les noeuds ni les liens sont étiquetés. Nous présentons une approche unifiée pour résoudre trois importants problèmes du domaine: l'exploration perpétuelle, le netoyage perpétuel, et le rassemblement. Dans le premier problème, chaque sommet doit être visiter infiniment souvent par chaque robot; dans le deuxième, une équipe de robots doit nettoyer les arêtes d'un graphe infiniment souvent; et dans le dernier problème, tous les robots doivent occuper le même noeud simultanément. Nous étudions ces trois problèmes dans le modèle de calcul distribué CORDA. Dans ce modèle, les robots ne peuvent communiquer qu'en observant les positions des autres robots. Plus précisemment, chaque robot est équipé de capteurs visuels et peut se déplacer d'un noeud à l'autre. Un robot agit par cycle Voir-Calculer-Se déplacer. Lors d'un cycle, le robot reçoit un instantané de la configuration courante (Voir), puis il prend la décision de se déplacer sur un noeud voisin ou pas, selon la configuration (Calculer) ; enfin il effectue l'action qu'il a calculée (Déplacer). Par ailleurs, les robots ont des capacités très restreintes: ils sont anonymes, sans mémoire, uniforme (ils exécutent le même algorithme) et n'ont pas de sens commun de l'orientation. Concernant les deux problèmes, la contrainte d'exclusion doit également être satisfaite : un noeud ne peut être occupé que par un robot.

Dans ce contexte, nous proposons des algorithmes qui, partant de n'importe quelle configuration asymmétrique et apériodique, résolvent les problèmes mentionnés ci-dessus dans un anneau anonyme. Notre principal algorithme est composé de deux phases. La première est commune à tous les problèmes et permet à k ≥ 2 robots d'atteindre une configuration particulière dans un anneau de n sommets, k < n -2. La seconde phase consiste en deux sous-procédures distinctes: l'une pour résoudre le problème du rassemblement, et la seconde qui permet à 5 ≤ k < n -3 robots, n ≥ 10 (sauf pourk = 5 et n = 10), de résoudre à la fois le problème de l'exploration et du nettoyage perpétuel. En plus d'être une approche unifiée, nos algorithmes résolvent quelques problèmes ouverts. De plus, nous prouvons des résultats d'impossibilité dans le cas du nettoyage perpétuel d'un anneau. En résumé, nous caractérisons presque complètement le problème du nettoyage perpétuel d'un anneau.

Mots-clés : calcul distribué, modèle CORDA 1 Introduction

In the field of robot-based computing systems, we consider k ≥ 1 robots placed on the nodes of an input graph. Robots are equipped with visibility sensors and motion actuators, and operate in Look-Compute-Move cycles in order to achieve a common task. Various problems have been studied in this setting such as pattern formation (in Euclidean metric spaces), graph exploration with stop, exclusive perpetual exploration, exclusive perpetual graph searching and gathering. Recently, several algorithms have been proposed to solve these problems in particular topologies such as lines, rings, trees and grids. Here, we propose a unified approach to solve the last three problems in rings.

The Look-Compute-Move model considers that in each cycle a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it moves to this neighbor (Move). Cycles are performed asynchronously, i.e., the time between Look, Compute, and Move operations is finite but unbounded, and it is decided by the adversary for each robot. Hence, robots that cannot communicate may move based on outdated perceptions. Moves are instantaneous, and hence any robot performing a Look operation sees all other robots at nodes and not on edges. This model is referred in the literature also as the CORDA model [START_REF] Flocchini | Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots[END_REF][START_REF] Prencipe | Impossibility of gathering by a set of autonomous mobile robots[END_REF]. We consider the minimalist variant of the CORDA model which has very weak hypothesis. Neither nodes nor edges of the graph are labeled and no local memory is available on nodes. Robots are anonymous, uniform (i.e. they all execute the same algorithm), oblivious (memoryless) and have no common sense of orientation. Guided by physical constraints, the robots may also satisfy the exclusivity property, according to which at most a node can be occupied by at most one robot [START_REF] Baldoni | Anonymous graph exploration without collision by mobile robots[END_REF].

The CORDA model received a lot of attention in the recent years. Most of the proposed algorithms consider that the starting configuration is exclusive, i.e., any node is occupied by at most one robot, and rigid, i.e., asymmetric and aperiodic. In the following, we review the literature concerning on graph topologies focussing on rings. Related work. In the problem of graph exploration with stop [START_REF] Devismes | Optimal probabilistic ring exploration by semisynchronous oblivious robots[END_REF][START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF][START_REF] Flocchini | Remembering without memory: Tree exploration by asynchronous oblivious robots[END_REF], it is required that each node (or each edge) of the input graph is visited a finite number of times by at least one robot and, eventually, all the robots have to stop. Whereas, the exclusive perpetual graph exploration [START_REF] Baldoni | Anonymous graph exploration without collision by mobile robots[END_REF][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][START_REF] Bonnet | Asynchronous exclusive perpetual grid exploration without sense of direction[END_REF] requires that each robot visits each node of the graph infinitely many times. Moreover, it adds the exclusivity constraint. In [START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF], first results on n-node rings are given. In detail, the paper gives algorithms for k = 3 and n ≥ 10, for k = n -5 (if n mod k = 0), and shows that the problem is infeasible for k = 3 and n ≤ 9, and for some symmetric configurations where k ≥ n -4.

Graph searching has been widely studied in centralized [START_REF] Fomin | An annotated bibliography on guaranteed graph searching[END_REF] and distributed setting (e.g., [START_REF] Ilcinkas | The cost of monotonicity in distributed graph searching[END_REF]). The aim is to make the robots clear all the edges of a contaminated graph. An edge is cleared if it is traversed by a robot or if both its ends are occupied. However, a clear edge can be recontaminated if there is a path without robots from a contaminated edge to it. The study of graph searching in the CORDA model when the exclusivity property must be always satisfied is introduced in [START_REF] Blin | Perpetual Graph Searching[END_REF] where a characterization of the perpetual exclusive graph searching on tree topologies is given. As far as we know, no results have been proposed in ring topologies for the perpetual exclusive graph searching problem in the CORDA model.

The gathering problem consists in moving all the robots in the same node and remain there. In [START_REF] Angelo | Gathering of robots on anonymous grids without multiplicity detection[END_REF], a full characterization of the gathering on grid topologies without any multiplicity detection is given. On rings, it has been proven that the gathering is unsolvable if the robots are not empowered by the so-called multiplicity detection capability [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF], either in its global or local version. In the former type, a robot is able to perceive whether any node of the graph is occupied Inria by a single robot or more than one (i.e., a multiplicity occurs). In the latter type, a robot is able to perceive the multiplicity only if it is part of it. Using the global multiplicity detection capability, in [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF], some impossibility results have been proven. Then, several algorithms have been proposed for different kinds of exclusive initial configurations in [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF][START_REF] Klasing | Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring[END_REF][START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF]. These papers left open some cases which have been closed in [START_REF] Angelo | How to gather asynchronous oblivious robots on anonymous rings[END_REF] where a unified strategy for all the gatherable configurations has been provided. With local multiplicity detection capability, an algorithm starting from rigid configurations where the number of robots k is strictly smaller than n 2 has been designed in [START_REF] Izumi | Mobile robots gathering algorithm with local weak multiplicity in rings[END_REF]. In [START_REF] Kamei | Asynchronous mobile robot gathering from symmetric configurations[END_REF], the case where k is odd and strictly smaller than n -3 has been solved. In [START_REF] Kamei | Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection[END_REF], the authors provide an algorithm for the case where n is odd, k is even, and 10 ≤ k ≤ n -5. The remaining cases with local multiplicity detection are left open and a the design of a unified algorithm is still not known. Contribution. In this work, we provide a unified approach for solving different tasks in the minimalist-CORDA model on ring topologies. Namely, we present an algorithm that, starting from any rigid configuration, solves: the exclusive perpetual exploration, the exclusive perpetual graph searching, and the gathering with local multiplicity detection capability. Our main algorithms consist of two phases. The first phase is common to all problems and allows k > 2 robots to achieve a particular rigid exclusive configuration, denoted below by C * , in an n-node ring, k < n -2. The second phase depends on the task. On the one hand, we design an algorithm that, starting from configuration C * , solves the gathering problem with local multiplicity detection for any team of k robots in n-node rings, 2 < k < n -2 (note that, if n = 2 or k ≥ n -2, no rigid configuration exists). On the other hand, we present an algorithm that, starting from configuration C * , solves both the perpetual exclusive graph exploration and the perpetual exclusive graph searching problems, for any team of k robots in n-node rings, n ≥ 10, 5 ≤ k < n -3 (but for k = 5 and n = 10). Moreover, we design a specific algorithm that, starting from any rigid configuration, solves the perpetual exclusive graph searching problem using n -3 robots in any n-node ring, n ≥ 10. Finally, we provide some impossibility results for the perpetual exclusive graph searching problem, showing that for 2 < n ≤ 9 and k < n, or k ∈ {1, 2, 3, n -2, n -1} and n > 4, the problem cannot be solved in a n-node ring with k robots. All together, we obtain an almost full characterization of exclusive perpetual graph searching in rings, leaving only open the cases (k = 4, n > 9) and (k = 5, n = 10). Outline. In the next section we define the notation used in the paper and describe the CORDA model. In Section 3, we propose an algorithm to achieve the special configuration C * . Perpetual exclusive graph searching is formally defined and studied in Section 4. We note that the algorithms given in this section also solve the perpetual exclusive exploration problem. The gathering problem is considered in Section 5.

Model and Notations

We consider a team of k ≥ 1 robots spread in an n-node ring, n ≥ 3. The ring is anonymous, that is its nodes and edges are undistinguishable. Moreover, no orientation is provided.

A configuration consists of the set of nodes that are occupied by a robot. Note that, it does not take into account the number of robots in each node. A configuration is said exclusive if each node is occupied by at most one robot. For 2 ≤ k < n -2, we denote by C * the configuration that consists of k -1 consecutive occupied nodes, one empty node, one occupied node, and the remaining ≥ 2 consecutive empty nodes. An interval in a configuration is an inclusion-maximal (possibly empty) subset of consecutive empty nodes, i.e., a subpath of empty nodes that stands between two occupied nodes. For instance, in C * , there are k -2 intervals of length 0, one interval of length 1 and one interval of length nk -1 > 1.

In a configuration C, a view at some occupied node r ∈ C is a sequence of integers W (r) = (q 0 , q 1 , . . . , q j ), j < k, that represents the sequence of the lengths of the intervals met when traversing the ring in one direction (clockwise or anti-clockwise) starting from r. Abusing the notation, for any i ≤ j, we refer to q i as the corresponding interval. Note that, if C is exclusive, then j = k -1 and 0≤i<j q j = nk. Note also that, a node r may have 2 distinct views, depending on the direction. Unless differently specified, we refer to W (r) = (q 0 , q 1 , . . . , q j ) as the view at r that is minimum in the lexicographical order.

Let W (C) be the set of the at most 2k views (at most two views per occupied node) in the configuration C. The supermin configuration view W C min of the configuration C is the minimal view in W (C) in the lexicographical order. Note that, in W C min , no interval has length strictly smaller than q 0 , and, moreover, if k < n, then q k-1 > 0. For instance, W C * min = (q 0 , . . . , q k-2 , q k-1 ) with q 0 = . . . = q k-3 = 0, q k-2 = 1 and

q k-1 = n -k -1.
For any view W = (q 0 , q 1 , . . . , q j ) in a configuration C, we set W = (q 0 , q j , q j-1 , . . . , q 1 ), and W i = (q i , q (i+1) mod (j+1) , . . . , q (i+j) mod (j+1) ) denotes the view obtained by reading W starting from q i as first interval. Note that

W (C) = {W i , W i , | 0 ≤ i ≤ j}. Let I C be the set of intervals q i such that W i or W i are equal to W C min . The intervals in I C are the supermins of C. For instance, |I C * | = 1.
An exclusive configuration is called symmetric if the ring admits a geometrical axis of symmetry, dividing the ring into two specular halves. An exclusive configuration is called periodic if it is invariable under non-trivial (i.e., non-complete) rotations. A configuration which is aperiodic and asymmetric is called rigid.

We now give some useful properties that are proved in [START_REF] Angelo | How to gather asynchronous oblivious robots on anonymous rings[END_REF]. In particular, Lemma 1 is used to detect possible symmetry or periodicity of a configuration.

Property 1 ([9]) Given a view W of a configuration C, (i) there exists 0 < i ≤ j such that W = W i iff C is periodic; (ii) there exists 0 ≤ i ≤ j such that W = W i iff C is symmetric; (iii)
C is aperiodic and symmetric iff there exists one unique axis of symmetry.

It follows that if a configuration is rigid, then each occupied node has a view which is different from any other occupied node.

Lemma 1 ([9]) Given a configuration C, (i) |I C | = 1 if

min-CORDA model

We consider the CORDA model [START_REF] Flocchini | Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots[END_REF][START_REF] Prencipe | Impossibility of gathering by a set of autonomous mobile robots[END_REF] where the robots have no explicit way of communicate to each other (e.g., they cannot exchange messages). However, they are are endowed with visibility sensors allowing each robot to perceive their own position in the graph and the positions of all the other robots.

In the CORDA model, the robots proceed by cycles of three phases Look-Compute-Move. In the Look-phase, a robot at some node r accesses a snapshot of the network that consists of the view W (r). In the Compute-phase, the robot decides its action based on the information it received during the Look-phase. Finally, during the Move-phase, the robot executes its action, i.e., it moves to a neighboring node or stays idle. The environment is fully asynchronous which, in particular, means that the Compute-phase may be executed based on an out-dated view of the network.

Inria

Following [START_REF] Blin | Perpetual Graph Searching[END_REF], we consider the min-CORDA model, where the robots have very weak abilities. Robots are anonymous, i.e., they do not have identifiers, and are uniform, i.e., they all run the same algorithm. Robots are oblivious (memoryless). The robots have no sense of direction, i.e., they do not agree on a common orientation of the ring. Unless differently specified, two or more robots cannot occupy the same node (exclusivity property). When the exclusivity property is not imposed (e.g. for solving the gathering problem), the robots have the so called weak multiplicity detection capability that is, a robot is able to detect whether the node where it resides is occupied by more than one robot or only by itself, but it is not able to detect the exact number of robots occupying the node. Note that this is the weakest assumption that has to be made to solve the gathering since it has been shown that the gathering is impossible if no multiplicity detection capability is allowed [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF].

Our goal is to investigate the feasibility of several collaborative tasks with these weak hypothesis. Throughout the paper, we assume that the starting configuration is rigid and it respects the exclusivity property. Note however that our impossibility results hold for any starting configuration.

3 Reaching configuration C * in the min-CORDA model

In this section, we propose an algorithm, called Align, in the min-CORDA model that allows to reach configuration C * starting from any exclusive rigid configuration. Algorithm Align will be used in next sections to achieve the configurations suitable for the graph searching, exploration, or gathering problems. We first describe the algorithm allowing to reach configuration C * . In the second subsection, we prove its correctness.

Algorithm Align

The assumption of initial rigidity and exclusivity ensures that one single robot moves at time. The moves performed aim to reduce the unique supermin of a rigid configuration in a way that the obtained configuration is again rigid and exclusive. The algorithm is performed until configuration C * is achieved.

By rigidity and exclusivity, the starting configuration has a unique supermin interval and each node has a unique supermin configuration view. Therefore, the snapshots provided to the robot allow to agree on a common view (the unique minimum one) where each robot can identify its position. This ensures that a single robot will move and that the next configuration is still exclusive. Four rules, called reduction, are defined below where, for each rule, a single robot is asked to move to an empty node. reduction 0 is executed only if the supermin has length at least one. If the supermin has null length, reduction 1 is executed if the corresponding move does not create any symmetry. Otherwise, reduction 2 is executed if it does not create any symmetry, and reduction -1 is executed otherwise. We prove that, starting from any rigid configuration, the move resulting from this algorithm achieves a new rigid configuration. The only exception is configuration C s such that W C s min = (0, 1, 1, 2). In fact, from such a configuration, any single move would generate either a symmetric configuration or configuration C s itself. In this case, we perform two times reduction 1 and show that this always leads to C * . In any case, in the entire algorithm, only one robot is allowed to move at one time. Moreover, we prove that reduction i , i ∈ {0, 1, 2} strictly decreases the supermin. Finally, from some configuration C, applying reduction -1 may lead to a configuration C ′ with a greater supermin configuration view. However, we prove that, in this case, the next move will reach a new configuration whose supermin configuration view is strictly smaller that the one of C. Since, clearly, C * is the rigid configuration with smallest supermin configuration view, this will prove that executing Algorithm Align eventually achieves to C * .

We now formally define the four rules mentioned above. Let C be any exclusive rigid configuration and let W C min = (q 0 , q 1 , . . . , q k-1 ) be its unique supermin configuration view. Let ℓ 1 be the smallest integer such that q ℓ1 > 0 and let ℓ 2 be the second smallest integer such that q ℓ2 > 0. That is, if 0 < ℓ 1 and ℓ 1 + 1 < ℓ 2 , W C min = (0, . . . , 0, q ℓ1 , 0, . . . , 0, q ℓ2 , q ℓ2+1 , . . . , q k-1 ). Let a, b, c and d be the nodes between the intervals q 0 and q k-1 , q ℓ1 and q ℓ1+1 , q ℓ2 and q ℓ2+1 , and q k-2 and q k-1 respectively.

• reduction 0 (C): The robot at a moves to its neighbor in the interval q 0 > 0. Then, the new configuration is (q 0 -1, q 1 , . . . , q k-2 , q k-1 + 1);

• reduction 1 (C): The robot at b moves to its neighbor in the interval q ℓ1 > 0. Then, the new configuration is (q 0 , q 1 , . . . , q ℓ1-1 , q ℓ1 -1, q ℓ1+1 + 1, . . . , q k-1 );

• reduction 2 (C): The robot at c moves to its neighbor in the interval q ℓ2 > 0. Then, the new configuration is (q 0 , q 1 , . . . , q ℓ2-1 , q ℓ2 -1, q ℓ2+1 + 1, . . . , q k-1 );

• reduction -1 (C): The robot at d moves to its neighbor in the interval q k-1 > 0. Then, the new configuration is (q 0 , q 1 , . . . , q k-2 + 1, q k-1 -1).

The pseudo-code of Algorithm Align is given in Fig. 1 and it is performed by a generic robot r. It makes use of procedure reduction i whose pseudo-code is given in Fig. 2 and described below.

Algorithm: Align Input: Rigid and exclusive configuration C with view W = (q0, q1, . . . , q k-1 ) seen from a robot r 1 Let qmin be the first interval of W C min ; 2 if qmin > 0 then Let q min be the first interval of W C min . If q min > 0, the algorithm performs reduction 0 (lines 2-3). Otherwise, it first tries to perform reduction 1 by computing the configuration C ′ that would be obtained (line 5) and by checking whether C ′ is symmetric (line 6). In the Inria negative case, reduction 1 is performed (line 7), Otherwise, the algorithm tries to perform reduction 2 (lines 9-11) and then reduction -1 (lines [START_REF] Flocchini | Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots[END_REF][START_REF] Fomin | An annotated bibliography on guaranteed graph searching[END_REF][START_REF] Ilcinkas | The cost of monotonicity in distributed graph searching[END_REF]. If the configuration obtained is still symmetric, then it must be C s such that W C s min = (0, 1, 1, 2). In this case, reduction 1 is performed at line 17. The configuration obtained is C such that W C min = (0, 0, 2, 2). At the next step, reduction 1 is again performed at line 7.

We now describe the pseudo-code of reduction i which is given in Fig. 2.

Procedure: reductioni Input: Rigid and exclusive configuration C with view W = (q0, q1, . . . , q k-1 ) as seen from a robot r Let W = (q 0 , q 1 , . . . , q k ) be the view of C read by the robot r which performs the procedure and let W C min = (q ′ 0 , q ′ 1 , . . . , q ′ k ). At lines 1-6, the algorithm moves the last robot in a supermin configuration view, that is it performs reduction -1 . If (W C min ) j-1 ≥ (W C min ) j , then the robot has to move if and only if W 1 = W C min (line 2), that is, q 0 = q ′ j , q 1 = q ′ 0 , . . . , q j = q ′ j-1 , and it has to move towards q 0 (line 3) in order to reduce q ′ j by enlarging q ′ j-1 . If (W C min ) j-1 ≤ (W C min ) j , then the robot has to move if and only if W j-1 = W C min (line 5) and it has to move towards q j (line 6). Lines 7-9 implement reduction 0 which consists in reducing the supermin interval by moving the robot on the largest side of such interval, that is the robot which view is the supermin one. At lines 10-15 the algorithm performs reduction i for i ∈ {1, 2}.

1 if i = -1 then 2 if W1 = W C
If (W C min ) ℓi ≥ (W C min ) ℓi+1
, then a robot has to move if and only if there exists an integer m such that q ′ 0 = q m , q ′ 1 = q m-1 , . . . , q ′ ℓi = q 0 , that is if and only if W m = W C min and m = ℓ i (line 11). In this case, such robot has to move towards q 0 (line 12). If (W C min ) ℓi ≤ (W C min ) ℓi+1 , then a robot has to move if and only if there exists an integer m such that q ′ 0 = q m , q ′ 1 = q m+1 , . . . , q ′ ℓi = q j , that is if and only if W m = W C min and jm = ℓ i (line 14). In this case, such robot has to move towards q j (line 15).

It is clear from the definition of the rules that, from an exclusive rigid configuration, only one robot can execute a move and that the reached configuration is still exclusive. Note that, in the case that the configuration is C s (i.e. W C s min = (0, 1, 1, 2)), any reduction move creates a symmetric configuration. In this case, we perform reduction 1 which produces the symmetric configuration C such that W C min = (0, 0, 2, 2). After this, reduction 1 is again performed and it leads to C * (i.e W C * min = (0, 0, 1, 3)). As C is symmetric, the supermin configuration view can be obtained by reading the ring in both possible direction (i.e. W C min = (W C min )). However robot b is unequivocally identified as the single robot on the axis of symmetry and reduction 1 corresponds to moving b in an arbitrary direction. In any case C * is achieved. In next subsection, we formally prove that C * is eventually achieved and that, except for the case of C s , the obtained intermediate configurations are always rigid.

Correctness

We consider a rigid exclusive configuration C with unique (by Lemma 1) supermin configuration view W C min = (q 0 , q 1 , . . . , q k-1 ). We prove that, when one of the four rules is applied by Algorithm Align, the resulting configuration C ′ is still rigid. Moreover, in the case of the first three rules, the supermin configuration view of C ′ is strictly smaller than W C min . In the case of reduction -1 , we have to consider the next move to strictly reduce the supermin configuration view.

Since W C min = (q 0 , q 1 , . . . , q k-1 ) is the supermin configuration view, no interval has length smaller than q 0 and q 1 ≤ q k-1 . Therefore, if q 0 > 0 and reduction 0 is applied, the view (q 0 -1, q 1 , . . . , q k-2 , q k-1 + 1) is clearly the unique supermin configuration view of the resulting configuration C ′ . By Lemma 1, we obtain:

Lemma 2 ([9]) The configuration C ′ obtained by applying reduction 0 in the rigid exclusive configuration C with q 0 > 0 is rigid. Moreover, W C min > W C ′ min (in lexicographical order).
Algorithm Align performs reduction 0 until it reaches a rigid exclusive configuration C with supermin configuration view W C min = (0, q 1 , . . . , q k-1 ) (i.e., q 0 = 0). In this case, reduction 0 cannot be applied as otherwise there would be a collision. Therefore reduction 1 , reduction 2 or reduction -1 are applied depending on the configuration C. In particular, reduction 1 is applied if it does not create any symmetry. If q 0 = 0, by performing reduction 1 we cannot obtain a symmetry except for some particular configurations given in the next lemma.

Lemma 3 Let C be a rigid exclusive configuration with supermin configuration view W C min = (q 0 , q 1 , . . . , q k-1 ), q 0 = 0 and ℓ 1 > 0 be the smallest integer such that q ℓ1 > 0. Then, the configuration C ′ resulting from the application of reduction 1 is aperiodic. Moreover, C ′ is symmetric if and only if conditions 1-4 hold:

q i = 0, for each i = 0, 1, . . . , ℓ 1 -1;
(1)

q ℓ1 = 1; (2)
q ℓ1+1 + 1 = q k-1 ; (3)
the sequence q ℓ1+2 , q ℓ1+3 , . . . q k-2 is symmetric.

Proof. By rigidity of C, only one robot can perform reduction 1 and then C ′ is well defined and admits a view W = (q ′ 0 , q 1 , . . . , q ′ k-1 ) = (q 0 , q 1 , . . . , q ℓ1 -1, q ℓ1+1 + 1, . . . , q k-1 ). If C ′ is periodic, there must be j > 0 such that (q ′ j mod k , q ′ (j+1) mod k , . . . , q ′ (j+ℓ1) mod k ) = (q 0 , q 1 , . . . , q ℓ1 -1) = (0, . . . , 0, q ℓ1 -1). Note that, because q ′ ℓ1+1 > 0, j > ℓ 1 + 1. Hence, in that case, the view (q j , . . . , q k-1 , q 0 , . . . , q j-1 ) would be a view of C strictly smaller than W C min , a contradiction. Therefore, C ′ is aperiodic.

If equations 1-4 hold, then W = (0, . . . , 0, q ℓ1+1 + 1, q ℓ1+2 , q ℓ1+3 , . . . q k-2 , q ℓ1+1 + 1) is symmetric with the axis of symmetry passing through the middle of the sequences q 0 , q 1 , . . . , q ℓ1 -1 and q ℓ1+2 , q ℓ1+3 , . . . q k-2 .

Inria

We now show the only if statement. Note that Condition 1 is always satisfied by the hypothesis that q 0 = 0 and the definition of ℓ 1 . Let us assume that C ′ is symmetric.

For the sake of contradiction, let us assume that q ℓ1 > 1 Then, because q ℓ1 ≤ q k-1 and q ℓ1 -1 > 0, it is easy to check that W is the supermin configuration view of C ′ , and W < W C min . Hence, q 0 must be the unique supermin of C ′ since otherwise, a supermin interval different from q 0 would have been a supermin interval in C, contradicting the fact that W C min is the supermin minimum view of C. By Lemma 1, since |I C ′ | = 1 and C ′ is symmetric, the (unique) axis of symmetry of W passes through the edge corresponding to q 0 . However, since q ℓ1 -1 < q k-1 , C ′ is not symmetric, a contradiction. It follows that q ℓ1 = 1.

In this case, the first ℓ 1 elements of W are 0 and, by the same arguments as before this sequence is unique and the possible axis of symmetry of C ′ passes through the middle of such unique sequence. This implies that C ′ is symmetric only if q ℓ1+1 + 1 = q j and that the sequence q ℓ1+2 , q ℓ1+3 , . . . , q j-1 is symmetric.

It follows that if W C

min does not satisfy Conditions 1-4, the application of reduction 1 results in a rigid configuration. Otherwise, if applying reduction 2 does not create any symmetry, it is applied. Lemma 4 shows that actually, when Conditions 1-4 hold, reduction 2 can create symmetries only for some specific configurations.

For the next lemmata, we need further notation. A pattern is the set of possible configurations admitting a view that fulfills some rules defined by a string of integer numbers and the following symbols. Let x be an integer number: x * denotes the repetition of x zero or more times; x + denotes the repetition of x one or more times; x {n} denotes the repetition of x exactly n times. Given a configuration C we say that C belongs to a pattern P if it has a view W that matches the rules of the pattern. We denote it by W ∈ P . As an example, the configuration C with a view (0, 0, 0, 1, . . . , 1, 2, 2, . . . , 2) belongs to (0 {3} , 1 * , 2 + ).

Lemma 4 Let C be a rigid exclusive configuration with supermin configuration view W C min = (q 0 , q 1 , . . . , q k-1 ), with 3 ≤ k < n -2, q 0 = 0, ℓ 1 be the smallest integer such that q ℓ1 > 0 and Conditions 1-4 hold. Then, the configuration C ′ resulting from the application of reduction 2 is aperiodic. Moreover, C ′ is symmetric if and only if one of the following conditions hold:

W C min ∈ (0, 1, 1 + , 2); (5)
W C min ∈ (0 {ℓ1} , 1, {0 {ℓ1-1} , 1} + , 0 {ℓ1-2} , 1). (6)
Proof. By rigidity of C, only one robot can perform reduction 2 and then C ′ is well defined and admits a view W = (q ′ 0 , . . . , q ′ k-1 ) = (q 0 , q 1 , . . . , q ℓ2 -1, q ℓ2+1 + 1, . . . , q k-1 ).

Because C satisfies Conditions 1-4, it is straightforward to see that C ′ is aperiodic. If W C min ∈ (0, 1, 1 + , 2)
, by performing reduction 2 we obtain either W = (0, 1, 0, 3) or W = (0, 1, 0, 2, 1 * , 2). In the first case, C ′ is symmetric with the axis of symmetry passing through the intervals of size 1 and 3. In the second case, C ′ is symmetric with the axis of symmetry passing through the single node of interval q 1 and either in the middle of the sequence 1 * or in the occupied node which separates the two intervals of size 2.

If W C min ∈ (0 {ℓ1} , 1, {0 {ℓ1-1} , 1} + , 0 {ℓ1-2} , 1)
, by performing reduction 2 we obtain either

W ∈ (0 {ℓ1} , 1, 0 {ℓ1} , 1, 0 {ℓ1-2} , 1, {0 {ℓ1-1} , 1} * , 0 {ℓ1-2} , 1) or W ∈ (0 {ℓ1} , 1, 0 {ℓ1} , 1, 0 {ℓ1-3} , 1) in both cases C ′ is
symmetric with the axis of symmetry passing through the single node of interval q 1 and in the middle of the sequence 1, {0 {ℓ1-1} , 1} * in the first case, and in the middle of the sequence 0 {ℓ1-3} in the second case.

Let us assume that C ′ is symmetric. We prove the only if statement by case analysis on q ℓ1+1 .

• q ℓ1+1 > 0. Let us first assume that ℓ 1 + 2 < k -1. The hypothesis q ℓ1+1 > 0, implies that ℓ 2 = ℓ 1 + 1 and hence, W ∈ (0 {ℓ1} , 1, q ℓ1+1 -1, q ℓ1+2 + 1, S ′ , q ℓ1+1 + 1), for some sequence S ′ . Note that S ′ may be empty if ℓ 1 + 2 = k -2, and otherwise, we set S ′ = (S, q k-2 ) (where S may be an empty sequence).

The possible axis of symmetry cannot pass through the middle of the initial sequence of 0s because, under the hypothesis that q ℓ1+1 > 0, we have that q k-1 = q ℓ1+1 + 1 > 1 = q ℓ1 and hence q ℓ1 = q k-1 . It follows that, if there exists an axis of symmetry in C ′ , it does not pass through the initial sequence of 0s.

Therefore, W contains a subsequence (q ′ j , . . . , q ′ j+ℓ1 ) = (1, 0 {ℓ1} ) where the sequence of ℓ 1 zeros is disjoint from the initial sequence of zeros, i.e., ℓ 1 < j and j + ℓ

1 < k -1. If ℓ 1 + 1 < j, then the view W C
min has to contain (q ′ j , . . . , q ′ j+ℓ1 ) or (q ′ j -1, . . . , q ′ j+ℓ1 ) (the second case occurs only if j = ℓ 1 + 2) as a subsequence disjoint from (q 0 , . . . , q ℓ1-1 ), which would constitute another supermin, smaller or equal than the original one, contradicting the rigidity of C. Therefore, j = ℓ 1 + 1 and, thus, q ℓ1+1 = 1. By similar arguments, we show that ℓ 1 must equal 1.

Therefore, W = (0, 1, 0, q ℓ1+2 + 1, S ′ , q ℓ1+1 + 1), and the axis in C ′ passes through the single node of q 1 and the middle of sequence S ′ which thus is symmetric. Hence, q ℓ1+2 + 1 = q k-1 and, as q ℓ1+1 = 1 and q k-1 = q ℓ1+1 + 1, then q k-1 = 2 and q ℓ1+2 = 1. Since sequence S ′ is symmetric, we have that

q ℓ1+2+m = q k-1-m , for all m = 1, 2, . . . , ⌊ k-1-ℓ1-4 2 ⌋. Moreover, by Condition 4, q ℓ1+1+m = q k-1-m , for all m = 1, 2, . . . , ⌊ k-1-ℓ1-3 2 ⌋. As q ℓ1+2 = 1, this implies that (q ℓ1+2 , q ℓ1+3 , . . . q k-2 ) ∈ (1 + ). In conclusion, W C min ∈ (0, 1, 1, 1 + , 2). If q ℓ1+1 > 0 and ℓ 1 + 2 = k -1, we have that W C min ∈ (0 {ℓ1} , 1, q ℓ1+1 , q ℓ1+1 + 1) and W ∈ (0 {ℓ1} , 1, q ℓ1+1 -1, q ℓ1+1 + 2). By similar arguments used before, C ′ is symmetric only if ℓ 1 = 1 and q ℓ1+1 -1 = 0 which implies that W C min = (0, 1, 1, 2). Summarizing if q ℓ1+1 > 0 and C ′ is symmetric, then W C min ∈ (0, 1, 1 + , 2).
• q ℓ1+1 = 0. In this case q k-1 = q ℓ1+1 + 1 = 1 and then W C min ∈ (0 {ℓ1} , 1, 0, S, 1), where, by Condition 4, S is a symmetric sequence. We first show that the possible axis of symmetry cannot pass through the sequence 0 {ℓ1} . Let us denote W as W = (q ′ 0 , q ′ 1 , . . . , q ′ k-1 ) ∈ (0 {ℓ1} , 1, 0, S ′ , 1), for some sequence S ′ , and note that q ′ i = q i for all i ∈ {0, 1, . . . , k -1} \ {ℓ 2 , ℓ 2 + 1}. If the axis passes through the sequence 0 {ℓ1} , then the sequence (q ′ ℓ1+1 , q ′ ℓ1+2 , . . . , q ′ k-2 ) = (0, S ′ ) is symmetric. Therefore, since q ′ ℓ1+1 = 0, then q ′ k-2 = 0. Since q ′ ℓ2+1 ≥ 1, it follows that q ′ k-2 = q ′ ℓ2+1 , that is j -1 = ℓ 2 + 1 and then q k-2 = q ′ k-2 = 0. Moreover, since also S is symmetric, q ℓ1+2 = 0 and ℓ 1 + 2 = ℓ 2 , which implies that q ′ ℓ1+2 = q ℓ1+2 = 0. By iterating these arguments, we have that q ′ i = q i = 0 for all i ∈ {ℓ 1 + 1, . . . , k -2} which implies that k = n -2, a contradiction.

Let us assume that there is an axis not passing through the sequence of 0 {ℓ1} . This implies that W contains a subsequence (q ′ j , . . . , q ′ j+ℓ1 ) = (1, 0 {ℓ1} ) where the sequence of ℓ 1 zeros is disjoint from the initial sequence of zeros, i.e., ℓ 1 < j and j + ℓ 1 < k -1.

Three cases may arise:

-the move performed by reduction 2 creates a sequence 0 {ℓ1+1} (i.e., there was in W C min a sequence 0 {ℓ1} distinct from the initial one). In this case, the axis of symmetry of C ′ has to pass through the middle of the unique sequence 0 {ℓ1+1} . This implies that W ∈ (0 {ℓ1} , 1, 0 {ℓ1+1} , 1, 0 {ℓ1} , S ′′ ), where S ′′ is a symmetric sequence. Therefore, W C min = (0 {ℓ1} , 1, 0 {ℓ1} , 1, 0 {ℓ1+1} , S ′′ ) which is a contradiction to the fact that W C min is the supermin configuration view as there is a sequence of ℓ 1 + 1 of zeros.

Inria

-the move performed by reduction 2 creates a sequence 0 {ℓ1} (disjoint from the initial one). Under this hypothesis, q ℓ2 = 1, either W C min = (0 {ℓ1} , 1, 0 {ℓ1-1} , 1, 1) or W C min ∈ (0 {ℓ1} , 1, 0 ℓ1-1 , 1, q ℓ2+1 , S ′′ , 1) where S ′′ is a sequence that may be empty. Because W C min satisfies Conditions 1-4, the first case may occur only for ℓ 1 = 2, and in that case, W C min ∈ (0 {ℓ1} , 1, {0 {ℓ1-1} , 1} + , 0 {ℓ1-2} , 1). Assume that W C min ∈ (0 {ℓ1} , 1, 0 ℓ1-1 , 1, q ℓ2+1 , S ′′ , 1). In that case, W ∈ (0 {ℓ1} , 1, 0 {ℓ1} , q ℓ2+1 + 1, S ′′ , 1). We first show that the possible axis of symmetry passes through the middle of the initial subsequence (0 {ℓ1} , 1, 0 {ℓ1} ). By contradiction, let us assume that the axis of symmetry passes through another interval which implies that there exists an index

m ≥ ℓ 2 + 1 such that W = W m (see Property 1). However, W < W C min while W m > (W C min ) m (because q ℓ2+1 increased) and (W C min ) m > W C min (because W C
min is the unique supermin). Therefore W < W m , a contradiction. It follows that the axis of symmetry passes through the middle of the initial subsequence (0 {ℓ1} , 1, 0 {ℓ1} ) and therefore, q ℓ2+1 = 0 and S ′′ is a symmetric sequence. Summarizing, W ∈ (0 {ℓ1} , 1, 0 {ℓ1} , 1, S ′′ , 1) and W C min ∈ (0 {ℓ1} , 1, 0 {ℓ1-1} , 1, 0, S ′′ , 1) = (0 {ℓ1} , 1, 0, 0 {ℓ1-2} , 1, 0, S ′′ , 1), where S ′′ is symmetric and, by Condition 4, (0 {ℓ1-2} , 1, 0, S ′′ ) is also symmetric. By the latter symmetry, we have that S ′′ ends with (0, 1, 0 {ℓ1-2} ) and by the former one it follows that S ′′ starts with (0 {ℓ1-2} , 1, 0). By iterating these arguments, we obtain

S ′′ ∈ (0 {ℓ1-2} , 1, 0, 0 {ℓ1-2} , 1, 0, . . . , 0, 1, 0 {ℓ1-2} , 0, 1, 0 {ℓ1-2} ) = (0 {ℓ1-2} , 1, {0 {ℓ1-1} , 1} * , 0 {ℓ1-2} ) and hence, by plugging S ′′ into W C min , W C min ∈ (0 {ℓ1} , 1, {0 {ℓ1-1} , 1} + , 0 {ℓ1-2} , 1).
-the move performed by reduction 2 does not create a sequence 0 {x} , for any x ≥ ℓ 1 .

In this case, the sequence (1, 0 {ℓ1} ) is contained also in W C min . Let m be the position of the first 0 of this sequence in W . Note that, such sequence does not contain neither q ℓ2 nor q ℓ2+1 . Hence W ∈ (0 {ℓ1} , 1, 0, . . . , q ℓ2 -1, q ℓ2+1 + 1, . . . , 1, 0 {ℓ1} , . . . , 1). Moreover W < W C min while W m > (W C min ) m . Hence W m cannot be equal to W . It follows that no such axis of symmetry can exist.

In conclusion, if q ℓ1+1 = 0 and C ′ is symmetric, then

W C min ∈ (0 {ℓ1} , 1, {0 {ℓ1-1} , 1} + , 0 {ℓ1-2} , 1).
It follows that we can use reduction 2 in all the configurations which satisfy Conditions 1-4 but not Conditions 5-6. The next lemma shows that in the remaining cases we can use reduction -1 , the resulting configuration being rigid.

Lemma 5 Let C be a rigid exclusive configuration with supermin configuration view

W C min . If ei- ther W C min ∈ (0, 1, 1, 1 + , 2) or W C min ∈ (0 {ℓ1} , 1, {0 {ℓ1-1} , 1} + , 0 {ℓ1-2} , 1)
, then, the configuration C ′ resulting from the application of reduction -1 is rigid.

Proof. By rigidity of C, only one robot can perform reduction -1 and then C ′ is well defined.

If

W C min ∈ (0, 1, 1, 1 + , 2), then C ′ admits a view W ∈ (0, 1, 1, 1 * , 2, 1
) which is always rigid. Indeed, there is only one interval of size 0 and only one interval of size 2 which implies that a possible axis can pass only through these two intervals. However, the number of nodes between theses two intervals on one side is different from that on the other side.

If W C min ∈ (0 {ℓ1} , 1, {0 {ℓ1-1} , 1} + , 0 {ℓ1-2} , 1), then C ′ admits a view W ∈ (0 {ℓ1+1} , 1, {0 {ℓ1-1} , 1} + , 0 {ℓ1-3} , 1) which is rigid. Indeed, the axis of symmetry can pass only through the middle of the initial sequence 0 {ℓ1+1} but the two sides of such sequence are different.

By the above lemma, it follows that if we apply reduction -1 to a supermin configuration view W C min fulfilling Condition 5 or 6, the only case in which the obtained configuration can be symmetric is when W C min = (0, 1, 1, 2). The correctness of Algorithm Align then follows from next theorem.

Theorem 1 Let k ≥ 3 robots standing in an n-node ring with k < n -2. Starting from a rigid exclusive configuration, Algorithm Align eventually terminates achieving configuration C * and all intermediate configurations obtained are either rigid or such that the supermin view is (0, 0, 2, 2).

Proof. As Align starts from a rigid exclusive configuration, by Lemma 1, there exists a unique supermin in the initial configuration. Hence exactly one robot moves at one time.

Let us first assume that the initial configuration is different from C s . In a current rigid exclusive configuration C with unique supermin configuration view W C min = (q 0 , q 1 , . . . , q k-1 ), we prove that the next move is unique and result in a rigid exclusive configuration.

If q 0 > 0, the algorithm performs reduction 0 . This involves a unique robot and the resulting configuration satisfies the desired properties by Lemma 2.

If q 0 = 0, a unique robot executes reduction 1 if the resulting configuration is rigid and exclusive. Otherwise, by Lemma 3, W C min satisfies Conditions 1-4. In that case, a unique robot executes reduction 2 if the resulting configuration is rigid and exclusive. Otherwise, by Lemma 4,

W C min ∈ (0, 1, 1 + , 2) or W C min ∈ (0 {ℓ1} , 1, {0 {ℓ1-1} , 1} + , 0 {ℓ1-2} , 1
). In this case, a unique robot executes reduction -1 . By Lemma 5, as the initial configuration is different from C s , this results in a configuration satisfying the desired properties.

Since configuration C * is the configuration with the smallest supermin configuration view, it only remains to show that each movement reduces the supermin. Hence, in the following, we show that the each movement (or each two movements) of Align reduces the supermin.

Let us denote by W = (q ′ 0 , q ′ 1 , . . . , q ′ k-1 ) the view of the configuration C ′ obtained after the movement. W is the view of C ′ at the same node and in the same direction as W C min . Let W C ′ min be the supermin configuration view of C ′ . If the movement is reduction 0 , then q ′ 0 = q 0 -1 and hence W C ′ min ≤ W < W C min . If the movement is reduction i , i ∈ {1, 2} then W = (q 0 , q 1 , . . . , q ℓi -1, q ℓi+1 + 1, . . . , q k-1 ) < W C min and therefore

W C ′ min ≤ W < W C min . If the move- ment is reduction -1 it follows that W C min ∈ (0, 1, 1, 1 + , 2) or W C min ∈ (0 {ℓ1} , 1, {0 {ℓ1-1} , 1} + , 0 {ℓ1-2} , 1
). In the latter case, W ∈ (0 {ℓ1+1} , 1, {0 {ℓ1-1} , 1} + , 0 {ℓ1-3} , 1) and hence W C ′ min ≤ W < W C min . In the former case, W ∈ (0, 1, 1, 1 * , 2, 1) and hence W > W C min . However, C ′ is rigid and does not satisfy Conditions 1-4 and hence the movement performed in C ′ is reduction 1 . Therefore, the configuration C ′′ obtained after performing reduction 1 on C ′ is W ′′ ∈ (0, 0, 2, 1 * , 2, 1). Therefore, W ′′ < W C min . Let us now assume that the initial configuration is C s . Note that, this is the only initial configuration with k = 4 and n = 8 which is rigid and different from C * . From C s , reduction 1 is performed at line 17 and the symmetric configuration C such that W C min = (0, 0, 2, 2) is achieved. The next movement performed is again reduction 1 which leads to C * (i.e. W C * min = (0, 0, 1, 3)) independently from the supermin view. In fact, even if configuration C is symmetric, robot b is unequivocally identified as the single robot on the axis of symmetry and reduction 1 corresponds to moving b in an arbitrary direction. In any case C * is achieved.

Inria 4 Clearing a ring in the min-CORDA model

In this section, we study the exclusive perpetual graph searching problem of an n-node ring (n ≥ 3) by a team of 1 ≤ k ≤ n robots in the min-CORDA model, starting from any rigid exclusive configuration. In the case, 5 ≤ k < n -3 and n ≥ 10 (or n > 10 if k = 5), we propose an algorithm that makes use of Algorithm Align presented in previous section. We then propose a specific algorithm for the case k = n -3 and n ≥ 10. On the other hand, we show that for k ∈ {1, 2, 3, n -2, n -1} and n > 3, or for 2 < n ≤ 9 and k < n, there is no algorithm that solves the problem, even if the initial configuration is given. The cases k = 4 and (k = 5, n = 10) are left as open problems.

Perpetual exclusive graph searching

Given a n-node graph G where all edges are contaminated, the graph searching problem consists in coordinating a team of robots to eventually clear all edges. The robots occupy the nodes of G and a robot can move along an edge from its current position to a neighboring node. An edge is cleared by a robot when it traverses it or if both its ends are simultaneously occupied by some robots. However, a clear edge is instantaneously recontaminated if there is a path from one of its end to the end of a contaminated edge and no node of this path is occupied by some robot. This variant of graph searching is classically referred as mixed graph searching [START_REF] Bienstock | Monotonicity in graph searching[END_REF]. Motivated by physical constraints and following [START_REF] Blin | Perpetual Graph Searching[END_REF], we moreover impose the exclusivity constraint, i.e., a node can be occupied by at most one robot.

A search strategy using 1 ≤ k ≤ n robots consists of a set of k nodes, the initial positions, and a sequence of moves of the robots, sliding the robots along the edges to empty neighbors, that eventually clear all edges. For instance, it is obvious that there is no search strategy that clears a n-node ring using one robot. On the other hand, a possible strategy using two robots is the following: first place two robots at adjacent nodes u and v, then slide the robot at u along the empty nodes of the ring until it reaches the other neighbor w of v.

In this section, we consider the graph searching problem in n-node rings in the min-CORDA model. More precisely, we aim at designing algorithms that allow robots to clear a n-node ring starting from any rigid exclusive configuration. Because our algorithms ensure that all met configurations are rigid and exclusive, and because the robots are oblivious and cannot know whether an edge is cleared or not, the resulting strategies clear the ring perpetually, i.e., each edge is cleared infinitely often. Moreover, we study the exclusive perpetual exploration. Perpetual graph searching and perpetual exploration look similar but are not equivalent. For instance, one robot always moving clockwise will perpetually explore a ring without clearing it. On the other hand, the above search strategy using two robots perpetually clears a ring (one robot is at v and the other one alternate its move from u to w and then from w to u) but does not perpetually explore it since the robot at v never moves. The algorithms we propose in the sequel both perpetually explore and perpetually clear the rings.

Impossibility results

In this section, we show that for k ∈ {1, 2, 3, n -2, n -1} or for n ≤ 9, no algorithm in the min-CORDA model allows to clear an n-node graph using k robots. We start with a simple result.

Lemma 6 For any n > 2 and for any exclusive configuration C, there is no algorithm that solves the exclusive perpetual graph searching problem in a n-node ring using n -1 robots starting from C.

Proof. In any configuration with n -1 occupied nodes, only two robots may move without violating the exclusivity property: the two robots adjacent to the unoccupied node. Since these two robots have the same view of the network, whatever be the algorithm in the min-CORDA model, they take the same decision. Either they never move and the ring cannot be cleared, or both decide to move to their unoccupied neighbor. In the latter case, their moves can be scheduled (due to the asynchronicity) such that they collide.

Let us consider the case of two robots in a ring with at least three nodes. Two nodes u and v of an n-node ring are called diametral if either n is even and there are two shortest paths between u and v; or n is odd and the length of the two paths from u to v differ by one. We say that two robots occupy a diametral configuration if they are occupying two diametral nodes.

We show that any algorithm for perpetual searching with two robots needs to reach a configuration where the two robots occupy two diametral nodes. Then, we show that when the two robots reach occupy two diametral nodes they cannot break the symmetry and hence they cannot clear the ring. The next theorem follows.

Theorem 2 For any n > 2 and for any initial configuration C, there is no algorithm that solves the exclusive perpetual graph searching problem in a n-node ring using k ≤ 2 robots starting from C.

Proof. Since there is no strategy to clear a ring using one robot, it follows that at least two robots are necessary. to perpetually clear a ring.

We first give general remarks on the clearing of a ring with two robots, independently of the distributed model of computation. Let us assume only two robots are occupying the nodes of a n-node ring, n > 2, all edges of which are initially contaminated. If the two robots never occupy adjacent nodes, then the ring will never be cleared. Therefore, consider the first time that such a situation occurs. Let u and v be the two neighbors occupied by the robots at this step. Then, all edges but {u, v} are contaminated at this step. Moreover, for the ring to be eventually clear, there must be a later step such that, up to a symmetry, the robot that was occupying v is now at w = v and the other robot reaches w ′ the neighbor of w on the path between u and w not containing v. In particular, this proves that, at some step of any clearing strategy of the ring, the two robots are occupying diametral nodes.

In what follows, we show that no algorithm in the CORDA model can ensure the above properties because the symmetry cannot be broken when the robots pass through diametral nodes. This will prove the theorem.

We consider an adversarial scheduler that always alternates the moves of the two robots until it reaches a diametral configuration for the first time. That is, it first makes one robot do its Look-Compute-Move actions, and then do the same with the second robot, and so on. By the above remarks, if a diametral configuration is never reached, then the ring cannot be cleared. Moreover, when a diametral configuration is reached, then there are no pendent move. Now there are two cases depending on the parity of n. In what follows, the robots always are in diametral configuration. Therefore, whatever be the algorithm used, both of them must move when they look such a configuration.

• Assume first that n is even. Then, since there are no pendent move, the adversarial scheduler can synchronize the two robots such that after their respective moves the configuration has not changed and there still are no pendant moves. Indeed, the two robots look and decide before any move and then both of them move before the next look. Going on this way, the robots remain in a diametral configuration and the ring cannot be clear.

Inria

• Now consider the case when n is odd. Consider the path between the two robots with an odd number of nodes and let v be the node on this path at same distance from both robots. Then, the adversarial scheduler makes the two robots do their Look-Compute actions and then their Move action. Since they are in a symmetrical configuration (with axis passing through v), they move symmetrically. Doing so, after each move of both robots, i.e., each time they are looking, the node v remains at equal distance from both robots. Therefore, it cannot be reached unless both robots collide in it. Hence, the ring cannot be cleared.

Let us now consider the case of three robots in a ring with at least four nodes. For ease of presentation, we give identifiers to the robots. Of course, the robots are anonymous in the sense that they are not aware of these identifiers and that no algorithm for searching the ring can make use of them. However, the adversarial scheduler will use them. Hence, let us call the three robots by A, B and C. At any step s, we denote by dist s (X, Y ) the distance (i.e., the minimum number of consecutive edges) between the nodes occupied by robots X and Y at this step (if no ambiguity, the subscript will be omitted).

Let C c be the configuration where the 3 robots occupy three consecutive nodes. Given any algorithm A for perpetually clearing a ring with 3 robots, we say that a configuration C is bad if, in this configuration, dist(A, B) ≤ dist(B, C) and there exists a robot such that, if this robot executes A in configuration C, then the configuration reached after its move is such that

dist(A, B) > dist(B, C).
In what follows, we show that any algorithm for perpetually clearing a ring with 3 robots must always avoid the configuration C c . Then, we show that such an algorithm cannot avoid to reach a bad configuration. Finally, we show that from any bad configuration, it is possible to schedule the three robots such that either they reach the configuration C c , or (1) each robot is scheduled at least once; and (2) this reaches a configuration such that dist(A, B) ≤ dist(B, C) and B has not met C in the meantime; and (3) if the new configuration is not C c , then from this new configuration, A will reach another bad configuration before B meets C.

Since any algorithm for perpetually clear the ring must ensure that B meets infinitely often C, this proves that such an algorithm cannot exist.

Theorem 3 For any n > 3 and for any initial configuration C, there is no algorithm that solves the exclusive perpetual graph searching problem in a n-node ring using 3 robots starting from C.

Proof. First, if n = 4, the single node that is not occupied cannot be reached without collision. Therefore, let us assume that n > 4.

For purpose of contradiction, let us consider any algorithm A that perpetually clears the ring with 3 robots. Let us consider the periodic infinite sequence S of moves of the robots following A, subject to a scheduler that alternate the robots, i.e., first A makes its Look-Compute-Move actions, then B, then C and so on. The goal of considering such a scheduler is to be able to analyze the behavior of A in some particular configurations (without pending moves). Then, taking use of a more clever scheduler, A can be faked. There are two cases to be considered.

Case 1. Let us first assume that S contains the configuration C c where the three robots are occupying three consecutive nodes. Considering the moves just before and just after this configuration, we can derive two facts. First, in the configuration where two robots are adjacent and the third one is at distance two of the closest of the others, if it is the turn of the third one, it will get closer to the other robots and reached the configuration C c . Second, in the configuration C c , if it is the turn of a robot not in the middle, then it moves to its unoccupied neighbor.

Then, let us consider the following adversarial scheduler against A. First, it schedules the robots alternatively until they reach configuration C c . W.l.o.g., say B is in the middle. From this step, the adversarial schedules twice A, then B and then twice C. That is, A moves to its unoccupied neighbor, then comes back; then B cannot move, and finally C goes and back. Clearly, A cannot perpetually clear the ring against the proposed adversarial, a contradiction.

Case 2. Second, assume that C c never occurs in S. Note that, in any infinite sequence of moves that perpetually clear the ring, the three robots must be pairwise adjacent infinitely often.

W.l.o.g. (up to a renaming of the robots), since S does not contain the configuration C c , there must be a step s such that A and B are occupying adjacent nodes and then a further step s ′ when B and C are occupying adjacent nodes, such that C and A never are never occupying adjacent nodes between steps s and s ′ (including s and s ′ ). Therefore, between steps s and s ′ , there must be a step s 0 such that x = dist s0 (A, B) ≤ dist s0 (B, C) = y and after the next step, dist s0+1 (A, B) > dist s0+1 (B, C). Let C 0 be the configuration reached at step s 0 . Note that C 0 is a bad configuration.

The proof is a case-analysis depending on whether x = y or not and on how Algorithm A behaves in configuration C 0 , i.e., what are the moves that can be done by robots A, B and C in configuration C 0 when executing A.

• Let assume first that x = y. Then, the three robots are scheduled simultaneously, that is, all three robots performs a Look-Compute-Move cycle, following A in configuration C 0 . Moreover, if B decides to move in configuration C 0 , we make it moving towards A. This is possible since C 0 is symmetric from the point of view of B. Similarly, A and C must move symmetrically: either both of them go towards B, or they move to their neighbor on the path between A and C not containing B.

There cannot be a collision since otherwise A would not be a valid algorithm. Therefore, after each robot has moved, the reached configuration C 1 is such that dist(A, B) ≤ dist(B, C) and B has not met C. There are two cases, depending on C 1 .

-Either C 1 is C c and then Case 1. ensures that A cannot perpetually clear the ring, a contradiction. -Or, we go back using the scheduler that alternates the three robots until a new bad configuration is reached. The same discussion as above ensures that another bad configuration will be reached before B mets C. Note that, possibly Configuration C 1 is a bad configuration. Again, we process as in Case 2. Therefore, we can avoid forever that B mets C, which contradicts the correctness of A.

• Second, assume that x < y. Note that, since only one robot moves during step s 0 + 1 and dist s0+1 (A, B) > dist s0+1 (B, C), this implies that the robot that moves during this step is B. Therefore, y = x + 1 and the configuration C ′ 0 reached after step s 0 + 1 is symmetric with C 0 . In particular, B cannot distinguish C 0 and C ′ 0 . Note that, Robot A must move in configuration C ′ 0 , and Robot C must move in configuration C 0 . Indeed, otherwise, scheduling alternatively Robot B, then Robot A, then Robot B, then Robot C, and so on, Algorithm A would oscillate between configurations C 0 and C ′ 0 which cannot clear the ring since n > 4. Moreover, in the configuration C ′ 0 , robot A acts in the same way as robot C in the configuration C 0 (by symmetry). There are three cases to be considered.

Inria

-First assume that x = 0 and, when executing Algorithm A in configuration C 0 , robot C goes to the neighbor of B. In that case, configuration C c is reached then Case 1 ensures that A cannot perpetually clear the ring, a contradiction. -Second assume that x > 0. In that case, B and C first look and compute in configuration C 0 , then B moves. Note that, because x > 0 and y = x + 1, B does not meet C. Then, A and B look and compute in configuration C ′ 0 . Then, B moves and reaches the configuration C 0 . Finally, B and C move. As mentioned above, they must move symmetrically, i.e., in opposite orientation. Therefore, after each robot has moved (B has moved twice), the reached configuration C 1 is such that dist(A, B) ≤ dist(B, C) and B has not met C. We get a contradiction as above.

-The last case to be considered is when x = 0 and, when executing Algorithm A in configuration C 0 , robot C goes to its neighbor that is not adjacent with B. In that case, there are two possibilities for Robot A in configuration C 0 . * Either it does not move, in which case, the three robots look and compute in Configuration C 0 , then C and A move first (but A remains on its position) and finally B moves. Therefore, after each robot has moved (B has moved twice), the reached configuration C 1 is such that dist(A, B) ≤ dist(B, C) and B has not met C. We get a contradiction as above. * Otherwise, Robot A looks, computes and moves. Here the configuration is such that B is at distance 2 from both other robots. Then, A and C looks, computes and moves. Since their view are identical, they must do the same move.

If they go to the neighbors of B, we have reached the configuration C c and then Case 1 ensures that A cannot perpetually clear the ring, a contradiction. Otherwise, B looks, computes and moves. Since its view is symmetrical, the adversarial can let it move toward A. Therefore, after each robot has moved (B has moved twice), the reached configuration C 1 is such that dist(A, B) ≤ dist(B, C) and B has not met C. We get a contradiction as above.

By using similar argument as Theorem 2 the next theorem can be shown.

Theorem 4 For any n > 2 and for any exclusive initial configuration C, there is no algorithm that solves the exclusive perpetual graph searching problem in a n-node ring using n -2 robots starting from C.

Proof. If k = n -2, then all the nodes of the ring but two are occupied. If n ≤ 4, then k ≤ 2 and hence it is impossible to clear the ring. Let us assume that n ≥ 5. Two cases may arise: either the two empty nodes are consecutive (see Fig. 3a) or they are far (see Fig. 3b). In both cases, all the possible configurations are symmetric and the axis of symmetry either passes on the middle of the interval of empty nodes or in the middle of the two intervals of occupied nodes between the empty nodes, respectively. In the first case there are only two robots which can move without creating a collision: those close to an empty node. The adversary can force to move only one of these two symmetric robots while the other robot does not perform the look phase (it does not wake up). The obtained configuration falls into the second case (see Fig. 3c) and the ring is not searched. Hence, we can assume without loss of generality that the initial configuration falls in the second case.

In such configurations only the three or four robots close to an empty node can move and two cases may arise: the two intervals of occupied nodes between the empty nodes have the same size or not. In the first case, the configuration is periodic with two axis of symmetry and the second axis passes through the two empty nodes (see Fig. 3d). In this case, no robot can move as the four robots close to an empty interval are indistinguishable and the adversary can force them to move together causing a collision. Hence let us assume that the two intervals of occupied nodes between the empty nodes have different sizes, which implies that the configuration is symmetric but not periodic.

Let us denote as A and B the sizes of the smallest and the largest intervals of consecutive occupied nodes, respectively. Moreover, we denote ad x and x ′ the two symmetric robots at the border of A and with y and y ′ the two symmetric robots at the border of B. Note that x (y, respectively) cannot be distinguished by x ′ (y ′ , respectively) and hence they will do the same movements. see Fig. 3b for a visualization. There are two possible movements:

1. x and x ′ move towards y and y ′ , respectively; 2. y and y ′ move towards x and x ′ , respectively. By performing the first (second, respectively) movement, A is decreased (increased, respectively) and B is increased (decreased, respectively). We now show that if an algorithm does one of such movements, then it cannot do the other movement in a subsequent step where A > 1 and it still holds that A < B. By contradiction let us assume that an algorithm first does movement 1 and then movement 2, the other case is symmetric. Let us assume that the adversary moves x towards y but let the symmetric movement of x ′ towards y ′ pending, that is x ′ performs the look and compute phases but it does not move yet. In the obtained configuration if the new y moves towards the new x, then, as the configuration is still symmetric, also y ′ as to move towards x ′ causing a collision between x ′ and y ′ due to the pending move of x ′ . It follows that an algorithm has to do always the same movement: either moving x towards y or moving y towards x.

We first analyze the case where an algorithm always do movement 2. If an algorithm moves y towards x, then A is increased and B is decreased until either A = B or A = B -1. The case that A = B has been already shown to be impossible. If A = B -1, the adversary can force y to move towards x while the symmetric move of y ′ remains pending. The configuration Inria obtained is identical to the previous one but the intervals are flipped. Hence the new y ′ (which is the old x ′ ) has to move towards the new x ′ (which is the old y ′ ), causing a collision due to the pending move of the latter. Therefore, an algorithm can only move x towards y (movement 1) until the two empty nodes are adjacent (Fig. 3a) or at distance one (Fig. 3c). In the case of two empty adjacent nodes, as already discussed, the adversary can force to move only one of two symmetric robots adjacent to an empty node and then the two empty nodes will be at distance one. We then assume that the two empty nodes are at distance one. In this configuration there are three robots that can move: the robot in the middle of the empty nodes which we call x and the two symmetric robots close to an empty node which we call y and y ′ . Two movements are possible: x move towards an arbitrary direction or y and y ′ move towards x. If the first movement is performed, we go back to the configuration with two empty adjacent nodes and from this configuration again the adversary can force to move always the same robot infinitely many times without searching the ring. If y and y ′ move towards x, the adversary can force to move only one among y and y ′ , let us say y. In the obtained configuration, the two empty nodes are at distance two, that is A = 2 < B and, as shown above, the algorithm has to perform movement 1, that is nodes x and x ′ of the new configuration have to move towards nodes y and y ′ . Note that node x of the new configuration corresponds to node y of the old one. Hence, the adversary can force to move only such node, obtaining again the configuration with the empty nodes at distance one. This two configurations can alternate infinitely many times by moving always the same robot and hence without searching the ring.

The next theorem is proven by an exhaustive study of the possible configurations. To prove Theorem 5, we first need the following lemmata.

Lemma 7 Let an even number k of robots be in a symmetrical exclusive configuration in an nnode ring with n odd. No algorithm starting from (or reaching at some step) such a configuration allows the perpetual searching of the ring.

Proof. Indeed, there is a node v that is unoccupied on the axis of symmetry of the initial configuration. Because of the symmetry, the adversarial scheduler can e ensure that at each step, two robots occupying symmetrical positions execute the same move. Thus, the axis of symmetry always remains the same. Therefore, if at some step, the vertex v would be occupied, then during the previous step, both its neighbors were occupied and both robots occupying these neighbors would move to v. Hence, v cannot be occupied without collision.

Lemma 8

No algorithm starting from (or reaching at some step) a configuration where all the k < n robots occupy consecutive nodes allows the perpetual searching of the ring.

Proof. The proof is similar to the one in the case k = 3, in the proof of Theorem 3.

Theorem 5 For any 2 ≤ k < n ≤ 9 and for any initial configuration C, there is no algorithm that solves the exclusive perpetual graph searching problem in a n-node using k robots starting from C.

Proof. By the previous results of this section, for any k ∈ {1, 2, 3, n -2, n -1}, no algorithm allows k robots to perpetually clear an n-node ring. Therefore, it only remains to show the theorem for (k, n) ∈ {(4, 7); (4, 8); [START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF][START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF]; [START_REF] Blin | Perpetual Graph Searching[END_REF][START_REF] Angelo | How to gather asynchronous oblivious robots on anonymous rings[END_REF]; [START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF][START_REF] Angelo | How to gather asynchronous oblivious robots on anonymous rings[END_REF]; [START_REF] Bonnet | Asynchronous exclusive perpetual grid exploration without sense of direction[END_REF][START_REF] Angelo | How to gather asynchronous oblivious robots on anonymous rings[END_REF]}. We prove it by an exhaustive study of the possible configurations in each case.

In what follows, we consider any algorithm A for perpetual graph searching. The adversary schedules the moves sequentially: the adversary chooses a set of robots (generally one robot or two robots having symmetrical positions) that look, then they compute and move simultaneously. In particular, this implies that the robots always look the current configuration, i.e., there is no problem of asynchrony. Of course, in any configuration, any Algorithm must execute some move since otherwise the system would never change and the ring cannot be cleared.

In the proof below, we use the Figures 4567. In these figures, grey nodes are the occupied nodes. An arc from Configuration C 1 to Configuration C 2 , with label a means that Robot a in Configuration C 1 moves such that Configuration C 2 is reached. Note that the labels of robots in C 1 and C 2 may be not consistent because of the symmetries.

• Case (k, n) = (4, 7). In that case, there are only four distinct configurations that are depicted in • Case (k, n) = (4, 8). In that case, there are 8 distinct configurations that are depicted in Figure 5. By Lemma To conclude, in Configuration B 5 , all robots have distinct views, but any move of one of the robot would lead to one of the previous configurations that we prove to be forbidden.

• Case (k, n) = [START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF][START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF]. In that case, there are 5 distinct configurations that are depicted in Figure 6. To conclude, it is sufficient to note that, when C 1 is eventually reached (which must be by above discussion), then the adversary can ensure to oscillate between Configurations C 1 and C 3 , such that all robots execute a cycle infinitely often (only e, c and a actually may move) without clearing the ring.

• Case (k, n) = [START_REF] Bonnet | Asynchronous exclusive perpetual grid exploration without sense of direction[END_REF][START_REF] Angelo | How to gather asynchronous oblivious robots on anonymous rings[END_REF]. In that case, there are 7 distinct configurations that are depicted in Figure 7. • Case (k, n) = (4, 9). In that case, there are 10 distinct configurations that are depicted in Figure 8. If Algorithm A eventually reaches Configuration F 1 , then the clearing fails by Lemma 8.

By
By
We then assume it is not the case.

First, let us assume that, in configuration F 6 , A allows other move than moving Robot a toward b. In that case, the adversary schedules Robots one by one. Moreover, it ensures that Robot a does not move in Configuration F 6 by moving another robot first. This case is depicted in Figure 10 where the dotted move ins never executed. Hence, in that case, the green vertices are never cleared (of course, the adversary ensures that, in the case of symmetries, e.g. from F 8 to F 7 , the considered robot moves to the "bad" side). Indeed, we can check that, for any configuration, if the green vertices are initially contaminated, then after any move leading to another configuration, the new green vertices are contaminated. Therefore, such an Algorithm A cannot clear the ring.

Algorithm Ring Clearing

In this section, we give an algorithm, called Algorithm Ring Clearing, to clear a ring of n ≥ 10 nodes with 5 ≤ k < n -3 robots (except for n = 10 and k = 5) starting from any rigid configuration.

Algorithm Ring Clearing works in two phases and it is formally described in Fig. 11. In the first phase, Algorithm Align is executed until one configuration in the set of configurations A (described below and that contains C * ) is reached. Then, the robots execute the algorithm illustrated in Fig. 12. The assumption of initial rigidity ensures that, in the entire algorithm, only one robot is allowed to move at one time. Moreover, the set of configurations in the two phases are disjoint and hence the robots can always distinguish which phase is performing.

We denote as A the set of the following configurations. Note that the configuration C * belongs to the set of configurations A-f. A-a: Configurations with sequence of k -2 adjacent robots and two adjacent robots separated by one empty node from the first sequence (Fig. 12a).

A-b: Configurations with sequence of k -2 adjacent robots, one robot separated by one empty node from the sequence, and another robot not adjacent to any other one (Fig. 12b).

A-c: Configurations with sequence of k -2 adjacent robots, one robot separated by one empty node from the sequence, and another robot separated by two empty nodes from the sequence on the other side of the first robot. (Fig. 12c).

A-d: Configurations with sequence of k -3 adjacent robots, two adjacent robots separated by one empty node from the first sequence, and another robot separated by two empty nodes from the sequence on the other side of the two robots (Fig. 12d).

OR (q0 > 0, q k-1 > 2, q1 = 1, qi = 0 ∀i ∈ {2, 3, . . . , k -2}) // A-b 6 OR (qi = 0 ∀i ∈ {0, 1, . . . , k -4}, q k-3 = 2, q k-2 > 0, q k-1 = 1) // A-c 7 OR (q0 > 0, q1 = 0, q2 = 1, qi = 0 ∀i ∈ {3, 4, . . . , k -2}, q k-1 > 2) // A-d 8 OR (qi = 0 ∀i ∈ {0, 1, . . . , k -3}, q k-2 > q k-1 > 0, q k-2 + q k-1 > 3) // A-f 9 then 10 move towards q k-1 ;

11 if (q0 > 2, q k-1 > 0, qi = 0 ∀i ∈ {1, 2, . . . , j -2}, q k-2 = 1) // A-b 12 OR (q0 = 2, qi = 0 ∀i ∈ {1, 2, . . . , k -4}, q k-3 = 1, q k-2 = 0, q k-1 > 0) // A-d 13 OR (q0 = 1, qi = 0 ∀i ∈ {1, 2, . . . , k -4}, q k-3 = 1, q k-2 = 0, q k-1 > 1) // A-e 5 Gathering in a ring in the min-CORDA model

In this section, we devise a strategy to accomplish the gathering task on a ring under the min-CORDA model. The problem requires the robots to reach a common node and remain in there. Hence, more than one robot must be allowed to occupy a node, i.e. a multiplicity occurs. We assume that the robots have the local multiplicity detection capability. This is necessary as in [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF] it has been proved that the gathering on rings is unfeasible without any multiplicity detection, and the local is the lightest one that can be assumed.

In accordance to the tasks previously shown, we make use of procedure Align in order to achieve configuration C * starting from any (exclusive) rigid configuration on rings of n > k + 2 nodes and k > 2 robots. In fact, any configuration with n = 2, n = k + 1, or n = k + 2 nodes is symmetric. Hence, the next algorithm provides a full characterization of rigid configurations where the gathering can be accomplished. Before providing the algorithm, we need some notation.

A configuration is said to be of type C * if it is composed by an ordered sequence of j -2 intervals of length 0, one interval of length 1 and one interval of length nj -1, with 3 ≤ j ≤ k. Consequently, also the nodes of the ring can be considered ordered according to the intervals' order. Hence, the first two nodes of the sequence will constitute interval q 0 = 0 in the current configuration. Clearly, C * is a C * -type configuration.

Rule Contraction allows to move any robot occupying the first node of a C * -type configuration towards the second one. Possibly, such nodes can be occupied by many robots. Whenever a robot r wakes up, it executes the algorithm Gathering given in Fig. 14. From C * -type configurations, the algorithm simply applies Contraction until only two nodes are occupied. Note that, at each intermediate step, the current configuration is always a C * -type, and the algorithm allows to move the robot(s) from the first node of the current interval q 0 towards the second one. Eventually, the number of intervals of length 0 is reduced by one. This is repeated until only two nodes at distance 2 remain occupied. Note that, in such a configuration, k -1 robots are gathered on the same node and the other occupied node contains a single robot. From this configuration the robots can distinguish which is the node occupied Inria by a single robot by using the local multiplicity detection. Therefore, only the single robot is allowed to move towards the other occupied node until joining it, while robots composing the multiplicity do not move. We can now state the next theorem.

Theorem 8 There exists an algorithm performing the gathering of k > 2 robots on rings of n > k+2 nodes when the initial configuration is exclusive and rigid, and the robots are empowered with the local multiplicity detection.

Further work

In this work, we provided a unified strategy for solving three tasks in the minimalist-CORDA model on ring topologies when the initial configuration is rigid. Namely we solved the exclusive perpetual search, the exclusive perpetual exploration and the gathering with local multiplicity detection capability. Moreover, the given algorithms solve some open problems and the impossibility results provided for the exclusive perpetual graph searching problem fully characterize any initial configuration.

Our work opens two main research direction: use the Align algorithm to solve other problems in rigid configurations and devise similar algorithms to handle symmetric or periodic configurations.

3 5 Let 8 else 9 Let 13 Let 17 Apply

 5891317 Apply reduction0(C, W ); 4 else C ′ be the configuration obtained after reduction1(C, W ); 6 if not symmetric(C ′ ) then 7 Apply reduction1(C, W ); C ′′ be the configuration obtained after reduction2(C, W ); 10 if not symmetric(C ′ ) then 11 Apply reduction2(C, W ); 12 else C ′′′ be the configuration obtained after reduction-1(C, W ); 14 if not symmetric(C ′ ) then 15 Apply reduction-1(C, W ); 16 else reduction1(C, W );

Figure 1 :

 1 Figure 1: Algorithm Align.

Figure 2 :

 2 Figure 2: Procedure reduction.

Figure 3 :

 3 Figure 3: Configurations with k = n -2.

Figure 4 .Figure 4 :

 44 Figure 4: Theorem 5. Case (k, n) = (4, 7). Grey nodes are the occupied ones.

Figure 5 :

 5 Figure 5: Theorem 5. Case (k, n) = (4, 8). Grey nodes are the occupied ones.

By Lemma 8 ,Figure 6 :

 86 Figure 6: Theorem 5. Case (k, n) = (5, 8). Grey nodes are the occupied ones.

Figure 7 :

 7 Figure 7: Theorem 5. Case (k, n) = (6, 9). Grey nodes are the occupied ones.

Figure 8 :F9Figure 9 :

 89 Figure 8: Theorem 5. Case (k, n) = (4, 9). Grey nodes are the occupied ones.

F6Figure 10 :

 10 Figure 10: Theorem 5. Case (k, n) = (5, 9). Grey nodes are the occupied ones.

Figure 11 :Theorem 6

 116 Figure 11: Algorithm Ring Clearing.

2 Align 4 if 5 Apply 6 else 7 if r is not part of a multiplicity then 8

 245678 Algorithm: Gathering Input: Rigid and exclusive configuration C1 if C is not a C * -type configuration then More than two nodes are occupied then Contraction(C); Move towards the other occupied node;

Figure 14 :

 14 Figure 14: Algorithm Gathering.

  and only if C is either rigid or it admits only one axis of symmetry passing through the supermin; (ii) |I C | = 2 if and only if C is either aperiodic and symmetric with the axis not passing through any supermin or it is periodic with period n

2 ; (iii) |I C | > 2 if and only if C is periodic, with period at most n 3 .

  8, if Algorithm A reaches Configuration B 1 , then the clearing fails. Similarly, if Configuration B 8 is reached then the clearing fails since, in such a configuration, all robots have the same view. Therefore, the adversary can schedule all robots simultaneously such that they all move clockwise, which does not clear the ring. Now we show that any algorithm A eventually reaches Configurations B 1 or B 8 and thus cannot clear the ring.In Configuration B 3 , only Robots a and b can move since, otherwise, the adversary could simultaneously move the other two robots (that have the same view) so that they collide in their common unoccupied neighbor. Moreover, since Robots a and b have the same view, the adversary can schedule both of them simultaneously such that Configuration B 8 is reached. In Configuration B 7 , all robots have the same view. Then, the adversary can schedule Robots a and b such that Configuration B 8 is reached. Therefore, if A reaches Configurations B 3 or B 7 , it will eventually reach Configuration B 8 , which, by previous paragraph, cannot clear the ring. Thus, A must never reach Configurations B 3 or B 7 .

  Lemma 7, if Algorithm A reaches Configuration D 3 or D 4 , then the clearing fails. If Configuration D 2 is reached, all robots have the same view, if one of them can move, the one with the same common unoccupied neighbor can also move which would create a collision. Therefore, if Algorithm A reaches Configuration D 2 , then the clearing fails. If Configuration D 1 is reached, only Robots a and b may move (if the other two robots with an unoccupied neighbor move, they would collide in it). In that case, Robots a and b are scheduled simultaneously which reaches Configuration D 2 that is forbidden. Therefore, any Algorithm A that clears the ring must never reach one of these four configurations.

  Lemma 7, if Algorithm A reaches Configuration E 1 to E 6 , then the clearing fails. Therefore, in particular, any Algorithm A that clears the ring never reaches Configuration E 7 or only b is allowed to move towards a in that configuration. Similarly, in Configuration E 9 , the possible moves are: Robot b moving towards c and Robot a moving towards d. In Configuration E 10 , the possible moves are: Robot b moving towards c, Robot c moving towards d, and moving Robot d. Any movement of Robots a, b, c are allowed in Configuration E 8 . It is easy to check that, allowing only these moves cannot clear the green vertices.

  By previous paragraph, in Configuration F 6 , Algorithm A only allows Robots a to move towards b. Moreover, Configuration F 6 followed by Configuration F 2 must be met infinitely often. Therefore, we can assume that F 2 is the initial configuration and that we have to go back to it via F 6 . Such an Algorithm A cannot clear the ring since the adversary can ensure that only Configurations F 2 , F 7 , F 8 and F 9 are perpetually reached, which does not allow to clear the green nodes. Therefore, in Configuration F 9 , Algorithm A must allows Robots a to move towards c (all other robots decide not to move but d that may move remaining in the same configuration).

Now, assume that, in Configuration F 9 , A allows other move than moving Robot a towards c or moving d.

  In that case, the adversary executes the following schedule: in F 2 , it schedules Robot a going to Configuration F 6 , then in F 6 , it schedules all robots but a, that do not move, and then a going back to Configuration F 2 without having cleared the ring. Therefore, in Configuration F 2 , Algorithm A does not allow Robot a to move toward b. Since, because Configuration F 1 cannot be reached, the only possible move is to allow Robot c (resp., d) to move towards a (resp., towards b). conclude, we prove that, in Configuration F 10 , Robot e must be allowed to move. First, assume Robot b is allowed to move in F 10 . Then, the adversary can schedule Robots c and d in F 2 but only Robot c moves, i.e., Robot d has looked and computed but not moved yet. Therefore, arriving in Configuration F 10 , the adversary can schedule Robot b and makes it moving simultaneously with Robot d which results in a collision. Hence, Robot b have to decide not to move in Configuration F 10 . 10 . Then, the adversary can execute the following schedule: Robot c moves in F 2 to reach F 10 , then Robot a moves reaching F 9 (resp., Robot d moves to F 8 and then Robot e moves to F 9 ), then all Robots but a are scheduled without moving in F 9 (see above), then Robot a move to reach back F 10 and then, the adversary can alternate Configurations F 9 and F 10 (resp., F 8 , F 9 and F 10 ) without clearing the ring.Similarly, assume for purpose of contradiction, that Robot c is allowed to move in F 10 . Then, the adversary can execute the following schedule: in F 2 , Robots a, b, e are scheduled without moving (see above), then Robot c moves in F 2 to reach F 10 , then Robot c moves reaching back F 2 , and then this cycle is done again with Robot d moving in F 2 instead of c. Thus, the adversary can alternate Configurations F 2 and F 10 without clearing the ring.Therefore, in Configuration F 10 , only moving e and b may be possible. Of course, if moving Robot e is not allowed, then the adversary can schedule Robot c in F 2 to reach F 10 , and then, it schedules all robots, where only Robot b moves perpetually remaining in Configuration F 10 which does not clear the ring.To conclude the proof, the adversary does the following. In Configuration F 2 (we proved above that we may assume we can start with this configuration), Robot c (or d) moves and reaches Configuration F 10 , where Robot e moves which reaches Configuration F 6 , where all robots but a are scheduled without moving. Finally, Robot a is moving reaching back Configuration F 2 . It is easy to check that this does not allow to clear the ring.

	To

). Grey nodes are the occupied ones.

We now show that, in Configuration F 2 , Algorithm A has to allow Robots c and d to move and that these are the single possible moves. Indeed, let us assume that, in Configuration F 2 , Algorithm A allows Robot a (resp., b) decides to move toward b (resp., towards a).

Second, assume for purpose of contradiction, that Robot a (resp., Robot d) is allowed to Inria move in F

RR n°8013

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

A-e: Configurations with sequence of k -3 adjacent robots, two adjacent robots separated by one empty node from the first sequence, and another robot separated by one empty node from the sequence on the other side of the two robots (Fig. 12e).

A-f: Asymmetric configurations with sequence of k -1 adjacent robots and one single robot (Fig. 12f).

The pseudo-code of Algorithm Ring Clearing is reported in Fig. 11. First, at line 2, the algorithm performs Align until a configuration in A is achieved. Let us denote as r and r ′ as in the proof of Theorem 6. At line 4, the algorithm identifies robot r in a configuration in A-a. The configuration read by r is (q 0 , q 1 , . . . , q j ) = (0, 1, 0, 0, . . . , 0, q j ), where q j > 2. In this case r has to move towards the direction opposite to r ′ that is towards q j (line 10). Note that as the configuration is rigid, only r can read such a configuration. Configurations in A-b are identified at lines 5 and 11. In particular, robot r can read the configuration in two directions, depending on the size of the its adjacent intervals. If it reads in clockwise order with respect to Fig. 12, then the configuration read is (q 0 , q 1 , . . . , q j ) = (q 0 , 0, 0, . . . , 0, 1, q j ), where q 0 > 2 and q j > 0 (line 11) and r has to move towards q 0 (line 15). Otherwise, the configuration read is (q 0 , q 1 , . . . , q j ) = (q 0 , 1, 0, 0, . . . , 0, q j ), where q 0 > 0 and q j > 2 (line 5) and r has to move towards q j (line 10). Configurations in A-c, A-d, A-e, and A-f are identified similarly at lines 6, 7 and 12, 13, 8, respectively. Finally, we observe that the conditions at lines 4-13 are pairwise disjoint and, in the same configuration, only one conditions is satisfied for exactly one robot.

Procedure: Ring Clearing Input: Rigid and exclusive configuration C with view W = (q0, q1, . . . , q k-1 ) seen from a robot r

// A-a of the sequence of k -1 robots which is the closest to r. Note that, as the initial configuration is assumed to be rigid, then we can always distinguish robot r ′ . The algorithm moves r ′ towards the only direction allowed. The obtained configuration is either A-a or A-b.

In the following, we show that if a configuration is in any of the configurations in A, the algorithm perpetually cycles among them in the sequence (A-a, A-b, A-c, A-d, A-e). Hence the algorithm never goes back to a configuration in A-f and without loss of generality, we can assume that the first configuration is of type A-a.

In this case, we call S the sequence of k -2 adjacent robots and r and r ′ the robot at distance 3 and 2 from S, respectively. At line 4, the algorithm identifies robot r in a configuration in A-a. The view read by r is (q 0 , q 1 , . . . , q k-1 ) = (0, 1, 0, 0, . . . , 0, q k-1 ), where q k-1 > 2. In a configuration of type A-a, the edges which are searched are the internal edges of S and the edge between r and r ′ . The algorithm first searches the edges in the sequence of empty nodes. To this aim, it moves robot r towards the direction opposite to r ′ (line 10). Note that as the configuration is rigid, only r can read such a configuration.

The configuration obtained is of type A-b where the distance between the two single robots is 2. Configurations in A-b are identified at lines 5 and 11. In particular, robot r can read the configuration in two directions, depending on the size of the its adjacent intervals.

In this way, r searched the edge where it passed through. The algorithm keeps on moving r in the same direction until it reaches a configuration of type A-c, in this way the configuration is still A-b and all the edges between r and r ′ where r passed through are searched. Note that, the robots are always able to identify the correct direction thanks to the position of robot r ′ . More precisely, robot r can read the configuration in two directions, depending on the size of the its adjacent intervals. If it reads in clockwise order with respect to Fig. 12, then the configuration read is (q 0 , q 1 , . . . , q j ) = (q 0 , 0, 0, . . . , 0, 1, q k-1 ), where q 0 > 2 and q k-1 > 0 (line 11) and r has to move towards q 0 (line 15). Otherwise, the configuration read is (q 0 , q 1 , . . . , q j ) = (q 0 , 1, 0, 0, . . . , 0, q k-1 ), where q 0 > 0 and q k-1 > 2 (line 5) and r has to move towards q k-1 (line 10).

When the configuration is of type A-c, the only edges which are not searched are the two edges between r ′ and S and the three edges between r and S. Let r ′′ be the robot on the border of S which is the closest to r ′ . If the configuration is of type A-c, the algorithm moves robot r ′′ towards r ′ , searching the two edges between r ′ and S \ {r ′′ }. The obtained configuration is of type A-d, where the only edges which are not searched are those between r and S. Therefore, the algorithm moves r towards S obtaining first a configuration of type A-e and again a configuration of type A-a. Note that, in all the above configuration, it is always possible to distinguish robots r, r ′ and r ′′ . Moreover, the direction of the movements can be identified by the robots thanks to the position of robots r, r ′ and r ′′ themselves. Summarizing, the algorithm perpetually cycles among configurations A-a -A-e.

Clearing an n-node ring using n -3 robots

In this section, we propose a specific algorithm to clear any n-node ring, n ≥ 10 using n -3 robots. Together with the previous algorithm and the impossibility results, this closes all the cases, but for n = 10 and k = 5.

In any exclusive configuration with k = n -3 robots, all the nodes of the rings but three are occupied. In other words, the ring is made of at most three sequences of adjacent occupied nodes. We denote by A, B and C the number of nodes in such three sequences. If two empty nodes are adjacent, the corresponding sequence has size 0. Note that, as the configuration is rigid, such three sequences are all different and then, we can assume w.l.o.g. that A < B < C. In the following, we denote a configuration as (A, B, C). We call final configurations the three configurations: (0, 2, k -2), (0, 3, k -3), (1, 2, k -3). Note that, since k = n -3 ≥ 7, the final configurations are well defined and distinguishable, that is B is always strictly smaller than C. Our algorithm is denoted as NminusThree and it is formally given in Fig. 13. It works in two phases: In the first phase, it creates a final configuration and in the second one it performs the perpetual searching.

Inria

The first phase is performed if the configuration is not one of the final ones and it is accomplished by performing the following rules in the priority given by the following ordering. Proof. We first prove that, any configuration obtained by applying Rules R1.1-R1.3 is still rigid. Let us denote as A ′ , B ′ and C ′ the number of nodes in the sequences of occupied nodes obtained after one movement that corresponds to A, B and C, respectively. By performing Rule R1.1, we obtain that A ′ = A -1, B ′ = B, and

To conclude the proof, it is enough to observe that if k ≥ 7 (that is n ≥ 10) and the configuration is not final, one of the conditions of Rules R1.1-R1.3 is always true. Moreover, by the discussion which follows the rules, the phase one of the algorithm terminates in a finite number of steps in a final configuration.

The second phase of the algorithm performs the searching. It starts from any final configuration and performs the following rules. The following theorem states the correctness of the algorithm.

Theorem 7 Starting from any exclusive and rigid configuration, Algorithm NminusThree solves both the perpetual exclusive graph searching and exploration problems using n -3 robots in any n-node ring, n ≥ 10.

Proof. By the hypothesis that n ≥ 10, it follows that k ≥ 7, and then the final configurations are well defined and distinguishable. Moreover, by Lemma 9 the first phase of the algorithm always achieves a final configuration. It remain to show that the second phase perpetually performs the searching. Note that if we perform Rule R2.i we obtain the configuration in the condition of Rule R2.((i mod 3) + 1). It follows that Rules R2.1-R2.3 are performed cyclically infinitely many times. Let us assume that the second phase starts from configuration (0, 2, k -2). In this configuration, the edges inside sequences B and C are cleared. By performing Rule R2.1,