D ' Gianlorenzo

Alfredo Angelo

Nicolas Navarra

Nisse

Robot Searching and Gathering on Rings under Minimal Assumptions *

Keywords: Distributed Computing, CORDA model, Gathering, Graph Searching * Cacul distribué, Modèle CORDA, Réunion, Nettoyage de graphe

Consider a set of mobile robots with minimal capabilities placed over distinct nodes of a discrete anonymous ring. They operate on the basis of the so called Look -Compute-Move cycle. Asynchronously, each robot takes a snapshot of the ring, determining which nodes are either occupied by robots or empty. Based on the observed configuration, it decides whether to move to one of its adjacent nodes or to stay idle. In the first case, it performs the computed move, eventually. The computation also depends on the required task. In this paper, we solve both the well-known Searching and Gathering tasks. In the literature, most contributions are restricted to a subset of initial configurations. Here, we design two different algorithms and provide a full characterization of the initial configurations that permit the resolution of the problems under minimal assumptions.

Introduction

In the field of robot-based computing systems, the study of the minimal settings required to accomplish specific tasks represents a challenging issue. We consider k robots initially placed on n distinct nodes of a discrete ring, and we solve two fundamental problems: the Searching (see, e.g., [?, ?, ?]) and the Gathering (see, e.g., [?, ?, ?, ?, ?]). Robots are assumed to be oblivious (without memory of the past), uniform (running the same deterministic algorithm), autonomous (without a common coordinate system, identities or chirality), asynchronous (without central coordination), without the capability to communicate. Neither nodes nor edges are labeled and no local memory is available on nodes.

The relevance of the ring topology is motivated by its completely symmetric structure. It means that algorithms for rings are more difficult to devise as they cannot exploit any topological structure, assuming that all nodes look the same. In fact, our algorithms are only based on robots' disposal and not on topology. Robots are equipped with visibility sensors and motion actuators, and operate in Look -Compute-Move cycles in order to achieve a common task (see [?]). 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 an adversary for each robot. Hence, robots that cannot communicate may move based on outdated perceptions. The scheduler that determines the timing of the Look-Compute-Move cycles is assumed to be fair, that is, each robot performs its cycle within finite time and infinitely often. The inaccuracy of the sensors used by robots to scan the surrounding environment motivates its discretization. Moreover, robots can model software agents moving on a computer network.

Initial configurations are assumed to be exclusive, that is, any node is occupied by at most one robot. On rings, different types of exclusive configurations may require different approaches. In particular, periodicity and symmetry arguments must be carefully handled. An exclusive configuration is called periodic if it is invariable under non-complete rotations. It is called symmetric if the ring has an axis of symmetry that reflects single robots into single robots, and empty nodes into empty nodes. It is called rigid if it is aperiodic and asymmetric. Searching: Graph searching has been widely studied in centralized [?] and distributed settings (e.g., [?]). 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 endpoints are occupied. However, a clear edge can be recontaminated if there is a path without robots from a contaminated edge to it. A graph is searched if all its edges are cleared. The searching is perpetual if it is accomplished infinitely many time. In this paper (and following [?, ?]), we also consider an additional constraint: the so called exclusivity property, that is, no two robots can be concurrently on the same node or cross the same edge. The study of perpetual graph searching in the discrete model provided here when the exclusivity property must be always satisfied has been introduced in [?] for tree topologies. Concerning rings, in [?] the case of rigid configurations has been tackled. Gathering: The gathering problem consists in moving all the robots towards the same node and remain there, that is a sort of complementary requirement with respect to the exclusivity property. On rings, under the Look-Compute-Move model, the gathering is unsolvable if the robots are not empowered by the so-called multiplicity detection capability [?], 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 by a single robot or more than one (i.e., a multiplicity occurs) without perceiving the exact number. 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 [?] some impossibility results have been proven. In detail, if the initial disposal of the robots is periodic, or it has an axis of symmetry passing through two edges, or there are only two robots, the gathering is unsolvable. Then, several algorithms have been proposed for different kinds of exclusive initial configurations in [?, ?, ?]. These papers left open some cases which have been closed in [?] where a unified strategy 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 [?]. In [?], the case where k is odd and strictly smaller than n -3 has been solved. In [?], the authors provide an algorithm for the case where n is odd, k is even, and 10 ≤ k ≤ n-5. Recently, the case of rigid configurations has been solved in [?]. The remaining cases are left open and the design of a unified algorithm is still required. Contribution: We provide two distinct and complementary algorithms based on an initial common phase for solving both the perpetual searching and the gathering tasks. The perpetual searching is solved starting from any exclusive and aperiodic configuration with 4 < k ≤ n -3 robots but for the cases with n = 10 and k ∈ {5, 6}, or with k even and an axis of symmetry passing through an empty node. We prove that in this latter case the problem is unsolvable. Moreover, in [?] it has been shown that it is unsolvable also for k ≤ 3 and k ≥ n -2. Therefore, we provide a full characterization of any aperiodic initial configuration with k = 4, and (n, k) ∈ { [START_REF] Flocchini | Distributed Computing by oblivious mobile robots[END_REF][START_REF] Czyzowicz | Gathering few fat mobile robots in the plane[END_REF], [START_REF] Flocchini | Distributed Computing by oblivious mobile robots[END_REF][START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF]}. For the gathering, our algorithm solves the problem starting from any exclusive configuration with 3 ≤ k < n -4, k = 4, robots empowered by the local multiplicity detection, but for the unsolvable configurations provided in [?].

Due to space constraints, most of the proofs of the lemmata and theorems and the pseudocodes of the proposed algorithms are reported in Appendix.

Notation and preliminary

Consider a ring with n nodes {v 0 , • • • , v n-1 } and 3 ≤ k < n -2, k = 4, robots standing at distinct nodes. A configuration C is defined by the k nodes occupied by robots. For any i ≤ n, let S i = (r i 1 , • • • , r i n ) ∈ {0, 1} n be the sequence such that r i j = 0 if v i+j mod n is occupied and r i j = 1 otherwise, 1 ≤ j ≤ n. Intuitively, S i represents the positions of robots, starting at v i . For any sequence X = (x 0 , • • • , x r ), let us denote X = (x r , • • • , x 0 ) and X i = (x i mod r+1 , . . . , x r+i mod r+1 ). A representation of C is any sequence in S C = {S i , (S i )} i≤n . Abusing the notation, we say C = S for any S ∈ S C . Note that, for any S = (s

1 , • • • , s n ) ∈ S C , i≤n s i = n -k. A supermin of C is any representation of C that
is minimum in the lexicographical order. We denote the supermin of C as C min . Note that, in any supermin (s 1 , • • • , s n ), s n = 1 since k < n. We denote by x h a sequence of h ≥ 0 consecutive x, x ∈ {0, 1}. We say that a sequence X is palindrome if X = X and it is symmetric if X i is palindrome for some i. A configuration is symmetric if at least one of its representations is symmetric. Let us define the configurations C a , C b , and C c as those whose supermin is

(0 k-1 , 1, 0, 1 n-k-1 ), (0 k , 1 n-k ), or (0 k 2 , 1 j , 0 k 2 , 1 n-k-j ), with j < n-k
2 , respectively. Given a configuration C, a move M permits some robots to change their position by occupying one of their adjacent nodes. If C is symmetric, and M permits a robot r to move, then, if r is reflected by the axis of symmetry to another robot r (indistinguishable from r), also r is permitted to move in a symmetric way. That is, if r and r execute the same algorithm, they will perform the same (symmetric) move. However, since the system is asynchronous, it may happen that only one of them performs the entire Look-Compute-Move cycle. In this case the generated configuration has a potential so-called pending move. An asymmetric configuration C is adjacent to a symmetric configuration C with respect to a move M if C can be obtained from C by applying M to only one of the robots permitted to move by M.

It has been proven that the searching and gathering problems cannot be solved in some symmetric configurations. For instance, it is impossible to solve the searching in a configuration

RR n°8250

with an axis of symmetry passing through two nodes, while it is impossible to solve the gathering if the axis of symmetry passes through two edges. We say that a configuration is allowed for problem P if it is not periodic and it is not symmetric having one of the symmetries which are unsolvable for P . In particular, all rigid configurations are allowed.

Align algorithm

In this section, we devise algorithm Align that, starting from any allowed configuration, reaches one of the configurations C a , C b , and C c previously defined. Algorithm Align will be exploited in next sections to achieve the configurations suitable for the graph searching, or gathering problems.

In detail, if the initial allowed configuration is symmetric and k is even, Align achieves either configuration C b or C c , and the original type of symmetry is preserved, hence the obtained configuration is still allowed. If the configuration is asymmetric and k is even, then any of C a , C b , and C c can be achieved, if they are allowed. If k is odd, then the configuration achieved is either C a or C b , if this latter is allowed. The general strategy of the algorithm is the following.

• If the configuration is symmetric, then Align preserves the symmetry by performing two symmetric moves in a way that, if only one of such moves is performed, then the obtained configuration is guaranteed to be asymmetric and not adjacent to another symmetric configuration with respect to any other move that can be possibly performed by Align. When k is odd, the symmetry is preserved until it can be safely broken by moving in an arbitrary direction the unique robot lying on the axis of symmetry. • If the configuration is asymmetric, then always only one robot is permitted to move by Align. First, the algorithm checks whether the asymmetric configuration is adjacent to some allowed symmetric configuration with respect to some move permitted by Align.

In this case, Align forces the only possible pending move. We recall that the moves performed from a symmetric configuration are designed in a way that the configuration obtained is not adjacent to any other symmetric configuration different from the correct one. Therefore, from an asymmetric configuration adjacent to an allowed symmetric one with respect to the permitted move of Align, the robot that has to move can be univocally determined and the original symmetry preserved. Note that, such behavior is performed even if the initial configuration is asymmetric. In this case, the configuration obtained after the move is symmetric and allowed, and the algorithm proceeds like in the case that the initial configuration was symmetric. In fact, as the robots are oblivious, they cannot distinguish the two cases. • If an asymmetric configuration is not adjacent to any symmetric configuration with respect to any move of Align, then the algorithm in [?] is performed. Such algorithm, ensures that only one move is performed and the obtained configuration is always rigid, thus it is allowed. In detail, algorithm Align is based on four moves described below. Let C be any allowed configuration and let C min = (v 0 , v 1 , . . . , v n-1 ) be its supermin. Let 1 be the smallest integer such that 1 > 0, v 1 = 0 and v 1-1 = 1; let 2 be the smallest integer such that 2 > 1 , v 2 = 0 and v 2 -1 = 1; let -1 be the greatest integer such that -1 < n and v -1 = 0. The four moves permitted by Align are the following:

• reduce 0 (C): The robot at node v 0 moves to node v 1 ;

• reduce 1 (C): The robot at node v 1 moves to node v 1 -1 ;

• reduce 2 (C): The robot at node v 2 moves to node v 2 -1 ;

• reduce -1 (C): The robot at node v -1 moves to node v -1+1 . Align, works in two phases: the first phase (Procedure Align-One) copes with configura-tions without any consecutive occupied nodes (i.e. v 1 = 1) while the second phase copes with configurations having at least two consecutive occupied nodes (Procedure Align-Two-Sym, if the configuration is symmetric, and Align-Two-Asym otherwise).

Phase Align-One. If v 1 = 1 and the configuration C is symmetric, the general strategy is to reduce the supermin by performing reduce 0 . If the two symmetric robots that should move perform their Look-Compute-Move cycles synchronously, then a new symmetric configuration C is obtained where the supermin is reduced and the axis of symmetry of C is preserved. Hence, C is allowed.

If only one of the two symmetric robots that should move actually performs the move (due to the asynchronous execution of their respective Look-Compute-Move cycles), then the following lemma, from [?], ensures that the configuration C obtained is asymmetric and not adjacent to any symmetric configuration with respect to a possible move affecting at most two robots. Lemma 1 ([?]) Let C be an allowed configuration and let C be the one obtained from C after a reduce 0 performed by a single robot. Then, C is asymmetric and at least two robots have to move to obtain C from an aperiodic symmetric configuration with an axis of symmetry different from that of C.

It follows that robots can recognize whether C has been obtained by performing reduce 0 from C. This is done by performing such a move on C backwards. In the affirmative case, Align forces to perform the possible pending move.

However, it is not always possible to perform reduce 0 on a symmetric configuration C. Indeed, in case that C min = (0, 1, 0, R), for some R = R, then performing reduce 0 would imply that two robots occupy the same node (a collision occurs). In fact, note that in this case the node symmetric to v 0 is v 2 and performing reduce 0 consists in moving both robots from v 0 and v 2 to v 1 . In this case, we perform reduce -1 . In Lemma 5 (for j = 1) we show that such a move performed by only one robot from a configuration C such that C min = (0, 1, 0, R), with R = R, does not create a symmetric configuration and the configuration obtained is not adjacent to any possible move performed by Align. Therefore, we can again preserve the symmetry by forcing to perform the symmetric move. Note that also in this case, performing reduce -1 results in reducing the supermin.

If the configuration is asymmetric and it cannot be obtained by performing reduce 0 or reduce -1 from any possible allowed symmetric configuration, then we execute the algorithm in [?] (ProcedureAsym). The following lemma shows that such algorithm always leads to rigid configurations. Lemma 2 ([?]) Let 3 ≤ k < n -2 robots standing in an n-node ring and forming a rigid exclusive configuration, Algorithm Asym eventually terminates achieving configuration C c and all intermediate configurations obtained are exclusive and rigid.

Algorithm Asym ensures that each move permits only one robot to change its position, and then no pending moves are possible. If by applying Asym, we produce an asymmetric configuration which is adjacent to a symmetric configuration with respect to some of the moves permitted by Align, then we force to perform the possible pending move.

Note that, in some symmetric configurations there exists a robot r that occupies a node lying on the axis of symmetry. In these cases, reduce 0 or reduce -1 may consists in moving r (in any arbitrary direction). The obtained configuration is asymmetric and not adjacent to any other symmetric configuration with respect to the moves of Align. However, we cannot move the robot symmetric to r as it does not exist, but in this case, we can safely perform Asym as there are no pending moves.

By the above discussion, it follows that Align-One leads to a configuration with two consecutive occupied nodes. In detail, we can obtain: (i) an asymmetric configuration with two consecutive nodes occupied which is not adjacent to any symmetric configuration with respect to RR n°8250 a move permitted by Align-One; (ii) an asymmetric configuration with two consecutive occupied nodes which is adjacent to a symmetric configuration with respect to some move permitted by Align-One; (iii) a symmetric configuration with two or three consecutive occupied nodes with the axis of symmetry passing in their middle; (iv) a symmetric configuration with two symmetric pairs of consecutive occupied nodes. Phase Align-Two-Sym. Once that a configuration with two consecutive occupied nodes is achieved, the second phase of algorithm Align starts. In such configurations, it is not possible to perform reduce 0 as it would cause a collision (which we want to avoid in this phase). Hence, one move among reduce 1 , reduce 2 or reduce -1 is performed.

In symmetric configurations, we perform reduce 1 every time it is possible. This occurs when the asynchronous execution of the two symmetric robots that should perform the move does not generate a symmetric configuration with a different axis of symmetry or a configuration which is adjacent to a different symmetric configuration with respect to any move permitted by Align.

If it is not possible to perform reduce 1 , we perform reduce 2 . It can be proven that asynchronous executions cannot generate other symmetries or configurations adjacent to symmetric ones potentially reachable.

There are cases when we cannot perform reduce 1 and reduce 2 . For instance this can happen if C min = (0 i , 1 j , 0 i , R), with R = R. In fact, in this case, C min = (C min 2i+j ) and performing reduce 1 corresponds to move the robot at v i+j which is symmetric to that at v i-1 . Similar instances where it is not possible to perform reduce 2 can occur. In such cases, we perform reduce -1 and show that this cannot create any different symmetry or configuration adjacent to symmetric ones with respect to any move permitted by Align.

To give more detail on the behavior of the algorithm in the case of symmetric configurations, we define the following three sets. Let S 1 be the set of symmetric configurations with supermin (0 i , 1, 0, R), where i ≥ 2 and R contains a sequence 0 i . Let S 2 be the set of configurations C ∈ S 1 such that C min = (0 i , 1 j , 0 i , Z) for some Z = Z and j ≥ 1. Finally, let S 3 be the set of configurations C ∈ S 1 such that C min = (0 i , 1 j , 0 x , 1 j , 0 x , 1 j , 0 i , Z) for some Z = Z, j, j > 0 and 1 ≤ x ≤ i or configurations C ∈ S 1 such that C min = (0 i , 1 j , 0 i-1 , 1, 0, R, 1), R = R, j > 0.

The sets S 2 and S 3 contain the configurations where it is not possible to perform reduce 1 or reduce 2 , respectively. In a series of lemmata provided in Appendix, we show that given a symmetric configuration C, if C 1 , C 2 , and C -1 are the configuration obtained from C by applying reduce 1 , reduce 2 , and reduce -1 , respectively, on only one robot, then

• (Lemma 6) C 1 is symmetric only if C ∈ S 1 \ S 3 , C min = (0 i , 1, 0, 0, 1, 0 i , (1, 0, 1, 0 i ) , 1, 0, 1), or C min = (0 i , 1, 0 i , 1, 0 i , 1, 0 i , (1, 0 i-1 , 1, 0 i , 1, 0 i ) , 1, 0 i-1 , 1), for some i > 1, > 0; • (Lemma 7) C 1 is adjacent to a symmetric configuration C different from C with respect to reduce 1 only if C ∈ S 1 \ S 3 , C ∈ S 1 \ S 3 or (C 1 ) min = (0 i , 1, 0, 1, 0 w , 1, 1)
, for some i > 1, w < x; • (Lemmata 8 and 10) if C ∈ S 1 \ S 3 or C min = (0 i , 1, 0, 1, 0 x , 1, 0, 1), where i > 1 and x < i, then C 2 is asymmetric and not adjacent to any symmetric configuration different from C with respect to moves reduce 1 and reduce 2 ;

• (Lemma 9) if C ∈ S 2 , or C min = (0 i , 1, 0, 0, 1, 0 i , (1, 0, 1, 0 i ) , 1, 0, 1), or C min = (0 i , 1, 0 i , 1, 0 i , 1, 0 i , (1, 0 i-1 , 1, 0 i , 1,
for some i > 1, > 0, then C -1 is asymmetric and it is not adjacent to any symmetric configuration different from C with respect to moves reduce 1 , reduce 2 , and reduce -1 ; Therefore, Align-Two-Sym works as follows. If C is in S 2 , then reduce 1 cannot be performed. However, we can safely perform reduce -1 (Lemma 9). If C ∈ S 2 , then Align-Two-Sym first computes the configuration C that would be obtained from C by applying reduce 1 on only one robot. If C is symmetric, then we know that

C ∈ S 1 \ S 3 , C min = (0 i , 1, 0, 0, 1, 0 i , (1, 0, 1, 0 i ) , 1, 0, 1), or C min = (0 i , 1, 0 i , 1, 0 i , 1, 0 i , (1, 0 i-1 , 1, 0 i , 1, 0 i ) , 1, 0 i-1 , 1),
for some > 0 (Lemma 6). In the former case, we can safely perform reduce 2 as the ob-tained configuration is neither symmetric nor adjacent to any other symmetric configuration (Lemma 8). In the latter two cases, we cannot perform reduce 2 but, similarly, we can safely perform reduce -1 (Lemma 9).

If C is asymmetric, then Align-Two-Sym checks whether it can be obtained by applying reduce 1 from a symmetric configuration C different from C. To this aim, it computes all the configurations that can possibly generate C . As reduce 1 reduces the supermin, then by performing it, the starting node of the supermin in the obtained configuration is either the same of the previous one or it is one of the endpoints of a sequence of consecutive occupied nodes which is generated by the move itself. It follows that C can be computed by increasing the supermin of C by moving one of the robots in the endpoints of the sequence of consecutive occupied nodes at the beginning of the supermin sequence or the possible robot in position v 1 . In other words, if C = (0 i , 1 j , 0, R, 1) for i ≥ 2 and j ≥ 1, then C can be only among the following configurations:

C α := (0 i-1 , 1, 0, 1 j-1 , R, 1), C β := (0 i-1 , 1 j , R, 0, 1), and, if R = (1, R ), C γ := (0 i , 1 j+1 , 0, R , 1).
If at least two among C α , C β , and C γ are symmetric and the move from both of them to C corresponds to reduce 1 (i.e. two symmetric configurations are adjacent to C with respect to reduce 1 ), then at least one of them must belong to S 1 \ S 3 (Lemma 7). Therefore, we can safely perform reduce 2 on such configuration and reduce 1 on the other one (see the first example in Appendix A.3).

In Appendix, we provide special arguments for the symmetric configurations C s1 = (0 i1 , 1, 0, 1, 0 x , 1, 0, 1) and C s2 = (0 i2 , 1, 1, 0 y , 1, 1) with x < i 1 and y < i 2 .

In any other symmetric configuration, Align-Two-Sym performs reduce 1 . Phase Align-Two-Asym. Procedure Align-Two-Asym works similarly to Align-One when the configuration is asymmetric. First, it checks whether the given configuration C has been obtained from a symmetric and allowed configuration C by performing only one of the two symmetric moves. In the affirmative case, it performs the possible pending move, otherwise it performs algorithm Asym. Given the moves performed by procedures Align-One and Align-Two-Sym, a configuration C with C min = (0 i , 1 j , 0 x , 1 j , R, 1), j ≥ 1, x ≥ 1, and j ≥ 0 can be adjacent to a symmetric configuration C with respect to one of such moves only if this latter is one of the following configurations:

C α := (0 i-1 , 1, 0, 1 j-1 , 0 x , 1 j , R, 1), C β := (0 i-1 , 1 j , R, 0, 1), if j > 0, C γ := (0 i , 1 j , 0 x-1 , 1, 0, 1 j -1 , R, 1), or, if R = (0, 1, R ), C δ := (0 i , 1 j , 0 x , 1 j +1 , 0, R , 1).
We remark that at most one of the above configurations can be symmetric. Let C i be such symmetric configuration, if by applying Align-Two-Sym (or Align-One if C i has no consecutive occupied nodes) on a single robot of C i we obtain C, then C has been possibly obtained from C i and then Align-Two-Asym performs the possible pending move (see the second example in Appendix A.3). If none of C i , i = α, β, γ, δ, is symmetric, then C has not been obtained from any symmetric configurations and then Align-Two-Asym performs Asym. As in the case of Align-One, if the robot that moved from C i to C is the one on the axis of symmetry of C i , then algorithm Asym is performed. The next theorem shows the correctness of Align. The proof relies on Lemmata 5-10, proven in Appendix.

Theorem 1 Let 3 ≤ k < n -2, k = 4,
robots standing in an n-node ring forming an exclusive allowed configuration, Algorithm Align eventually terminates achieving one exclusive allowed configuration among C a , C b , or C c . Proof. Let us model all the possible executions of Align as a directed graph where each configuration is represented as a node and there exists an arc (u, v) if there exist a move and a time schedule of the algorithm that starting from the configuration represented by u lead to that represented by v, even with possible pending moves. An execution of Align is represented by a path in this graph. In what follows, we show that such paths are acyclic, are made of nodes representing allowed configurations, and they always lead to a node representing one of the configurations C a , C b , or C c . We can partition the nodes into three sets: those representing symmetric configurations, those representing asymmetric configurations which are adjacent to some symmetric configurations with respect to one of the moves permitted by Align, and those representing the remaining asymmetric configurations. We denote such sets as S, AS1 and AS2, respectively. Lemmata 1, 2 and 5-10 imply the following properties.

• A node in S representing a configuration C has either one or two outgoing arcs. If it has exactly two outgoing arcs, then one of them is directed to the node v representing the configuration C obtained if both the symmetric robots permitted to move by Align perform their moves synchronously. The other arc is directed to the node v representing the configuration C obtained if only one of the two symmetric robots permitted to move by Align performs its move. In other words, the former arc models the case where both the two symmetric robots permitted to move perform the entire cycle Look-Compute-Move, while the latter arc models the case where only one of them performs entirely such cycle. Note that, v belongs to S, while v belongs to AS1. Moreover, if C is allowed, then also C is. If the node has exactly one outgoing arc then the robot r moved by Align lies on the axis of symmetry. In this case, any move performed by Align moves r in an arbitrary direction. Then, the arc is directed to a node in AS1. • A node in AS1 representing a configuration C has exactly one incoming arc from a node in S, it can have some incoming arcs from nodes in AS2, and it has exactly one outgoing arc, directed to a node in S or in AS2. If the outgoing arc is directed to a node in S, then one of the incoming arcs comes from a node u in S and models the case when only one of the two symmetric robots permitted to move by Align from the configuration C represented by u performs its move. From Lemmata 5-10, there exists only one of such nodes. The outgoing arc leads to the node in S representing configuration C which can be obtained by moving synchronously both the symmetric robots permitted to move by Align from C. Note that both C and C are allowed configurations. If the outgoing arc is directed to a node in AS2, then C has been obtained by a configuration C corresponding to a node in S such that the robot r moved by Align lies on the axis of symmetry. In this case, Align performs Asym from C and the obtained configuration is in AS2. • A node in AS2 has exactly one outgoing arc, directed either to another node in AS2 or to a node in AS1 but it cannot be directed to a node in S (by Lemma 2). It can have some arcs coming from nodes in AS1 or AS2. It follows that any execution path performed by the algorithm is made of nodes representing allowed configurations. Moreover, each allowed configuration has an outgoing arc that is traversed by the execution path of the algorithm. Note also that any move performed by the algorithm reduces the supermin of a configuration. This implies that the graph is acyclic, as we can define a topological ordering of the nodes on the basis of the ordering given by the supermin of the corresponding configurations. The statement is then proven by observing that configurations in C a , C b , or C c are those with the minimum possible supermin and hence are the only possible sinks of the graph.

Searching in a Ring

In this section, we present an algorithm that allows a team of robots to perpetually search a ring. In [?], it is shown that, for any starting configuration, it is not possible to search an n-node ring using k robots if n ≤ 9, k ≤ 3, or k ≥ n -2. However, there is an algorithm allowing 5 ≤ k ≤ n -3 robots to search a ring with n ≥ 10 nodes (but for k = 5 and n = 10), for rigid initial configurations.

If k is even and the axis does not pass through an empty node, the searching is clearly unsolvable because a synchronous execution of any algorithm either cause a collision in the node lying on the axis or does not allow to search the edges incident to such node. It follows that in the searching problem, the symmetric allowed configurations are all those with k odd and those with k even where the axis does not pass through an empty node, provided that 3 < k < n -2 and n > 9. Moreover, allowed configurations must be exclusive.

Here, we improve over the algorithm in [?] by addressing also aperiodic symmetric configurations. We will use two sub-procedures (defined in the Appendix): Algorithm Compact-Align is used after Align to achieve configuration C b , in the case Align reaches configuration C c , and Algorithm Break-Symmetry is used to achieve C a in the case that k is odd. Algorithm Search-Ring. The algorithm first checks whether k = n -3 or if n is odd and k is even. In the affirmative case, any allowed configuration must be asymmetric, and therefore the algorithm of [?] can be applied and the ring is searched. If k is odd, we first use Algorithm Break-Symmetry to break the potential symmetry and then use the algorithm of [?]. Each of these configurations used during the searching phase of the algorithm of [?] are asymmetric and are not adjacent to any symmetric configuration reached by Algorithm Break-Symmetry. Therefore, there is no ambiguity (no pending move) when a robot recognizes such a configuration.

If n and k are even, we may be in allowed symmetric configurations and therefore the Search-Ring proceeds in two phases. Algorithm Compact-Align is first applied until one of the configurations in A (described in Appendix) is achieved. This is guaranteed by the fact that both C a and C b belong to A. Then, the algorithm proceeds to Phase 2 which actually performs the searching.

The intuitive explication of the Searching algorithm (Phase 2) is as follows. All robots are aligned on consecutive nodes. Then, both robots r and r at the ends of this segment move (one clockwise and the other anti-clockwise) to reach the two adjacent nodes opposite to the occupied segment. Then, the two robots q and q occupying the ends of the "long" occupied segment move to their empty neighbors. These moves indicate to r and r that it is time to go back toward the "long" segment, and that is what happens. Finally, when r is adjacent to q and r is adjacent to q , then q and q move to their empty neighbors in order to re-build the original segment. Then, the process is repeated perpetually.

Such a sequence of moves actually searches the ring. Moreover, by definition of the configurations met during the process (configurations in A), there is no ambiguity in the choice of the robot(s) that must move. Finally, there are no conflicts between the different phases of our procedure because any configuration in A is not adjacent to any symmetric configuration not in A. This allows to state the following theorem: Theorem 2 Let 4 < k ≤ n -3 robots, standing in an n-node ring forming an allowed configuration, Algorithm Search-Ring perpetually searches the ring, but for (n, k) ∈ {(10, 5); [START_REF] Flocchini | Distributed Computing by oblivious mobile robots[END_REF][START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF]} when the configuration is symmetric.

Gathering in a ring

The gathering asks for a deterministic strategy that let robots meet at a common node and remain in there. This means that more than one robot must be allowed to occupy a single node, i.e. a collision occurs. Actually, collisions are referred as multiplicities (or towers) in the gathering literature. We assume that the robots have the local multiplicity detection capability. That is, a robot perceives whether a node x is occupied by more than one robot only if it resides on x as well. In [?], it has been proven that the multiplicity detection capability is necessary to allow robots to accomplish the gathering task. Moreover, the problem requires that an initial configuration is not periodic, does not admit an axis of symmetry passing through two edges, and contains more than two robots [?]. Starting from Align, in Appendix is described a strategy to reach the following result:

Theorem 3 Let 3 ≤ k < n -4, k = 4,
robots, empowered with the local multiplicity detection, standing in an n-node ring forming an allowed configuration, Algorithm Gathering eventually terminates with only one node occupied.

The idea is to first make use of Procedure Align to reach one of the following configuration types:

C a = (0 k-1 , 1, 0, 1 n-k-1 ), C b = (0 k , 1 n-k ), with k or n odd, C c = (0 k 2 , 1 j , 0 k 2 , 1 n-k-j ), with j or n odd. Then, configurations in C a are moved either to C b (if k is odd) or to C c (if k is even and n is odd). Configurations in C b move from (0 k , 1 n-k ) to (0 k-2 , 1 n-k+2 ) (if k is odd) and configurations in C c move to (0 k-3 , 1 n-k+3
) with a multiplicity in the middle. By continuing with this process, the gathering is accomplished, eventually.

Conclusion

We have proposed two algorithms to solve the perpetual searching and the gathering tasks under minimal assumptions. The results provided here constitute a complete characterization of the two problems but for few marginal cases. For the perpetual searching, our algorithm handles the missing cases of our previous work on the same subject. For the gathering, this paper closes a long standing open problem. In fact, the results in the literature left some open cases which are now closed. Moreover, we have also addressed the lack of a unified algorithm that works for any gatherable configuration.

Algorithm: Align-Two-Sym Input: Allowed configuration C with C min = (v 0 , v 1 , . . . , v n-1 )

1 if C ∈ S 2 or C min = (0 i , 1, 0, 0, 1, 0 i , (1, 0, 1, 0 i ) , 1, 0, 1), or C min = (0 i , 1, 0 i , 1, 0 i , 1, 0 i , (1, 0 i-1 , 1, 0 i , 1, 0 i ) , 1, 0 i-1 , 1) then 2 reduce -1 (C); 3 else 4
Let C be the configuration obtained by applying reduce 1 (C) on C;

5 if C is symmetric then 6 reduce 2 (C); 7 else 8 Let C = (0 i , 1 j , 0, R, 1); 9 C α := (0 i-1 , 1, 0, 1 j-1 , R, 1); 10 C β := (0 i-1 , 1 j , R, 0, 1); 11 if R = (1, R ) then C γ := (0 i , 1 j+1 , 0, R , 1); 12 if At least two among C α , C β ,
and C γ are symmetric, the move from both of them corresponds to reduce 1 , and (C ∈ S 1 \ S 3 or C = (0 i , 1, 0, 1, 0 x , 1, 0, 1)) then

Algorithm: Align-Two-Asym Input: Allowed configuration C with C min = (v 0 , v 1 , . . . , v n-1 )
1 Let C = (0 i , 1 j , 0 x , 1 j , R, 1) with j ≥ 1, x ≥ 1, and j ≥ 0; 2 C α := (0 i-1 , 1, 0, 1 j-1 , 0 x , 1 j , R, 1); 3 C β := (0 i-1 , 1 j , R, 0, 1); 4 if j > 0 then C γ := (0 i , 1 j , 0 x-1 , 1, 0, 1 j -1 , R, 1); 5 if R = (0, 1, R ) then C δ := (0 i , 1 j , 0 x , 1 j +1 , 0, R , 1); 6 for i ∈ {α, β, γ, δ} do

A.2 Further details

Here, we give some special arguments for the symmetric configurations C s1 = (0 i1 , 1, 0, 1, 0 x , 1, 0, 1) and C s2 = (0 i2 , 1, 1, 0 y , 1, 1) with x < i 1 and y < i 2 .

Note that in these cases reduce 1 and reduce -1 coincide. Moreover, in C s2 the only move that reduces the supermin and does not create a collision is reduce 1 . However, performing reduce 1 from C s1 and C s2 leads to the same configuration C = (0 i , 1, 0, 1, 0 w , 1, 1) if i = i 2 = i 1 + 1 and w = x = y -1. For these reasons Align-Two-Sym performs reduce 1 from C s2 and reduce 2 from C s1 . This latter move cannot create a symmetric configuration nor a configuration adjacent to any symmetric configuration different from C s1 with respect to any move permitted by Align (Lemma 10).

A.3 Examples of execution

The example in Figure 5 shows a case where applying reduce 1 on a symmetric configuration results in a symmetric configuration with a different axis of symmetry. Let us consider the configuration C in Figure 5a such that C min = (0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1). As v 1 = 0 and C is symmetric, then Procedure Align-Two-Sym is performed. It first compute configuration C in Figure 5b which is the one that would be obtained from C by applying reduce 1 on only one robot. As such a configuration is symmetric, reduce 2 is applied. If only one robot moves, then the configuration C in Figure 5c is obtained. Such configuration is asymmetric and it has a possible pending move. From configuration C , Procedure Align-Two-Asym is applied. Such a procedure computes the unique symmetric configuration which C is adjacent to. To this aim, it computes the four possible configurations that can generate C by applying Align. Such configurations are:

• C α given in Figure 5d; • C β which is equivalent to C;

• C γ given in Figure 5e; • C δ given in Figure 5f. Among such configurations, only one is symmetric which is C β = C. Therefore, Align-Two-Asym is able to identify the robot that has to move in order to perform the possible pending move. In this specific case, The robot that moved from C to C , is the one on the axis of symmetry. It follows that there are no pending moves and Align-Two-Asym proceeds by applying Asym.

The example in Figure 6 shows a case where applying reduce 1 on a symmetric configuration results in an asymmetric configuration which is adjacent to another symmetric configuration, different from the original one, with respect to reduce 1 . Let us consider the configuration of Figure 6a. As v 1 = 0 and C is symmetric, then Procedure Align-Two-Sym is performed. It first compute configuration C in Figure 6b which is the one that would be obtained from C by applying reduce 1 on only one robot. As such configuration is asymmetric, the procedure checks whether it can be obtained by applying reduce 1 from a symmetric configuration different from C. To this aim it computes:

• C α which is equivalent to C;

• C β given in Figure 6d;

• C γ given in Figure 6e. Both configurations C α and C γ are symmetric, and configuration C can be obtained from both of them by Therefore, Procedure Align-Two-Sym exploits Lemma 8 and applies reduce 2 on C. The obtained configuration C is given in Figure 6c. It is easy to see that such configuration is asymmetric and it is not adjacent to any symmetric configuration different from C with respect to any move permitted by Align.

A.4 Correctness

In the following, we distinguish between the following two types of symmetry.

Definition 1 Let C be a configuration such that C min = (0 i , 1, R, 1), then C is said symmetric if exactly one of the following two conditions is satisfied:

Symmetry 1. R = R, or Symmetry 2. (1, R, 1) = (Y, 0 i , Z) with Y = Y and Z = Z
In other words, if C has Symmetry 1, then the sequence of consecutive occupied nodes which starts with the supermin, is cut in the middle by the axis of symmetry. In this case, there are two symmetrical supermins at the two sides of such sequence. If C has Symmetry 2 then the axis of symmetry passes through the middle of sequences Y and Z and there are two symmetrical supermin corresponding to the two sequences of i consecutive occupied nodes.

Lemma 3 If (0, R) = (R, 0) and (0, R) = (R, 0), then R ∈ (0 k ), k ∈ N.
Proof. R may be ∅.

Clearly, R = (0) if |R| = 1. Assume |R| > 1.
By induction on 0 ≤ j ≤ n 2 , we show that R = (0 j , X, 0 j ).Assume that R = (0 j , a, X, b, 0 j ), then, by symmetries, (0, 0 j , a, X, b, 0 j ) = (0 j , b, X, a, 0 j , 0) and (0, 0 j , b, X, a, 0 j ) = (0 j , a, X, b, 0 j , 0), hence a = b = 0 and thus, R = (0 j+1 , X, 0 j+1 ). Then, X = ∅, or |X| = 1, in which case the only possibility is X = (0), or X = (0 j+1 , a , X , b , 0 j+1 ) and the result holds by induction.

Lemma 4 Let Y be any sequence and let X satisfy (Y, X) = (X, Y ) and X = X. Then, the set of solutions for consists of the sequences X that satisfy: X = (Y i , U ), with Y = (U, V ) and U = U and V = V , and i ≥ 0.

Proof. Clearly, any sequence X satisfying the properties of the lemma is a valid solution. We prove that any solution has the desired form by induction on the length of the solution.

Assume first that there is a solution X with |X| ≤ |Y |. Then, X is a prefix of Y because (Y, X) = (X, Y ). Therefore, Y = (X, V ). Plugging it into the equation, we get (X, V, X) = (X, V , X). Therefore, V = V . Hence, X and Y have the desired form. Now, consider a solution X such that |X| > |Y |. Then, Y is a prefix of X because (Y, X) = (X, Y ). Therefore, X = (Y, X ). Plugging it into the equation, we get (Y, Y, X ) = (Y, X , Y ). Moreover, because X = X, we get that (Y, X , Y ) = (Y, X , Y ). All together, we get that X = (Y, X ) with (Y, X ) = (X , Y ) and X = X .

Therefore, by induction, we get that, there is i ≥ 0 such that X = (Y i , U ) with Y = (U, V ) and U = U and V = V . Hence, X = (Y i+1 , U ) and the lemma holds.

Lemma 5 Let C be a symmetric and allowed configuration with supermin C min = (0, 1 j , 0, R), for R = R and j ≥ 1, and let C the configuration obtained by applying reduce -1 on only one robot on C. Then C is asymmetric and it is not adjacent with respect to reduce 0 and reduce -1 to any symmetric configuration different from C.

Proof. Since R is palindrome, then C min = (0, 1 j , 0, R) is the only supermin as otherwise C is periodic. Therefore, R = (1 j , 0, R , 0, 1 j ), for some j > j and R = R . The configuration obtained by applying reduce -1 on only one robot on C is C = (0, 1 j , 0, 1 j , 0, R , 1, 0, 1 j -1 ). We distinguish the following two cases.

• j -1 > j. In this case, C min = (0, 1 j , 0, 1 j -1 , 0, 1, R , 0, 1 j ). The configuration is asymmetric as if there exist another sequence starting with (0, 1 j , 0) then we obtain a contradiction with the superminimality of C min . Configuration C can be obtained by applying reduce 0 or reduce -1 on a configuration C different from C only if (i) C = (0, 1 j+1 , 0, 1 j -1 , 0, 1, R , 0, 1 j -1 ), or (ii) C = C, or (iii) C = (0, 1 j+1 , 0, 1 j -2 , 0, 1, R , 0, 1 j ). In fact, in case (i) C is obtained by performing reduce 0 on C and C min = (0, 1 j+1 , 0, 1 j -1 , 0, 1, R , 0, 1 j -1 ), or by performing reduce -1 on C and C min = (0, 1 j -1 , 0, 1 j+1 , 0, 1 j -1 , 0, R , 1); in case (ii) C is obtained by performing reduce 0 on C and C min = C min ; and in case (iii), C is obtained by performing reduce -1 on C and C min = (0, 1 j , 0, 1 j+1 , 0, 1 j -2 , 0, 1, R ). In the first case of (i), as the supermin is (0, 1 j+1 , 0, 1 j -1 , 0, 1, R , 0, 1 j -1 ) we have that (0, 1 j+1 , 0, 1 j -1 , 0, 1, R , 0, 1 j - (0, 1 j+1 , 0, 1 j -1 , 0, R , 1, 0, 1 j -1 ) which implies that (1, R ) < (R , 1). This last inequality can be satisfied only if R = (1 j ) for some j > j, which implies that k = 4, a contradiction. In the second case of (i), we must have that the axis passes through the middle of the first sequence of j -1 consecutive empty nodes and that (1 j+1 , 0, 1 j -1 , 0, R , 1) is palindrome, that is (1 j , 0, 1 j -1 , 0, R ) = (R , 0, 1 j -1 , 0, 1 j ). By Lemma 4, it follows that R = ((1 j , 0, 1 j -1 , 0) , 1 j ) for some ≥ 0. However, in this case we have that C min = (0, 1 j , 0, 1 j , 0, (1 j , 0, 1 j -1 , 0) , 1 j , 0, 1 j ) which is a contradiction as for > 0, C min j+j +2 < C min and for = 0 C is periodic. The case (ii) corresponds to the move that has been actually performed. In case (iii), we have that hat the axis passes through the middle of the first sequence of j consecutive empty nodes and that the sequence (1 j+1 , 0, 1 j -2 , 0, 1, R ) is palindrome. By Lemma 4, this can occur only if j = 0 as otherwise the sequence (1 j+1 , 0, 1 j -2 , 0, 1, ) cannot be split into two palindrome sub-sequences. We obtained a contradiction as j ≥ 1.

• j -1 = j. In this case C = (0, 1 j , 0, 1 j+1 , 0, R , 1, 0, 1 j ) and either C min = (0, 1 j , 0, 1 j , 0, 1 j+1 , 0, R , 1)

or C min = (0, 1 j , 0, 1 j , 0, 1, R , 0, 1 j+1 ). In any case R cannot contain a sequence (0, 1 j , 0, 1 j ).

Therefore, if C min = (0, 1 j , 0, 1 j , 0, 1 j+1 , 0, R , 1), the axis of symmetry can only pass through the first sequence of j consecutive empty nodes or in the robot separating the two sequences of j consecutive empty nodes. In the first case, R must start with a (1 j-1 , 0) but this is a contradiction to the superminimality of C. In the second case, we must have that (1 j+1 , 0, R , 1) = (1, R , 0, 1 j+1 ) that is (1 j , 0, R ) = (R , 0, 1 j ). By Lemma 4, this implies that R = ((1 j , 0) , 1 j ) for some ≥ 0. It follows that C min = (0, 1 j , 0, 1 j+1 , 0, (1 j , 0) , 1 j , 0, 1 j+1 ). However, this implies that: if = 0, then C is periodic, and if > 0, then C min 2j+2 < C min . In any case, we obtain a contradiction. If C min = (0, 1 j , 0, 1 j , 0, 1, R , 0, 1 j+1 ), the axis of symmetry can only pass through the robot separating the two sequences of j consecutive empty nodes. Note that, in this case, C min = (0, 1 j , 0, 1 j , 0, 1, R , 0, 1 j+1 ) = (0, 1 j , 0, 1 j , 0, 1 j+1 , 0, R , 1) and hence the same arguments as before can be applied.

Configuration C can be obtained by applying reduce 0 or reduce -1 on a configuration C different from C only if (i) C = (0, 1 j+1 , 0, 1 j , 0, 1, R , 0, 1 j ). In fact, C can be obtained by applying reduce 0 or reduce -1 to C if C min = (0, 1 j+1 , 0, 1 j , 0, 1, R , 0, 1 j ) or C min = (0, 1 j , 0, 1 j+1 , 0, 1 j , 0, R , 1), respectively. The first case is impossible as C min is not minimum. In the second case, we must have that (1 j+1 , 0, 1 j , 0, R , 1) = (1, R , 0, 1 j , 0, 1 j+1 ) and hence (1 j , 0, 1 j , 0, R ) = (R , 0, 1 j , 0, 1 j ). By Lemma 4, this implies that R = ((1 j , 0, 1 j , 0, ) , 1 j ) or R = ((1 j , 0, 1 j , 0, ) , 1 j , 0, 1 j ). In any case, we obtain that either C is periodic or that C min is not minimum.

Lemma 6 Let C be a symmetric and allowed configuration with supermin C min = (0 i , 1, R), i > 1, and let C the configuration obtained by applying reduce 1 on only one robot on C.

If C is symmetric, then C ∈ S 1 \S 3 , C min = (0 i , 1, 0, 0, 1, 0 i , (1, 0, 1, 0 i ) , 1, 0, 1), or C min = (0 i , 1, 0 i , 1, 0 i , 1, 0 i , (1, 0 i-1 , 1, 0 i , 1, 0 i ) , 1, 0 i-1 , 1).
Proof. We first show that C ∈ S 1 and then that the only configuration in S 3 such that C is symmetric is such that C min = (0 i-1 , 1, 0, 0, 1, 0 i-1 , (1, 0, 1, 0 i-1 ) , 1, 0, 1).

Let C min = (0 i , 1 j , 0, R ) for j ≥ 1, then S = (0 i , 1 j-1 , 0, 1, R ) is a representation of C . We show that if j > 1, then C min = (0 i , 1 j-1 , 0, 1, R )
is the unique supermin of C , i.e. the configuration is asymmetric.

Note that S < C min and that S h > C min h ≥ C min for each h = 1 -1. Moreover, S j-1 > S. Therefore, S h cannot be a supermin of C for each h. By contradiction, let j be an integer such that S j < S. Then C min j < C min , a contradiction. It follows that if C is symmetric, then C min = (0 i , 1, 0, R ) and the supermin of C is (0 i+1 , 1, R ), (0 i+1 , R , 1) or both. In this case, C can only have symmetry 1 as there is only one sequence of i + 1 consecutive occupied nodes. This implies that (0 i+1 , 1, R ) = (0 i+1 , R , 1). Let us assume that C has symmetry 1, then the sequence (1, 0, R ) is palindrome and then R = (R , 0, 1) with R = R . Since, by the symmetry of C , (1, R ) = (R , 1), then (1, R , 0, 1) = (1, 0, R , 1) and therefore (R , 0) = (0, R ). By Lemma 3, R = (0 j ) for some j and then W C min = (0 i , 1, 0 j +2 , 1) which is a contradiction as it implies that k = n -2. Therefore, C has symmetry 2 and then C ∈ S 1 .

Since C is asymmetric if C min = (0 i , 1 j , 0, R ) for any R , it remains to show that it is asymmetric if C min = (0 i , 1, 0 i-1 , 1, 0, R, 1), for some R = R. Let us assume that C min = (0 i , 1, 0 i-1 , 1, 0, R, 1) with R = R, then C min = (0 i+1 , 1, 0 i-2 , 1, 0, R, 1). Therefore, C can only have symmetry 1 and hence the sequence (1, 0 i-2 , 1, 0, R, 1) must be palindrome. By Lemma 4, C is symmetric if and only if R = ((0 i-2 , 1, 0) , 0 i-3 ), with i ≥ 3, that is C min = (0 i , 1, 0 i-1 , 1, 0, (0 i-2 , 1, 0) , 0 i-3 , 1) and then C is asymmetric.

To show the second part of the proof, let us assume that C min = (0 i , 1 j , 0 x , 1 j , 0 x , 1 j , 0 i , Z) with j > 0 and Z = Z. We can assume that j = 1 as otherwise C is asymmetric. After applying reduce 1 , we have

C min = (0 i+1 , 1, 0 x-1 , 1 j , 0 x , 1, 0 i , Z) with (1, 0 x-1 , 1 j , 0 x , 1, 0 i , Z) palindrome, that is (1, 0 x-1 , 1 j , 0 x , 1, 0 i , Z) = (Z, 0 i , 1, 0 x , 1 j , 0 x-1 , 1)
. By Lemma 4 it follows that Z = ((1 j+1 , 0, 1, 0 i ) , 1 j+1 ) for some ≥ 0, x = 1, and i = 1; or Z = ((1, 0, 1, 0 i ) , 1, 0, 1) for some ≥ 0, x = 1, and j = 0; or Z = ((1, 0 i-1 , 1, 0 i , 1, 0 i ) , 1, 0 i-1 , 1) for some ≥ 0, x = i, and j = 1. In the first case we obtain a contradiction with the hypothesis that i > 1; in the second case, C min = (0 i , 1, 0, 0, 1, 0 i , (1, 0, 1, 0 i ) , 1, 0, 1); in the third case

C min = (0 i , 1, 0 i , 1, 0 i , 1, 0 i , (1, 0 i-1 , 1, 0 i , 1, 0 i ) , 1, 0 i-1 , 1).
Lemma 7 Let C be a symmetric and allowed configuration and let C be the configuration obtained by applying reduce 1 on only one robot on C. If C is adjacent with respect to reduce 0 to a symmetric configuration

C different from C , then C ∈ S 1 \ S 3 , C ∈ S 1 \ S 3 or C min = (0 i , 1, 0, 1, 0 x , 0, 1). Proof. Let C min = (0 i , 1, R, 1) with i > 1.
Then, C and C are one of the following configurations:

• If R does not start by 0 i-2 or i = 2, C1 min = (0 i-1 , 1, 0, R, 1) ; • If R does not start by 0 i-2 or i = 2, C2 min = (0 i-1 , 1, 0, R, 1); • If R = (1 j-1 , 0, 1, R ) and R does not start by 0 i-1 , C3 min = (0 i , 1 j+1 , 0, R , 1).
The proof proceed by showing that if two among C1, C2, and C3 are symmetric than one of them belongs to S 1 \ S 3 or C min = (0 i , 1, 0, 1, 0 x , 0, 1). The following facts analyze any possible pair of symmetries. In what follows, we assume that C1, C2, and C3 are distinct. Proof. By symmetry of C1, (0, R) = (R, 0) and, by symmetry of C2, (0, R) = (R, 0). By Lemma 3,

R = {∅; (0 n-i-2 )} that is k = n -2, a contradiction.
Fact 2 C1 and C3 cannot have both symmetry 1.

Proof. By symmetry of C1, (0, R) = (R, 0) so the last element of R (and of R ) is 0, so by symmetry of C3, j = 0, a contradiction because j > 0.

Fact 3 If C2 and C3 have symmetry 1, then j = 1 and R = (0, 1, 0 n-i-5 , 1). Therefore, C2 = (0 i-1 , 1, 0, 1, 0 n-i-5 , 1, 0, 1), C3 = (0 i , 1, 1, 0 n-i-4 , 1, 1) and C min = (0 i , 1, 0, 1, 0 x , 0, 1).

and C min = (0 i , 1, 0, 1, 0 x , 0, 1).

Proof. Recall that R = (1 j-1 , 0, 1, R ).
By symmetry of C2, (0, R) = (R, 0) and the first element of R is 0 and thus, j = 1 and R = (0, 1, R ). By symmetry of C3, (1, 0, R ) = (R , 0, 1). Therefore, R = (1) or R = (0, 1), or R = (R , 0, 1).

In the latter case, by symmetry of C2, (0, 1, 0, R , 1, 0) = (0, 1, R , 0, 1, 0). Hence, (0, R ) = (R , 0). By symmetry of C3, (1, 0, R , 0, 1) = (1, 0, R , 0, 1), hence R = R . Hence, R is a sequence of 0 by Lemma 4. Proof. Assume that R = (0 i-2 ) as otherwise, C1 would be periodic. By symmetry of C1 (0, R) = (R, 0). This implies that R = (X, 0) with X = X. By symmetry of C2, (1, 0, 0, X, 1) = (Y, 0 i-1 , Z) with Y = Y and Z = Z.

• Case X = (0 i-3 , V ), V = ∅ and starts by 1 and Y = (1). By symmetry of X, (V , 0 i-3 ) = (0 i-3 , V ) and, by symmetry of Z = (V, 1), (V, 1) = (1, V ). Hence, V = (1, V , 0 i-3 ). Again, the symmetry of X gives that (V , 1) = (1, V ) and, by symmetry of Z, (V , 0 i-3 ) = (0 i-3 , V ). Therefore, if V = ∅, V = (0 i-3 , V , 1). The symmetry gives that (V , 1) = (1, V ) and (V , 0 i-3 ) = (0 i-3 , V ). Hence, V = (1, V , 0 i-3 ). Going on this way, we get that

R = (0 i-3 , (1, 0 i-3 ) n-3i+2 i-2 , 1, (0 i-3 , 1) n-3i+2 i-2 , 0 i-2 ).
By plugging R into the definition of C2, it follows that C2 ∈ S 2 . • Case X = (U, 0 i-2 ), and Z = (1), U = ∅ and finishes by 1. This case is excluded. Indeed, by definition of C2, R cannot start with 0 i-2 unless i = 2. If i = 2, by minimality of C1 and C2, R must start and finish with 1, contradicting (0, R) = (R, 0). • Case X = (U, 0 i-1 , V ), U = ∅ and finishes by 1, V = ∅ and starts by 1. In that case, Y = (1, 0, 0, U ) = (U , 0, 0, 1) and 1), (0, 1), (U , 0, 0, 1)}, where U = U . Moreover, by symmetry of X, (V ,

Z = (V, 1) = (1, V ), that is V = (1, V ) and U ∈ {(
0 i-1 , U ) = (U, 0 i-1 , V ) that is (V , 1, 0 i-1 , U ) = (U, 0 i-1 , 1, V ) that implies that V starts like U or is empty. -If U = (1), then C1 = (0 i-1 , 1, 0, 1, 0 i-1 , 1, V , 0, 1
). If V is not empty, then it starts with 1 and (V , 0) > (0, V ). Therefore, C1 is not supermin as C1 2i+1 is strictly smaller. If V is empty, then C1 = (0 i-1 , 1, 0, 1, 0 i-1 , 1, 0, 1) which is periodic and has more than one symmetry, a contradiction. -If U = (0, 1), then C1 = (0 i-1 , 1, 0, 0, 1, 0 i-1 , 1, V , 0, 1) and V either starts with 0 or with (0, 1). In the first case, C1 is periodic with more than one axis of symmetry, in the second case, C1 is not supermin as C1 2i+2 is strictly smaller since (V , 0) > (0, V ), a contradiction to the superminimality of C1.

-If U = (U , 0, 0, 1), then C1 = (0 i-1 , 1, 0, U , 0, 0, 1, 0 i-1 , 1, V , 0, 1). If U = (0 x ) for some x ≥ 0, then (0 i-1 , 1, 0, U ) > (, 0 i-1 , 1, 0, 0, U ) and hence, C1 2i+2+|U | is strictly smaller than C1. If U = (0 x ) for some x ≥ 0, then C1 = (0 i-1 , 1, 0 x+3 , 1, 0 i-1 , 1, V , 0, 1) and therefore, if V = (0 y ) for some 0 ≤ y ≤ x + 2, then (V , 0) > (0, V ) and hence C1 2i+x+3 is strictly smaller than C1. Finally, if U = (0 x ) for some x ≥ 0 and V = (0 x ) for some 0 ≤ y ≤ x + 2, then C1 = (0 i-1 , 1, 0 x+3 , 1, 0 i-1 , 1, 0 y+1 , 1). Moreover, by the symmetry of X, C1 = (0 i-1 , 1, 0 y+1 , 1, 0 i-1 , 1, 0 x+3 , 1). It follows that y = x + 2 and C1 is periodic with more than one axis of symmetry, a contradiction.

Fact 5 If C1 has symmetry 2 and C2 has symmetry 1, then C1 ∈ S 2 .

Proof. By symmetry with previous fact.

Fact 6

It is not possible that C1 has symmetry 1 and C3 has symmetry 2.

Proof. C1 = (0 i-1 , 1, 0, R, 1) and C3 = (0 i , 1 j+1 , 0, R , 1) and R = (1 j-1 , 0, 1, R ), i > 1 and j > 0.

By symmetry of C1, (0, R) = (R, 0) so (0, 1 j-1 , 0, 1, R ) = (R , 1, 0, 1 j-1 , 0) and the last element of R is 0.

By symmetry of C3, (1, 1 j , 0, R , 1) = (Y, 0 i , Z) with Y = Y and Z = Z. Note that R cannot contain a sequence of i consecutive 0 by superminimality of C1. Therefore, the only possibility is

R = (0 i-1 , R ) with Z = (R , 1) and Y = 1 j+1 . Then, (R , 1) = (1, R ) and thus, R = (1, R ) with R palindrome. Moreover, because (0, R) = (R, 0), we get (0, 1 j-1 , 0, 1, 0 i-1 , 1, R ) = (R , 1, 0 i-1 , 1, 0, 1 j-1 , 0)
. We now use Lemma 4 by setting X = R and Y = (0, 1 j-1 , 0, 1, 0 i-1 , 1). The possible cases are:

• U = (0) and V = (

, 0) for ≥ 0, only if i = j = 2. In which case R = (0, 1, (

, 0) and C1 = (0,

, 0, 1) which is periodic, a contradiction. • U = (0), 1 j-1 , 0 and V = (1, 0 i-1 , 1), then R = ((0, 1 j-1 , 0, 1, 0 i-1 , 1) , 0, 1 j-1 , 0) for ≥ 0. In which case R = (0 i-1 , 1, (0, 1 j-1 , 0, 1, 0 i-1 , 1)

n-2(i+j+2) i+j+2
, 0, 1 j-1 , 0) and

C1 = (0 i-1 , 1, 0, 1 j-1 , 0, 1, 0 i-1 , 1, (0, 1 j-1 , 0, 1, 0 i-1 , 1) n-2(i+j+2) i+j+2
, 0, 1 j-1 , 0, 1)

which is periodic, a contradiction. • U = (0, 1, 0, 1, 0) and V = (1), then R = ((0, 1, 0, 1, 0, 1) , 0, 1, 0, 1, 0) for ≥ 0, only if i = j = 2. In which case R = (0, 1, (

, 0, 1, 0, 1, 0) and C1 = (0, 1, 0,

, 0, 1, 0, 1, 0, 1) which is periodic, a contradiction. Proof. C1 = (0 i-1 , 1, 0, R, 1) and C3 = (0 i , 1 j+1 , 0, R , 1) and R = (1 j-1 , 0, 1, R ), i > 1 and j > 0. Moreover, by superminimality of C1, R cannot contain a sequence of i consecutive 0.

By Symmetry of C3, R = (R , 1 j ) and (0, R ) = (R , 0).

By Symmetry of C1, (1, 0, R, 1) = (Y, 0 i , Z) with Y = Y and Z = Z. That is, (1, 0, 1 j-1 , 0, 1, R , 1 j+1 ) = (Y, 0 i-1 , Z).
• Case R = (0 i-1 , U ) and Y = (1, 0, 1 j-1 , 0, 1) and Z = (U, 1 j+1 ). Because (0, R ) = (R , 0), U finishes with 0 and, thus, because Z palindrome, U = (1 j+1 , U ) with U palindrome. Hence, because (0, R ) = (R , 0), we have (0 i , 1 j+1 , U ) = (U , 1 j+1 , 0 i ). By Lemma 4, there is ≥ 0 such that U = ((0 i , 1 j+1 ) , 0 i ). However, it means that R contains i consecutive 0, a contradiction. • Case R = (U, 0 i-1 ) and Z = 1 j+1 and Y = (1, 0, 1 j-1 , 0, 1, U ).

-Case U = ∅. Then, R = (0 i-1 , 1 j ) and C3 = (0 i , 1 j+1 , 0 i , 1 j+1 ) which is periodic with more than one axis of symmetry.

(X, Y , 1, X) which implies that (1, Y ) = (Y , 1) and that we can define Y such that Y = (Y , 1) and Y = Y . Then Y = (Y , 1, X) and plugging it into (Y, X) = (X, Y ) we obtain (Y , 1, X, X) = (X, X, 1, Y ). By Lemma 4, it follows that Y = ((X, X, 1) , X ) where X = (X , X ), X = X , X = X . If = 0, then Y = (X , 1, X) and from (Y, X) = (X, Y ) follows that (X , 1, X, X) = (X, X, 1, X ) and then (X , 1, X , X , X , X ) = (X , X , X , X , 1, X ) which implies that X = (1 m ) for some m > 0. In fact, if we assume that X contains a 0, that is X = (1 m , 0, X , 0, 1 m ) for m ≥ 0, then we have (X , 1, 1 m , 0, X , 0, 1 m , X , 1 m , 0, X , 0, 1 m , X ) = (X , 1 m , 0, X , 0, 1 m , X , 1 m , which is not palindrome. Similar arguments can be used to show that X does not contains 0. If > 0 similar arguments can be used to show that Y is palindrome if and only if X = (1 m ) for some m > 0.

If |X| > |Y |, then as (X, 1, Y ) = (Y , 1, X), we define X such that X = (Y , X ). By plugging Y into (Y, X) = (X, Y ), we obtain (Y, X , Y ) = (Y , X , Y ) which implies that Y = Y and X = X. From (X, 1, Y ) = (Y , 1, X) it follows that (Y, X , 1, Y ) = (Y, 1, X , Y )
and then (X , 1) = (1, X ). Therefore, X = (1 m ) for some > 0 and X = (Y, 1 m ).

-Case Y = (1, 0, V, 1, 0 i-1 , 1, 0, A) and Z = (B, 1) with U = (A, 0 i-1 , B). In this case C2

does not belong to S 3 .

Fact 9 C1 and C3 cannot have both symmetry 2.

Proof. C1 = (0 i-1 , 1, 0, R, 1) and C3 = (0 i , 1 j+1 , 0, R , 1) and R = (1 j-1 , 0, 1, R ), i > 1 and j > 0.

By Symmetry of C3, (1 j+1 , 0, R , 1) = (Y, 0 i , Z) with Y, Z palindromes. Moreover, by superminimality of C1, R cannot contain a sequence of i consecutive 0.

Hence, R = (0 i-1 , U ) which contradicts the definition of C3.

Fact 10 C2 cannot have symmetry 1 when C3 has symmetry 2.

Proof. C2 = (0 i-1 , 1, 0, R, 1) and C3 = (0 i , 1 j+1 , 0, R , 1) and R = (1 j-1 , 0, 1, R ), i > 1 and j > 0.

By Symmetry of C3, (1 j+1 , 0, R , 1) = (Y, 0 i , Z) with Y, Z palindromes. Moreover, by superminimality of C2, R cannot contain a sequence of i consecutive 0 nor finishes by 0 i-1 .

Hence, R = (0 i-1 , U ) which contradicts the definition of C3.

Fact 11 If C2 has symmetry 2 and C3 has symmetry 1, then C2 ∈ S 1 \ S 3 .

Proof. By symmetry with Fact 7.

Fact 12 C2 and C3 cannot have both symmetry 2.

Proof. C2 = (0 i-1 , 1, 0, R, 1) and C3 = (0 i , 1 j+1 , 0, R , 1) and R = (1 j-1 , 0, 1, R ), i > 1 and j > 0.

By Symmetry of C3, (1 j+1 , 0, R , 1) = (Y, 0 i , Z) with Y, Z palindromes. Moreover, by superminimality of C2, R cannot contain a sequence of i consecutive 0 nor finishes by 0 i-1 .

Hence, R = (0 i-1 , U ) which contradicts the definition of C3.

Lemma 8 Let C be a configuration in S 1 \ S 3 with supermin C min = (0 i , 1, R), i > 1, and let C the configuration obtained by applying reduce 2 on only one robot on C. Then C is asymmetric and it is not adjacent with respect to reduce 1 and reduce 2 to any symmetric configuration different from C.

Proof. We first show that C is asymmetric and that cannot it be obtained by applying reduce 1 on a configuration different from C Note that if C min = (0 i , 1 j , 0, X, 1), then it can be obtained by performing reduce 1 on a configuration C such that (i) C = (0 i-1 , 1, 0, 1 j-1 , 0, X, 1), or (ii) C = (0 i-1 , 1 j , 0, X, 0, 1), or (iii) C = (0 i , 1, 0, 1 j+1 , 0, X , 1), where this last case can occur only if X = (1, X ) for some X .

We obtain the following cases.

• C min = (0 i , 1, 0 i , 1, 0, R ). In this case, C has a representation C = (0 i , 1, 0 i+1 , 1, R ) with C min = (0 i+1 , 1, R , 0 i , 1) or C min = (0 i+1 , 1, 0 i , R , 1) since there is only one sequence of i + 1. Therefore, C can have only symmetry 1. However, this implies that R starts with 0 i which is a contradiction to the superminimality of C min as in this case C min contains a sequence of i + 1 consecutive occupied nodes. This also implies that C min = (0 i+1 , 1, 0 i , R , 1). If C can been obtained by applying reduce 1 on a configuration C different from C, then (i) C = (0 i , 1, 0 i+1 , R , 1), or (ii) C = (0 i , 1, 0 i , R , 0, 1). The case (iii) cannot occur as in this case X starts with 0. In the first case the step from C to C does not correspond to reduce 1 , in the second case we obtain C = C in any case we get a contradiction.

• C min = (0 i , 1, 0 i , 1 j , 0, R ), j > 1. In this case, C min = (0 i , 1, 0 i , 1 j-1 , 0, 1, R ). Moreover, such sequence is the only supermin sequence as otherwise we obtain a contradiction to the superminimality of C min . Therefore, C is asymmetric. If C has been obtained by applying reduce 1 on a configuration C different from C, then (i) C = (0 i-1 , 1, 0 i+1 , 1 j-1 , 0, 1, R ), or (ii) C = (0 i-1 , 1, 0 i , 1 j-1 , 0, 1, R , 0, 1) with R = (R , 1). The case (iii) cannot occur as in this case X starts with 0. In both cases (i) and (ii) the step from C to C does not correspond to reduce 1 , a contradiction.

• C min = (0 i , 1 j , 0 x , 1 j , 0, R ), x ≤ i, j > 0, and j > 0. We exclude the case x = i and j = 1 because it has been already analyzed. In this case, C = (0 i , 1 j , 0 x , 1 j -1 , 0, 1, R ).

If x < i -1 or j > 1, then C min = (0 i , 1 j , 0 x , 1 j -1 , 0, 1, R ).
Moreover, such sequence is the only supermin sequence as otherwise we obtain a contradiction to the superminimality of C min . Therefore, C is asymmetric. If C has been obtained by applying reduce 1 on a configuration C different from C, then (i) C = (0 i-1 , 1, 0, 1 j-1 , 0 x , 1 j -1 , 0, 1, R ), (ii) C = (0 i-1 , 1, 0, 1 j-1 , 0 x , 1 j -1 , 0, 1, R , 0, 1) with R = (R , 1), or (iii) C = (0 i , 1 j+1 , 0, 1 j -1 , 0, 1, R ) where x = 1 and j > 1 as otherwise such case cannot occur. In cases (i) and (ii) R contains a sequence of i consecutive occupied nodes and hence the step from C to C does not correspond to reduce 1 , a contradiction. In case (iii) C min = (0 i , 1 j+1 , 0, 1 j -1 , 0, 1, R ) as the superminimality of C implies that either R contains a sequence (0, 1 j , 0 i ) or it finishes by (0, 1 j ). Therefore also in this case, the step from C to C does not correspond to reduce 1 . If x = i -1 and j = 1, then C min = (0 i , 1 j , 0 i-1 , 1, 0, R ) then C ∈ S 3 since R m must finish by 1. If x = 1, j = 1, and j > 1, then C min = (0 i , 1 j , 0 i , 1, 0, R ) is a contradiction as (C min ) i+j < C min . We conclude the proof by showing that C cannot be obtained by applying reduce 2 on a configuration different from C.

Let us assume that C min = (0 i , 1 j , 0 x , 1 j , 0 y , 1, X). After performing reduce 2 on C we have C = (0 i , 1 j , 0 x , 1 j -1 , 0, 1, 0 y-1 , 1, X). Let us assume that C can be obtained by performing reduce 2 on symmetric configuration C different from C. The following cases may arise.

• X = (X , 0 i , 1 j ) and the supermin of C starts from the sequence of i consecutive occupied nodes in X. In this case we have that either C = (0 i-1 , 1, 0, 1 j-1 , 0 x , 1 j -1 , 0, 1, 0 y-1 , 1, X , 0 i , 1 j ) or x = 1 and C = (0 i , 1 j+1 , 0, 1 j -2 , 0, 1, 0 y-1 , 1, X , 0 i , 1 j ). The supermin of C is either C min = (0 i , 1 j , 0 i-1 , 1, 0, 1 j-1 , 0 x , 1 j -1 , 0, 1, 0 y-1 , 1, X ) or C min = (0 i , 1 j , 0 i , 1 j+1 , 0, 1 j -2 , 0, 1, 0 y-1 , 1, X ), respectively. In any case, we must have that j > j otherwise we obtain a contradiction to the superminimality of C min . It follows that C has symmetry 2 and hence X contains a sequence (0 i , 1 j , 0) which is a contradiction to the superminimality of C min . • The supermin of C starts from the same node as C . In this case C min = (0 i , 1 j , 0 x-1 , 1, 0, 1 j -2 , 0, 1, 0 y-1 , 1, X) but in C must exist another sequence which starts by (0 i , 1 j , 0 x ). As C ∈ S , such a sequence is still in C and induces a view which is smaller than C min , a contradiction. • The supermin of C starts from the sequence consecutive occupied nodes corresponding to position i + j of C. Three cases may arise.

x = i, y = 2 and j -1 < j. In this case C = (0 i , 1 j , 0 i , 1 j -1 , 0, 1, 1, 0, X) and C min = (0 i , 1 j -1 , 0, 1, 1, 0, X, 0 i , 1 j ). As j ≥ j by the superminimality of C min , then j = j and hence C min = (0 i , 1 j-1 , 0, 1, 1, 0, X, 0 i , 1 j ). It follows that either X contains a sequence (0 i , 1 j-1 , 0) or that X starts by 0 i-1 and j = 3. In the first case we obtain a contradiction with the Proof. The configuration obtained by applying reduce 2 on only one robot on C is C min = (0 i , 1, 0, 0, 1, 0 x-1 , 1, 0, 1) which is asymmetric as there exists only one sequence of i consecutive occupied nodes and the axis of symmetry cannot pass in the middle of it. Let us assume that C can be obtained by applying reduce 1 or reduce 2 on a configuration different from C. Then two cases may arise.

• C = (0 i-1 , 1, 0, 0, 0, 1, 0 x-1 , 1, 0, 1). In this first case either C min = (0 i-1 , 1, 0, 0, 0, 1, 0 x-1 , 1, 0, 1)

or C min = (0, 0, 0, 1, 0 i-1 , 1, 0, 1, 0 x-1 , 1). In the first case C is asymmetric and in the second case the step from C to C does not correspond to reduce 1 or to reduce 2 . • C = (0 i-1 , 1, 0, 0, 1, 0 x-1 , 1, 0, 0, 1). In this case, if i-1 > 2, then C min = (0 i-1 , 1, 0, 0, 1, 0 x-1 , 1, 0, 0, 1) but the step from C to C does not correspond to reduce 1 or to reduce 2 . If i -1 = 2 then C min = (0, 0, 1, 0, 0, 1, 0, 0, 1, 0 x-1 , 1) and step from C to C does not correspond to reduce 1 , moreover reduce 2 cannot be performed on C has it is in S 3 . If i -1 = 1, then x = 1, C = (0, 1, 0, 0, 1, 1, 0, 0, 1) and C min = (0, 0, 1, 0, 1, 0, 0, 1, 1) and hence the step from C to C does not correspond to reduce 1 or to reduce 2 .

A.5 Searching in a Ring

In this section, we give more details on the algorithm to perpetually search a ring. First, we recall some results concerning the perpetual searching of a ring in the Look-Compute-Move model. In [?], it is shown that, for any starting configuration, it is not possible to search an n-node ring using k robots if n ≤ 9, k ≤ 3, or k ≥ n -2. On the other hand, there is an algorithm allowing 5 ≤ k ≤ n -3 robots to search a ring with n ≥ 10 nodes (except for k = 5 and n = 10), if the initial configuration is rigid. Moreover, in [?] an algorithm for k = n -3 is given.

If k is even and the axis does not pass through an empty node, the searching is clearly unsolvable because a synchronous execution of any algorithm either cause a collision in the node lying on the axis or does not allow to search the edges incident to such node. It follows that in the searching problem, the symmetric allowed configurations are all those with k odd and those with k even where the axis does not pass through an empty node, provided that 3 < k < n -2 and n > 9. Moreover, allowed configurations must be exclusive.

Here, we improve over the algorithm in [?] by addressing also aperiodic symmetric configurations. More precisely, our new algorithm works for any aperiodic allowed configuration such that k = 4, and if n = 10, k ∈ {5, 6}. For asymmetric configuration, the case (n, k) = ( 10 The algorithm given in this section exploits algorithm Align to reach one of the configurations C a , C b , or C c . First, we give two procedures that are used after Align to achieve configuration C b , in the case Align reaches configuration C c , and to achieve C a in the case that k is odd. Algorithm Compact-Align. We now define an algorithm that complements Algorithm Align given in the previous section. In detail, Algorithm Compact-Align is applied until one of the configurations C a (all robots occupy consecutive nodes) or C b (all robots but one occupy consecutive nodes) is achieved.

Algorithm Compact-Align first applies Align. Then, either a configuration C a or C b is achieved, in which case we are done, or a configuration in the set R defined below is achieved. Since the configuration C c (the robots are divided into two segments of consecutive nodes) belongs to R, the specifications of Align Since a and b are even, then b ≥ a + 2, and therefore we can check that any configuration C in R is not adjacent to any other allowed symmetric configuration. Indeed, if C is adjacent to an allowed and symmetric configuration, then the axis must pass through the unique long segment of at least b -1 consecutive 1's, and it is easy to check that such a configuration would not be allowed because b is even. Therefore, there is no conflict between the moves done if C ∈ R and the moves done by Align when Procedure: Search-Ring Input: Exclusive configuration C = (u0, • • • , un-1), with i ui = k robots, k ≥ 6 and n ≥ 10 and (k, n) = (6, 10) and n -k ≥ 3, and such that C has at most one axis of symmetry and, if any and if k is even, this axis does not pass through an empty node. The robot at u0 move to un-1 ; // two symmetrical moves if C ∈ A-a 20 if C = (0 k-4 , 1, 0, 1 (n-k)/2-1-, 0, 1 2 , 0, 1 (n-k)/2--1 , 0, 1) with 0 ≤ ≤ (n -k)/2 -1 ; // C ∈ A-d

> 1. • R 2 (a, b, c) = (0 k/2-c-1 , 1, 0 c+1 , 1 a , 0 c , 1, 0 k/2-c , 1 b ), where 0 ≤ c < k/2. Such a configuration is asymmetric and u n-b-(k/2-c) can be identified. Note also that R 2 (0, b, k/2 -1) ∈ C b . If C ∈ R 1 (

21

OR C = (0 k-4 , 1, 0, 1 (n-k)/2-1-, 0, 1 2 +1 , 0, 1 (n-k)/2--2 , 0, 1) with 0 ≤ ≤ (n -k)/2 -2 ; // C ∈ A-e obtain. Therefore, to prove the correctness of Algorithm Search-Ring, it will be sufficient to prove that Phase 1 and Phase 2 are not in conflict (i.e., that robots can decide which phase to proceed). It is enough to note that any configuration in A is not adjacent to any symmetric configuration not in A.

Theorem 4 Let 4 < k ≤ n -3 robots, standing in an n-node ring forming an allowed configuration, Algorithm Search-Ring perpetually searches the ring, but for n = 10 and k = 5, and for n = 10, k = 6 when the configuration is symmetric.

B Gathering in a ring

In this section, we provide the full strategy for achieving the gathering The allowed symmetric configurations for the gathering are those aperiodic, without an axis of symmetry passing through two edges.

We make use of procedure Align to reach one of the following configuration types: C a = (0 k-1 , 1, 0, 1 n-k-1 ), C b = (0 k , 1 n-k ), with k or n odd, C c = (0 k 2 , 1 j , 0 k 2 , 1 n-k-j ), with j or n odd. Actually, algorithm Align terminates when either the obtained configuration belongs to one of the three types above, or to the types of configurations generated by Algorithm Gathering as we are going to describe.

If the initial configuration has both k and n even, then Align either reaches a configuration of type C a or of type C c with j odd. In the former case, algorithm Gathering leads to C d = (0 k-1 , 1, 1, 0, 1 n-k-2 ). As k < n -4, then C d is asymmetric and it is not adjacent to any possible symmetric configuration with respect to any move of one single robot. From C d , Algorithm Gathering performs reduce 0 , hence creating a multiplicity, and still obtaining a configuration of type C d . This process is repeated until only two nodes remain occupied. At this point, only one of the two occupied nodes contains a multiplicity, while the other contains one single robot. The single robot will be the only one permitted to move towards the other occupied node until the gathering is accomplished. In the latter case, that is, from C c with j odd, algorithm Gathering leads to a configuration of type C c with j = 1. This is achieved by iterating move compact 0 as defined below. Let C = (v 0 , v 1 , . . . , v n ) be a configuration of type (0 k 2 -i , 1, 0 i , 1 j , 0 i , 1, 0 k 2 -i , 1 n-k-j-2 ) where 1 ≤ i ≤ k 2 and j < n-k-2

2

. Note that for i = k 2 , C = C c . Move compact 0 consists in moving the robot at v k 2 -i-1 towards v k 2 -i . As C is symmetric, move compact 0 permits two robots to move. If both move synchronously, the out-coming configuration C is similar to C but with i increased by one. If only one robot moves, the obtained configuration (0 k 2 -i-1 , 1, 0 i+1 , 1 j , 0 i , 1, 0 k 2 -i , 1 n-k-j-2 ) is asymmetric and not adjacent to any other symmetric configuration, and hence C can be easily obtained with the subsequent move. Once configuration C c with j = 1 is reached, again compact 0 is applied. If both the permitted robots move, a symmetric configuration C = (0 k 2 -1 , 1, 0, 1, 0 k 2 -1 , 1 n-k-1 ) with a multiplicity in v k 2 is reached. This equals to the case of symmetric configurations with k odd that will be discussed later. If only one robot moves, configuration (0

k 2 -1 , 1, 0 k 2 +1 , 1 n-k-1
) is reached. As k is even, then 4 < k < n -4 and hence, such a configuration is asymmetric and not adjacent to any other symmetric configuration, and hence C can be easily obtained with the subsequent move.

If k is even and n is odd, then Align either reaches a configuration of type C b or of type C c with either j or n -k -j odd. In this case, Algorithm Gathering behaves as above but creating the multiplicity at the central node of the only odd sequence of consecutive empty nodes among j and n -k -j. Eventually, algorithm Gathering achieves configuration C . Again, this equals to the case of symmetric configurations with k odd. Note that, this case is similar to the technique presented in [?] where the solved configurations are only those with k even and n odd.

If the initial configuration has k odd, then Align always reaches a configuration of type C b . In this case, the used technique is similar to that presented in [?] where the solved configurations are only those with k odd. From C b , Algorithm Gathering permits robots at v k-1 2 -1 and v k-1 2 +1 to move towards v k-1

2

. If only one robot performs the move, configuration (0

k 2 -1 , 1, 0 k 2 +1 , 1 n-k -1
) is achieved with k = k -1. By the parity of k , configuration C is achieved by the subsequent move. If both robots perform the move synchronously, again configuration C is reached. From here, Algorithm Gathering performs move compact 1 defined as follows. Let C = (v 0 , v 1 , . . . , v n ) be a configuration of type (0

k-i 2 , 1, 0 i , 1, 0 k-i 2 , 1 n-k-2
) where 1 ≤ i ≤ k, then compact 1 consists in moving the robot at v k-i 2 -1 towards v k-i 2 . As C is symmetric, move compact 1 permits two robots to move. If both move synchronously, the outcoming configuration C is similar to C but with i increased by two. If only one robot moves, as before, the obtained configuration is asymmetric and not adjacent to any other symmetric configuration, and hence C can be easily obtained with the subsequent move. By iterating this process, Algorithm Gathering achieves a configuration of type C b with the number of occupied nodes decreased by two with respect to the original configuration. Eventually, this process terminates with only one occupied node.

13 reduce 2 (

 132

Figure 3 :

 3 Figure 3: Second phase of algorithm Align for symmetric configurations.

7 if C i is symmetric and allowed then 8 if 11 Let 12 if C = C then 13 if

 78111213 C i has no consecutive occupied nodes then 9 Let C be the configuration obtained by executing Align-One on C i ; 10 else C be the configuration obtained by executing Align-Two-Sym on C i ; The robot that moved from C i to C is not the one on the axis of symmetry of C i then 14 Perform the reduce 0 move symmetrical to the one from C to C and exit; 15 Asym(C);

Figure 4 :

 4 Figure 4: Second phase of algorithm Align for symmetric configurations.

reduce 1 reduce 1 reduce 2 (

 2 a) Configuration C. (b) Configuration C computed from C by applying reduce1. (c) Configuration C computed from C by applying reduce2. (d) Configuration C α computed from C in Procedure Align-Two-Asym. (e) Configuration C γ computed from C in Procedure Align-Two-Asym. (f) Configuration C δ computed from C in Procedure Align-Two-Asym.

Figure 5 :

 5 Figure 5: First example

reduce 1 reduce 1 reduce 2 (

 2 a) Configuration C. (b) Configuration C computed from C by applying reduce1. (c) Configuration C computed from C by applying reduce2. (d) Configuration C β computed from C in Procedure Align-Two-Sym. (e) Configuration C γ computed from C in Procedure Align-Two-Sym.

Figure 6 :

 6 Figure 6: Second example

Fact 1 C1

 1 and C2 cannot have both symmetry 1.

Fact 4

 4 If C1 has (only) symmetry 1 and C2 has (only) symmetry 2, then C2 ∈ S 2 .

Fact 7

 7 If C1 has symmetry 2 and C3 has symmetry 1, then C1 ∈ S 1 \ S 3 .

, 6 )

 6 is feasible, therefore the only cases left open are k = 4, (n, k) = (10, 5), and (n, k) = (10, 6) symmetric.

k 2 , 1 j , 0 k 2 ,

 202 (it achieves either C a or C b or C c and it may reach C c only if k and n are even) ensure that such a configuration is eventually reached. Finally, from any configuration in R, Algorithm Compact-Align allows the robots to achieve either C a or C b . If C ∈ R, then both k and n are even. Recall that any allowed configuration in C c has the following form: (0 1 n-k-j ), with 0 < j < n-k 2 and j even. For any 0 ≤ a < b with a and b = n -k -a -2 even (in particular b > 1), let us define R = R 1 ∪ R 2 as the set of all configurations C = (u 0 , • • • , u n-1 ) with the following form: • R 1 (a, b, c) = (0 k/2-c , 1, 0 c , 1 a , 0 c , 1, 0 k/2-c , 1 b ), where 0 ≤ c < k/2. Note that R 1 (a, b, 0) ∈ C c . Moreover, any configuration R 1 (a, b, c) is symmetric with one unique axis (because a < b) and this axis does not pass through an empty node (because a and b are even). Moreover, u k/2-c-1 and u n-1-b can be identified because a < b and b

  a, b, c) for some a, b, and c, then Compact-Align moves the robot at u k/2-c-1 to u k/2-c . Otherwise, if C ∈ R 2 (a, b, c) for some a, b, and c, then it moves the robot at u n-b-(k/2-c) to u n-b-(k/2-c-1) , otherwise it applies Align.

11 if C ∈ A then 12 if 15 The

 111215 C = (0 k-2 , 1 , 0, 1 n-2 -k , 0, 1 ) with 0 ≤ ≤ (n -k)/2 ; // C ∈ A-a 13 OR C = (0 k-2 , 1 , 0, 1 n-2 -k-1 , 0, 1 ) with 0 ≤ < (n -k)/2; // C ∈ A-b 14 then robot at u k-2+ moves to u k-2+ +1 ; // two symmetrical moves if C ∈ A-a 16 if C = (0 k-2 , 1 (n-k)/2 , 0, 0, 1 (n-k)/2 ) ; // C = A-a((n -k)/2) 17 OR C = (0 k-3 , 1, 0, 1 (n-k)/2-1 , 0, 0, 1 (n-k)/2 ) ; // C = A-c 18 then 19

22 then 23 Figure 9 :

 239 Figure 9: Algorithm Search-Ring.

RR n°8250

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

Appendix A Align Algorithm

else if C = (1, 1, 0, 1, 0, 1, 1, 0, X , 0), C min = (0, 1, 0, 1, 1, 0, X , 0, 1, 1), and X = X then if The robot that moved from C to C is not the one on the axis of symmetry of C then Perform the reduce 0 move symmetrical to the one from C to C and exit; else if C min = (0, 1, 0, 1 j , 0, 1, X ) then

Let C = (0, 1, 0, 1 j+1 , 0, X );

if C is symmetric and allowed and C min = (0, 1, 0, 1 j+1 , 0, X ) then if The robot that moved from C to C is not the one on the axis of symmetry of C then Perform the reduce 0 move symmetrical to the one from C to C and exit; Asym(C); Figure 2: First phase of algorithm Align.

-Then, assume U = ∅. Therefore, U must contain at least one 1 since otherwise, R = (U, 0 i-1 , 1 j ) would have at least i consecutive 0. But, if U contains at least one 1, because (0, R ) = (R , 0), we get (0, U, 0 i-1 ) = (0 i-1 , U , 0) and U = (0 i-2 , U ) with U palindrome. Because Y is a palindrome, (1, 0, 1 j-1 , 0, 1, 0 i-2 , U ) = (U , 0 i-2 , 1, 0, 1 j-1 , 0, 1). By Lemma 4, there is ≥ 0 such that * U = ((1, 0, 1, 0, 1, 0) , 1) only if i = 3 and j = 2, or * U = ((1, 0, 1, 0, 1, 0) , 1, 0, 1) only if i = 3 and j = 2, or * U = ((1, 0, 1 j-1 , 0, 1, 0 i-2 ) , 1, 0, 1 j-1 , 0, 1). Therefore, since R = (0 i-2 , U , 0 i-1 , 1 j ), * R = (0, (1, 0, 1, 0, 1, 0)

, 1, 0 2 , 1 2 ) only if i = 3 and j = 2, or * R = (0, (1, 0, 1, 0, 1, 0)

, 1, 0, 1 j-1 , 0, 1, 0 i-1 , 1 j ). In any case, by plugging R into C1, we have that

, 0) and U palindrome. Because, i > 1 and j > 0, by Lemma 4, there is a solution for U only for i = 2 and j = 3. In this case, there is ≥ 0 with U = ((0, 1, 0, 1, 0, 1 4 ) , 0, 1, 0, 1, 0). Hence, R = (1, 0, 1, 0, 1 4 , (0, 1, 0, 1, 0, 1 4 ) n-24 9

, 0, 1, 0, 1, 0, 1 3 ) and

, 0, 1, 0, 1, 0, 1 4 ).

In this case, C1 15 is strictly smaller than C1, a contradiction to the superminimality of C1.

, 0, 1) and j = 0, a contradiction. * Case U = (0, U , 0) and U palindrome. Then (V , 1, 0, 1 j-1 , 0, 1, 0 i-1 , 1 j+1 , 0, U ) = (U , 0, 1 j+1 , 0 i-1 , V , 1, 0, 1 j-1 , 0, 1).

It follows that U starts and finishes with 1 and then also V starts and finishes with 1, while V and R start with 1. Then, we define R such that R = (1, R ). As (0, R ) = (R , 0), then (0, 1, R ) = (R , 1, 0). The following two cases may arise.

• R = (0). In this case R = (1, 0), R = (1, 0, 1 j ), and C1 = (0 i-1 , 1, 0, 1 j-1 , 0, 1, 1, 0, 1 j+1 ) which is not symmetric, a contradiction. • R = (R , 1, 0) with R possibly empty. In this case, as (0, 1, R ) = (R , 1, 0), we have that (0, 1, R , 1, 0) = (0, 1, R , 1, 0) and then R is palindrome. Plugging R into C1 we obtain C1 = (0 i-1 , 1, 0, 1 j-1 , 0, 1, 1, 0, 1 j+1 ). As C1 has symmetry 2, then there exist an index such that C1 = C1. Moreover > i + j + 3, in other words, the sequence C1 starts in one of the elements of R . As R is palindrome, then there exists an = such that C1 = C1 and C1 starts in one of the elements of R . In detail, if C1 starts at the k-th element of R , then C1 starts at the (|R | -k)-th element of R . However, the elements at the two sides of R in C1 are different, in particular at one side of R there is (1, 1) while at the other side it is (1, 0). This is a contradiction as it implies that the element a position k + 2 of C1 is 1, while the element at position k + 2 of C1 is 0 and C1 and C1 are equal until element k + 1 and hence C1 is strictly smaller than C1 , a contradiction to the superminimality of C1.. Proof. C1 = (0 i-1 , 1, 0, R, 1) and C2 = (0 i-1 , 1, 0, R, 1). By symmetry, (1, 0, R, 1) = (Y, 0 i-1 , Z) and (1, 0, R, 1) = (Y , 0 i-1 , Z ) with Y, Z, Y and Z palindromes. In any case both C1 and C2 are in S 1 , we then need to show that they are not in S 3 .

• Case Y = (1). In this case C1 ∈ S 2 and, since S 2 is contained in S 1 and disjoint from S 3 , then

The following cases may arise.

-Case Y = (1, 0, V , 1) and Z = (1, U , 1). In this case, V is a palindrome because Z is a palindrome, and U is a palindrome because of Z . Moreover, by symmetry of Y and Y , (0, U ) = (U, 0) and (0, V ) = (V, 0). By Lemma 4, there are , ≥ 0 such that U = (0) and

we assume that both C1 and C2 belong to S 3 . Therefore, U = (1 j ) and A = (1 j , 0, 1) for some j, j > 0. As V is palindrome, then

From the first equality, we obtain that * B = (1 j ), j = j , and i = 2. In this case, Z = Z = (1 j+1 , 0, 1, 0, 1 j+1 ) and therefore, C1 = C2, a contradiction. * B = (B , 0 i-1 , 1, 0, 1 j ) = (1 j+1 , 0, 1, 0 i-1 , 1, B ), B = (1 j+1 ), B = (1 j-1 ) and i = 2. In this case, Z = (1 j +1 , 0, 1, 0, 1 j+1 , 0, 1, 0, 1 j +1 ) and Z = (1 j+1 , 0, 1, 0, 1 j +1 , 0, 1, 0, 1 j.+1 ), then, C1 = (0, 1, 0, 1 j , 0, 1, 0, 1 j +1 , 0, 1, 0, 1 j+1 , 0, 1, 0, 1 j +1 ) and C2 = (0, 1, 0, 1 j , 0, 1, 0, 1 j+1 , 0, 1, 0, 1 j +1 , C1 and C2 are supermin if and only if j + 1 > j and j + 1 > j , respectively. It follows that j = j and then C1 = C2, a contradiction. * B = (B , 0 i-1 , 1, 0, 1 j ) = (1 j+1 , 0, 1, 0 i-1 , 1, B ), B = (1, 0, 1), B = (0) and j = j = 0.

In this case C1 = (0

C1 and C2 are supermin if and only if j + 1 > j and j + 1 > j , respectively. It follows that j = j and hence B = (1 j+1 , 0, 1, 0 i-1 , 1, B ), and B = (B , 0 i-1 , 1, 0, 1 j ).

We obtain a contradiction by showing that B and B cannot be palindrome at the same time. To this aim we prove the following statement: Let X and Y be two sequences such that (X, 1,

) with Y palindrome and m > 0. To obtain a contradiction, we set X = (1 j+1 , 0, 1, 0 i-1 ) and Y = B . We first assume that |X| < |Y |. Then, as (X, 1, Y ) = (Y , 1, X), we define Y such that Y = (Y , X). By plugging Y into the same equality, we obtain (X, 1, Y , X) = superminimality of C min , in the second case the step from C to C does not correspond to reduce 2 , a contradiction. x = i -1, j = 1, and j > 1. In this case, C = (0 i , 1 j , 0 i , 1, 0 y-1 , X) with C min = (0 i , 1, 0 y-1 , X, 0 i , 1 j ). We assume that X = (1 j , 0, X ) which implies that C min = (0 i , 1, 0 y-1 , 1 j -1 , 0, 1, X , 0 i

In order to be symmetric, C min must contain another sequence starting by (0 i , 1, 0) but this implies a contradiction to the superminimality of C min . x = i -1, j = 1, and j > 1. In this case, C = (0 i , 1 j , 0 i+1 , 1, 0 y-1 , X) and C min = (0 i+1 , 1, 0 y-1 , X, 0 i , 1 j ). again we assume that X = (1 j , 0, X ) and this implies that C min = (0 i+1 , 1, 0 y-1 , 1 j -1 , 0, 1, X , 0 i , 1 j ) which cannot be symmetric as there is only one sequence of i + 1 consecutive occupied nodes and j > 1.

Lemma 9 Let C be a configuration in S 2 , or C min = (0 i , 1, 0, 0, 1, 0 i , (1, 0, 1, 0 i ) , 1, 0, 1), or

and let C the configuration obtained by applying reduce -1 on only one robot on C. Then C is asymmetric and it is not adjacent with respect to reduce 1 , reduce 2 , and reduce -1 to any symmetric configuration different from C.

Proof. If C min = (0 i , 1, 0, 0, 1, 0 i , (1, 0, 1, 0 i ) , 1, 0, 1), then C min = (0 i+1 , 1, 0, 0, 1, 0 i , (1, 0, 1, 0 i ) , 1, 1). It is easy to see that C is asymmetric since there is only one sequence of i + 1 consecutive occupied nodes. If C can be obtained by applying reduce 1 , or reduce 2 , or reduce -1 on a configuration C different from C, then C min = (0 i , 1, 0, 0, 0, 1, 0 i , (1, 0, 1, 0 i ) , 1, 1), or C min = (0 i+1 , 1, 0, 1, 0 i+1 , (1, 0, 1, 0 i ) , 1, 1). In any case C is asymmetric.

If

Therefore, C min can be obtained by applying reduce 1 , or reduce 2 , or reduce -1 on a configuration

Let us assume w.l.o.g. that Z = (1 j , 0, Z , 0, 1 j ) with Z = Z and j ≥ j. Then, C min = (0 i , 1 j , 0 i , 1 j , 0, Z , 0, 1 j ). We distinguish the following cases

• j = 1. In this case j = 1 and hence C min = (0 i , 1, 0 i , 1, 0, Z , 0, 1) and C min = (0 i+1 , 1, 0 i , 1, 0, Z , 1). By Lemma 4, C can be symmetric only if Z = (0, 1, 0) and i = 1, a contradiction. If C can be obtained by applying reduce 1 , or reduce 2 , or reduce -1 on a configuration C different from C, then C = (0 i , 1, 0 i+1 , 1, 0, Z , 1), or C = (0 i+1 , 1, 0 i-1 , 1, 0, 0, Z , 1), or C = (0 i+1 , 1, 0 i , 1, 1, Z , 1, 1) where Z = (1, Z , 1). In the first case, the step from C to C does not correspond to any of reduce 1 , or reduce 2 , or reduce -1 . In the second case C is symmetric only if Z = ((0, 0, 1, 0, 0) ) and i = 3, in which case C min = (0, 0, 0, 1, 0, 0, 0, 1, 0, (0, 0, 1, 0, 0) , 0, 1) which is periodic. In the third case C is asymmetric.

• j > 1. In this case C = (0 i , 1 j , 0 i , 1 j , 0, Z , 1, 0, 1 j -1 ).

If j = j, then C min = (0 i , 1 j-1 , 0, 1, Z , 0, 1 j , 0 i , 1 j ). It follows that C is asymmetric and that it can be obtained by applying reduce 1 , or reduce 2 , or reduce -1 on a configuration C different from C only if: C = (0 i-1 , 1, 0, 1 j-2 , 0, 1, Z , 0, 1 j , 0 i , 1 j ) or C = (0 i-1 , 1 j-1 , 0, 1, Z , 0, 1 j , 0 i , 1 j-1 , 0, 1). In the first case C is asymmetric, in the second case the step from C to C does not correspond to any of reduce 1 , or reduce 2 , or reduce -1 . If j > j, then C min = (0 i , 1 j , 0 i , 1 j -1 , 0, 1, Z , 1, 0, 1 j ) and C is asymmetric as another supermin would imply a contradiction to the superminimality of C. C can be obtained by applying reduce 1 , or reduce 2 , or reduce -1 on a configuration C different from C only if: C = (0 i-1 , 1, 0, 1 j-1 , 0 i , 1 j -1 , 0, 1, Z , 1, 0, 1 j ), or C = (0 i-1 , 1 j , 0 i , 1 j -1 , 0, 1, Z , 1, 0, 1 j -1 , 0, 1) or C min = (0 i , 1 j , 0 i-1 , 1, 0, 1 j -2 , 0, 1, Z , 1, 0, 1 j ). In any case the step from C to C does not correspond to any of reduce 1 , or reduce 2 , or reduce -1 .

Lemma 10 Let C be a configuration with supermin C min = (0 i , 1, 0, 1, 0 x , 1, 0, 1), i > 1 and x < i, and let C the configuration obtained by applying reduce 2 on only one robot on C. Then C is asymmetric and it is not adjacent with respect to reduce 1 and reduce 2 to any symmetric configuration different from C. C / ∈ R.

Procedure: Compact-Align Input: Allowed configuration C = (u0, • • • , un-1), with an even number of robots.

Robot at u k/2-c-1 moves to u k/2-c ; // Two symmetrical moves Algorithm Break-Symmetry. In the following, we give an algorithm that allows an odd number k of robots to eventually reach an asymmetric configuration. More precisely, the algorithm first applies Algorithm Align. Then, when all k robots are occupying consecutive nodes, they move to reach a symmetric configuration where one robot is on the axis and has its two neighbors that are empty. The robot on the axis moves to one of its neighbors, breaking the symmetry.

) with the following form:

), where 0 ≤ ≤ k/2 . Moreover, any configuration R 1 ( ) is symmetric with one unique axis and nodes u +1 and u k-+1 can be univocally identified.

), where 0 < ≤ k/2 . Such a configuration is asymmetric and u can be univocally identified. When a configuration C is in B 1 ( ) for some , then Break-Symmetry moves the robot at u +1 to u . When C is in B 1 ( ) for some , then Break-Symmetry moves robot at u to u -1 . Eventually, configuration C = (0 k/2 , 1, 0, 1, 0 k/2 , 1 n-k-2 ) is reached. At this point the robot at u k/2 +1 moves to u k/2 (or arbitrarily to u k/2 +2 ). At this point the obtained configuration is asymmetric and applying algorithm Align leads to configuration C a = (0 k-1 , 1, 0, 1 n-k-1 ). Finally, the robot at k moves to k + 1. The obtained configuration is suitable to be used in the algorithm of [?] for graph searching. As any asymmetric configuration in B 2 is not adjacent to any symmetric configuration not in B 1 , there are no conflicts between the moves of Align, those of the algorithm in [?] and those of Break-Symmetry.

Procedure: Break-Symmetry Input: Exclusive configuration C = (u0, • • • , un-1), with i ui = k robots, such that k is odd and C has at most one axis of symmetry and, if any, this axis does not pass through an empty node.

Robot at u k/2 +1 moves to u k/2 (or symmetrically to u k/2 +2 ) ; // symmetry is broken

Robot at u +1 moves to u ; // Two symmetrical moves

) where 0 < ≤ k/2 ; // C ∈ B2 Algorithm Search-Ring. Algorithm Search-Ring first checks whether k = n -3 or if n is odd and k is even. In the affermative case, any allowed configuration must be asymmetric, and therefore the algorithm of [?] can be applied and the ring is searched.

If k is odd, we first use Algorithm Break-Symmetry to break the potential symmetry and then use the algorithm of [?]. Each of these configurations used during the searching phase of the algorithm of [?] are asymmetric and are not adjacent to any symmetric configuration reached by Algorithm Break-Symmetry. Therefore, there is no ambiguity (no pending move) when a robot recognizes such a configuration.

If n and k are even, we may be in allowed symmetric configurations and therefore the Algorithm Search-Ring proceeds in two phases. Algorithm Compact-Align is first applied until one of the configurations in A (described in Appendix) is achieved. This is guaranteed by the fact that both C a and C b belong to A. Then, the algorithm proceeds to Phase 2 which actually performs the searching. Set A of configurations. We now define the set A of configurations required to define the algorithm for Phase 2. We consider the following hypothesis: n -k is even, n -k ≥ 4, k ≥ 6, n ≥ 10 and, if k = 6 then n ≥ 11. The set A is defined as the set of all configurations C = (u 0 , • • • , u n-1 ) with the following forms:

In this case, C is symmetric with a unique axis because k -2 > 1. This axis does not pass through an empty node because n -k is even. Clearly, nodes u k-2+ and u n-1-can be identified as occupied and adjacent to one (case = 0) or two (case 0 < < (n -k)/2) empty nodes, or (case = (n -k)/2) they form the unique (because k ≥ 5) segment of exactly two consecutive occupied nodes.

In this case, C is asymmetric for any 0 ≤ ≤ (n -k)/2. In particular, if = 0, it is asymmetric because n -k ≥ 4. Then, u k-2+ can be identified.

In this case, C is asymmetric, because k ≥ 6 and n -k ≥ 4. Then, u 0 can be identified.

In this case, C is symmetric with one unique axis not passing through an empty node. Indeed, it is easy to check if k = 6. If k = 6 and = 0, it is true because n > 10.

Then, u (n+k)/2-3 and u (n+k)/2-2 can be identified as the single segment of two occupied nodes (if k > 6) and as the single segment of two occupied nodes adjacent to segments of more than one empty node (if k = 6 and n > 10). A-e( ) = (0 k-4 , 1, 0, 1 (n-k)/2-1-, 0, 1 2 +1 , 0, 1 (n-k)/2--2 , 0, 1), 0 ≤ ≤ (n -k)/2 -2.

In this case, C is asymmetric (this is true in particular, when = 0, because if k = 6 then n > 10) Then, u (n+k)/2-3-can be identified. A-f = (0 k-3 , 1, 0, 0, 1 n-k-2 , 0, 1)

In this case, C is asymmetric because k ≥ 5 and n -k ≥ 4. Then, u k-2 can be identified. The pseudo-code of Algorithm Search-Ring is given in Figure 9 The intuitive explication of the Searching algorithm (Phase 2) is as follows. All robots are aligned on consecutive nodes (configuration A-a(0) = C a ). Then, each of the two robots X and Y at the ends of this segment move (one clockwise and the other anti-clockwise) to meet on the two adjacent nodes opposite to the occupied segment (passing "alternatively" from configuration A-a( ) to configuration A-b( ) for = 0 • • • (n -k)/2). Then, the two robots X and Y occupying the ends of the "long" occupied segment move to their empty neighbor (A-a(n -2 -k) and A-c). These moves are two indicate to X and Y that it is time to go back toward the "long" segment, and that is what happens (passing "alternatively" from configuration A-d( ) to configuration A-e( ) for = 0 • • • (n -k)/2 -2). Finally, when X is adjacent to X and Y is adjacent to Y , X and Y move to their empty neighbor (passing through the configuration A-f) such that they re-integrate the segment. Then, Configuration A-a(1) is achieved and the process is repeated perpetually.

It is easy to check that such a sequence of moves actually search the ring and, by definition of the configurations met during the process (configurations in A), there is no ambiguity. In Algorithm 9, O denotes the set of configurations used during the searching phase of the Algorithm of [?].

The distinct configurations that can be achieved in Phase 2 are the ones in A and can be characterized succinctly such that they are pairwise distinguishable without ambiguity. Moreover, each of those configurations is either asymmetric and only one (identifiable) robot can move, or it is symmetric with one unique axis of symmetry and two (identifiable) symmetric robots move. In the latter case, when only one of these symmetric robots moves, then we reach an asymmetric configuration where the only robot permitted to move is the other one (i.e., the possible pending move and the permitted move coincide). Therefore there is never ambiguity in the choice of the robot(s) that must move.

The validity of algorithms for Phase 2 and the fact that they actually search the ring are easy to