Sylvain Merlet

Emmanuel Caruyer

Aurobrata Ghosh

Rachid Deriche

Parametric Dictionary Learning in Diffusion MRI

I. INTRODUCTION

In this work, we propose an approach to exploit the ability of compressive sensing to recover diffusion MRI signal and its characteristics from a limited number of samples. Our approach is threefold. First, we learn and design a parametric dictionary from a set of training diffusion data. This provides a highly sparse representation of the diffusion signal. The use of a parametric method presents several advantages: we design a continuous representation of the signal, from which we can analytically recover some features such as the ODF; besides, the dictionary we train is acquisition-independant. Next, we use this sparse representation to reconstruct the signal of interest, using cross-validation to assess the optimal regularization parameter for each signal reconstruction. The use of cross-validation is critical in the ℓ1 minimization problem, as the choice of the parameter is sensitive to the noise level, the number of samples, and the data sparsity. Third, we use a polynomial approach to accurately extract ODF maxima. In the last section, we motivate and describe the choice of experimental parameters for the HARDI contest.

II. PARAMETRIC DICTIONARY LEARNING

A. Sparse reconstruction

We reconstruct the signal in an over-complete dictionary of continuous functions. Given a signal y ∈ R N , this is expressed from the coefficient vector x ∈ R M as y = HDx + ǫ.

(

) 1
The matrix H is the standard N × R design matrix of the underlying family of continuous functions. The dictionary D ∈ R R×M , is a linear sparsifying transform, such that the signal y can be reconstructed from a limited number of atoms. This matrix does not depend on the choice of a specific acquisition protocol. The reconstruction is done by minimizing ||y -HDx||2 + λ||x||1 . Here we propose to learn the dictionary D from a training dataset.

B. Parametric dictionary learning

We can rewrite Eq. 1 as y = Hc + ǫ, and c = Dx. Given a training set of signals Y of size N × S, we first estimate the coefficients C = (H T H) -1 H T Y. Then we look for a dictionary D of size R × M and a code X of size M × S verifying arg min

D,X ||C -DX|| 2 2 + α||X||1, s.t. ∀m ≤ M, ||dm||2 = 1 (2)
with dm the m th column of D. We use the python library scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in python[END_REF] to solve this problem.

III. CROSS-VALIDATION

We use cross validation to assess λ [START_REF] Ward | Compressed sensing with cross validation[END_REF]. In particular, we use a Kfold Cross Validation, which consists in splitting the entire data set in K subsets. K -1 subsets are used to reconstruct the signal whereas the K th subset enables a tight estimation of regularization parameter λK via the evaluation of a cross validation distance. This operation is repeated K times by considering another subset. Then, we keep an average value, λ = 1 K P K i=1 λi . To avoid a drastic increase of the computational effort, we split our data set in 5 partitions, i.e. K = 5.

Our previous experiments showed that it is sufficient to obtain a close approximation of the optimal λ.

IV. A POLYNOMIAL APPROACH FOR MAXIMA EXTRACTION

The HARDI contest is based on fiber orientation estimation via the extraction of ODF maxima. After computing the ODF, we extract its maxima using a polynomial approach that can analytically bracket and numerically refine with high precision all maxima, ensuring that none are missed [START_REF] Ghosh | A polynomial approach for maxima extraction and its application to tractography in hardi[END_REF]. First, leveraging the linear bijection between the spherical harmonic basis and the homogeneous polynomial basis of the same order and degree, we rewrite the ODF as a polynomial, P(x = [x1, x2, x3]), with x 2 = 1. Second we formulate the optimization problem for computing the ODF extrema:

∂F/∂x1 = ∂F/∂x2 = ∂F/∂x3 = x 2 2 -1 = 0, (3)
where using Lagrange multipliers F (x, Λ) = P(x) -Λ ( x 2 2 -1). However, instead of optimizing, which is inherently a local approach dependent on initializations, we solve the polynomial system Eq. 3 using a polynomial system solver that can analytically bracket all roots -missing none and refine them numerically to high precision. Finally, we identify the maxima from the extrema using the Bordered Hessian, which is the generalization of the Hessian.

V. EXPERIMENTAL PARAMETERS

For the HARDI contest, we choose H to be constituted of the continuous SPF basis functions [START_REF] Assemlal | Efficient and robust computation of pdf features from diffusion mr signal[END_REF], [START_REF] Caruyer | Optimal Regularization for MR Diffusion Signal Reconstruction[END_REF] and constrain our dictionary D to represent a combination of the SPF functions. We choose the SPF basis because it facilitates the ODF estimation [START_REF] Cheng | Model-free, regularized, fast, and robust analytical orientation distribution function estimation[END_REF]. We learn our dictionary on the training data set given for the HARDI contest. Then we probe the testing data set on 15 measurements uniformly spread on a single shell at b value b = 2000s • mm -2 .


D ' Gianlorenzo
email: gianlorenzo.d_angelo@inria.fr

Angelo

Gabriele Di
email: gabriele.distefano@univaq.it

Alfredo Navarra
email: alfredo.navarra@unipg.it

How to gather asynchronous oblivious robots on anonymous rings

Keywords: distributed algorithm, asynchronous system, gathering, oblivious robots

A set of robots arbitrarily placed on the nodes of an anonymous graph have to meet at one common node and remain in there. This problem is known in the literature as the gathering. Robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), decides whether to stay idle or to move to one of its neighbors (Compute), and in the latter case makes the computed move instantaneously (Move). Cycles are performed asynchronously for each robot. Moreover, each robot is empowered by the so called multiplicity detection capability, that is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. The described problem has been extensively studied during the last years. However, the known solutions work only for specific initial configurations and leave some open cases. In this paper, we provide an algorithm which solves the general problem, and is able to detect all the non-gatherable configurations. It is worth noting that our new algorithm makes use of a unified and general strategy for any initial configuration.

Comment rassembler robots asynchrones et inconscients sur les anneaux anonymes

Résumé : Un ensemble de robots placés arbitrairement sur les sommets d'un graphe anonyme doivent se rencontrer sur un sommet commun. Ce problème est connu dans la littérature comme le gathering. Les robots utilisent des cycles Look-Compute-Move; dans un cycle, un robot prend un instantané de la configuration actuelle (Look), décide de rester inactif ou de se déplacer sur l'un de ses voisins (Compute), et dans ce cas, fait le déplacement (Move). Les cycles sont exécutés de manière asynchrone pour chaque robot. Chaque robot possède la capacité de multiplicity detection: un robot est capable de détecter au cours de son opération Look si un sommet est vide, occupé par un robot, ou occupé par un nombre indéfini de robots. Le problème décrit a été largement étudié au cours des dernières années. Toutefois, les solutions connues ne sont valides que pour des configurations initiales spécifiques. Nous fournissons un algorithme qui résout le problème général, et est capable de détecter toutes les configurations initiales pour lesquelles le problème est impossible. Il est intéressant de noter que notre nouvel algorithme utilise une stratégie unifiée et générale pour chaque configuration initiale.

Mots-clés : distributed algorithm, asynchronous system, gathering, oblivious robots

1 Introduction

We study one of the most fundamental problems of self-organization of mobile entities, known in the literature as the gathering problem (see e.g., [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF][START_REF] Degener | A tight runtime bound for synchronous gathering of autonomous robots with limited visibility[END_REF][START_REF] Flocchini | Gathering of asynchronous robots with limited visibility[END_REF] and references therein). In particular, we consider oblivious robots initially located at different nodes of an anonymous ring that have to gather at the same common node (not determined in advance) and remain in there. Neither nodes nor links have any labels. Initially, some of the nodes of the ring are occupied by robots and there is at most one robot in each node. Robots operate in Look-Compute-Move cycles.

In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it moves to this neighbor (Move), eventually. Cycles are performed asynchronously for each robot. This means that the time between Look, Compute, and Move operations is finite but unbounded, and it is decided by the adversary for each robot. Hence, robots may move based on significantly outdated perceptions. The only constraint is that moves are instantaneous, and hence any robot performing a Look operation sees all other robots at nodes and not on edges. Robots are all identical, and execute the same deterministic algorithm. Moreover, they have the so called multiplicity detection capability (see e.g. [START_REF] Izumi | Randomized gathering of mobile robots with local-multiplicity detection[END_REF]), that is the ability to perceive during the Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. Without this capability the gathering would be impossible [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF].

Related Work and Our Results

The problem of let meet mobile entities on graphs [START_REF] Bampas | Almost optimal asynchronous rendezvous in infinite multidimensional grids[END_REF][START_REF] Dessmark | Deterministic rendezvous in graphs[END_REF][START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF] or open spaces [START_REF] Cord-Landwehr | A new approach for analyzing convergence algorithms for mobile robots[END_REF][START_REF] Degener | A tight runtime bound for synchronous gathering of autonomous robots with limited visibility[END_REF] has been extensively studied in the last decades. When only two robots are involved, the problem is usually referred to as the rendezvous problem [START_REF] Alpern | The rendezvous search problem[END_REF][START_REF] Chalopin | Rendezvous of mobile agents without agreement on local orientation[END_REF][START_REF] Czyzowicz | How to meet asynchronously (almost) everywhere[END_REF][START_REF] Dessmark | Deterministic rendezvous in graphs[END_REF][START_REF] Yamashita | Gathering two stateless mobile robots using very inaccurate compasses in finite time[END_REF]. Under the Look-Compute-Move model, many problems have been addressed, like the graph exploration and the perpetual graph exploration [START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF][START_REF] Devismes | Optimal probabilistic ring exploration by semisynchronous oblivious robots[END_REF][START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF][START_REF] Flocchini | Remembering without memory: Tree exploration by asynchronous oblivious robots[END_REF], while the rendezvous problem has been proved to be unsolvable on rings [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF].

Concerning the gathering, different types of configurations have required different approaches. In particular, periodicity and symmetry arguments have been exploited. A configuration is called periodic if it is invariable under non-trivial (i.e., non-complete) rotation. A configuration is called symmetric if the ring has a geometrical axis of symmetry, that reflects single robots into single robots, multiplicities into multiplicities, and empty nodes into empty nodes. A symmetric configuration with an axis of symmetry has an edge-edge symmetry if the axis goes through two edges; it has a node-edge symmetry if the axis goes through one node and one edge; it has a node-node symmetry if the axis goes through two nodes; it has a robot-on-axis symmetry if there is at least one node on the axis of symmetry occupied by a robot.

In [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF], it is proved that the gathering is not solvable for periodic configurations, for those with edge-edge symmetry, and if the multiplicity detection capability is removed. Then all configurations with an odd number of robots, and all the asymmetric configurations with an even number of robots have been solved by different algorithms. In [START_REF] Klasing | Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring[END_REF], the attention has been devoted to the symmetric cases with an even number of robots, and the problem was solved when the number of robots is greater than 18. These left open the gatherable symmetric cases of an even number of robots between 4 and 18. Most of the cases with 4 robots have been addressed in [START_REF] Koren | Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydzialu ETI Politechniki Gdanskiej[END_REF]. The remaining ones, that is when there is an axis of symmetry of type node-edge and the odd interval cut by the axis is bigger than the even one, are, in general, not gatherable. As outlined in [START_REF] Klasing | Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring[END_REF], it is very easy to see the impossibility to provide a successful strategy for a a) configuration of 4 robots on a five nodes ring. More complicated, and formally proven in [START_REF] Stefano | About ungatherable configurations of oblivious and asynchronous robots on anonymous rings[END_REF], is the case provided by instances with the described property of 4 robots on a seven nodes ring. In what follows, we refer to all such ungatherable configurations as the set SP 4. Finally, the case of 6 robots with an initial axis of symmetry of type node-edge, or node-node has been solved in [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF].

Besides the cases left open, a unified algorithm that handles all the above cases is also missing. In this paper, we present a new distributed algorithm for solving completely all the gatherable configurations. Our technique introduces a new approach and for some special cases makes use of previous ones. In particular, existing algorithms are used as subroutines for solving the basic gatherable cases with 4 or 6 robots from [START_REF] Koren | Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydzialu ETI Politechniki Gdanskiej[END_REF] and [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF], respectively. Also, we exploit: Property 1.1 [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF] Let C be a symmetric configuration with an odd number of robots, without multiplicities. Let C be the configuration resulting from C by moving the robot on the axis to any of its adjacent nodes. Then C is either asymmetric or still symmetric but aperiodic. Moreover, by repeating this procedure a finite number of times, eventually the configuration becomes asymmetric (with possibly one multiplicity).

For all the other gatherable configurations, we design a new approach that has been suitably unified with the used subroutines. Our result answers to the posed conjectures concerning the gathering, hence closing all the cases left open, and providing a general approach that can be applied for all the initial configurations. The main result of this paper can be stated as follows.

Theorem 1.2 There exists a distributed algorithm for gathering any initial configuration of more than two robots on a ring, provided that it does not belong to the set SP 4, it is aperiodic, it does not admit an edge-edge axis of symmetry.

Definitions and Preliminaries

We consider an n-nodes anonymous ring without orientation. Initially, k nodes of the ring are occupied by k robots. During a Look operation, a robot perceives the relative locations on the ring of multiplicities and single robots. The current configuration of the system can be described in terms of the view of a robot r. We denote a configuration seen by r as a tuple Q(r) = (q 0 , q 1 , . . . , q j ), j ≤ k -1, that represents the sequence of the numbers of free consecutive nodes broken up by robots when traversing the ring in one direction, starting from r. Unless differently specified, we refer to Q(r) as the lexicographical minimum view among the two possibilities. For instance, in the configuration of Fig. 1a, we have that Q(x) = (1, 2, 1, 3, 1, 2). A multiplicity is represented as q i = -1 for some 0 ≤ i ≤ j, regardless the number of robots in the multiplicity. For instance, for any robots in y of Fig. 1b, Q(y) = (-1, 1, 1, 1, -1, 0, 1, 3, 1, 0). Given a generic configuration C = (q 0 , q 1 , . . . , q j ), let C = (q 0 , q j , q j-1 , . . . , q 1 ), and let C i be the configuration obtained by reading C starting from q i , that is C i = (q i , q (i+1) mod j+1 , . . . , q (i+j) mod j+1 ). The above definitions imply:

Inria Property 2.1 Given a configuration C, i) there exists 0 < i ≤ j such that C = C i iff C is periodic; ii) there exists 0 ≤ i ≤ j such that C = (C i ) iff C is symmetric; iii) C is
aperiodic and symmetric iff there exists only one axis of symmetry.

The next definition represents the key feature for our algorithm since it has a twofold advantage. In fact, based on it, a robot can distinguish:

• If the perceived configuration (during the Look phase) is gatherable;

• If it is one of the robots allowed to move (during the Compute phase). Definition 2.1 Given a configuration C = (q 0 , q 1 , . . . , q j ) such that q i ≥ 0, for each 0 ≤ i ≤ j, the view defined as

C SM = min{C i , (C i ), | 0 ≤ i ≤ j} is called the supermin configuration view. An interval is called supermin if it belongs to the set I C = {q i | C i = C SM or (C i ) = C SM , 0 ≤ i ≤ j}.
The next lemma, based on Definition 2.1, is exploited to detect possible symmetry or periodicity features of a configuration: Lemma 2.2 Given a configuration C: Proof Let C = (q 0 , q 1 , . . . , q j ),

1. |I C | = 1 if
1.⇒) If |I C | = 1
, then if C is symmetric, there exists at least an axis of symmetry. This axis must pass through the supermin, as otherwise there exists another interval of the same size of supermin to which the supermin is reflected with respect to the axis. However, the same should hold for every neighboring interval of supermin and so forth. Since by hypothesis, supermin is unique, there must exist at least 2 intervals of different sizes that are reflected by the supposed symmetry, and hence C results asymmetric.

If C is asymmetric then it must be aperiodic, as otherwise there exists 0 < i ≤ j such that C = C i and this implies more than 1 copy of the supermin.

1.⇐) If C is asymmetric and aperiodic, then C i = (C i ), C i = C and C i = (C ), for each i and = i and hence must exist a unique supermin. If C admits only 1 axis of symmetry passing through a supermin, then there exists a unique 0 ≤ i ≤ j such that C SM = C i = (C i ) as, otherwise, by Property 2.1, it would imply the existence of other axes of symmetry, each 1 corresponding to 1 supermin.

2.⇒) If |I C | = 2 and C is asymmetric, then by Property 2.1, it is periodic and the period must be of n 2 . If |I C | = 2 and C is aperiodic and symmetric, the axis of symmetry cannot pass through both the supermins. In fact, if it does, C SM = (C SM ) = (C SM ) j/2 = (C SM ) j/2 that implies (C SM ) j/4 = (C SM ) j/4 , i.e., there exists another symmetry orthogonal to the other 1 that reflects the supermin into the other supermin. Hence, C would be periodic.

2.⇐) If C is aperiodic and symmetric with the unique axis not passing through any supermin then each supermin must be reflected by the axis to another 1. Moreover, there cannot be more than 2 supermins, as by definition of supermin, these would imply other axes of symmetry and hence C would be periodic by Property 2.1. If C is periodic with period n 2 , then any supermin has an exact copy after n 2 intervals, and there cannot be other supermins, as otherwise the period would smaller.

RR n°7963

3.⇒) If |I C | > 2, then there are at least 3 supermins, and this implies a period of at most n 3 for C.

3.⇐) If C is periodic with period at most n 3 , then a supermin is repeated at least 3 times in C.

A first look to the algorithm

The above lemma already provides useful information for a robot when it wakes up. In fact, during the Look operation, it can easily recognize if the configuration contains only 2 robots, or if it belongs to the set SP 4, or if |I C | > 2 (i.e., the configuration is periodic), or in case |I C | = 2, if the configuration admits an edge-edge axis of symmetry or it is again periodic. After this check, a robot knows if the configuration is gatherable, and proceeds with its computations. Indeed, we will show in the next chapter that all the other configurations are gatherable. From now on, we do not consider the above non-gatherable configurations.

The main strategy allows only movements that affect the supermin. In fact, if there is only one supermin, and the configuration allows its reduction, the subsequent configuration would still have only one supermin (the same of before but reduced), or a multiplicity is created. In general, such a strategy would lead asymmetric configurations or also symmetric ones with the axis passing through the supermin to create one multiplicity where the gathering will be easily finalized by collecting at turn the closest robots to the multiplicity.

For gatherable configurations with |I C | = 2, our algorithm requires more phases before creating the final multiplicity where the gathering is realized. In fact, in this case there are two supermins that can be reduced. If both are reduced simultaneously, then the configuration is still symmetric and gatherable. Possibly, it contains two symmetric multiplicities. In fact, this is the status that we want to reach even when only one of the two supermins is reduced. In general, the algorithm tries to preserve the original symmetry or to create a gatherable symmetric configuration from an asymmetric one. It is worth to remark that in all symmetric configurations with an even number of robots, the algorithm always allows the movement of two symmetric robots. Then it may happen that, after one move, the obtained configuration is either symmetric or it is asymmetric with a possible pending move. In fact, if only one robot among the two allowed to move performs its movement, it is possible that its symmetric one either did not start its Look-Compute-Move cycle, or it is taking more time. If there might be a pending move, then the algorithm forces it before any other decision.

In contrast, asymmetric configurations cannot produce pending moves as the algorithm allows the movement of only one robot. In fact, we reduce the unique supermin by deterministically distinguish among the two adjacent robots, until one multiplicity is created. Finally, all the other robots will join the multiplicity one-by-one. In some special cases, from asymmetric configurations at one "allowed" move from symmetry (i.e., with a possible pending move), robots must guess which move would have been realized from the symmetric configuration, and force it in order to avoid unexpected behaviors. By doing this correctly, the algorithm brings the configuration to have two symmetric multiplicities as above, eventually. From here, a new phase that collects all the other robots but two into the multiplicities starts. Still the configuration may move from symmetric configurations to asymmetric ones at one move from symmetry. Once the desired symmetric configuration with two multiplicities and two single robots is reached, a new phase starts and moves the two multiplicities to join each other. The node where the multiplicities join represents the final gathering location.

Resolution algorithm and its correctness

The algorithm works in 5 phases that depend on the configuration perceived by the robots, see Fig. 2. First, it starts from a configuration without multiplicities and performs phase multiplicity-creation whose aim is to create one multiplicity, where all the robots will eventually gather, or two symmetric multiplicities. In the former case, phase convergence is performed to gather all the robots into the multiplicity. In the latter case, phases collect and then multiplicity-convergence are performed in order to first collect almost all the robots into the two multiplicities and then to join the two multiplicities into a single one. After that, phase convergence is performed. Special cases of 7 nodes rings and 6 robots are considered separately in phase seven-nodes.

We can show how robots interchange from one phase to another until the final gathering is achieved. In each phase we can distinguish the type of configuration and provide the algorithm to be performed by robots for each of these types. The way how a robot can identify the type of configuration will be outlined later.

Phase multiplicity-creation

The main idea in this phase is to reduce the supermin by enlarging the largest interval adjacent to it as follows: Definition 3.1 Let Q(r) = (q 0 , q 1 , . . . , q j ) be a supermin configuration view, then robot r performs the reduction if the obtained configuration after its move is (q 0 -1, q 1 , . . . , q j + 1).

The pseudo-code of reduction is given in Fig. 1. The procedure, first checks whether the robot perceives the supermin configuration view by comparing the configuration C perceived by the robot with C SM . Note that, in asymmetric configurations, the robot that perceived C is the one among the two robots at the sides of the supermin allowed to move. In fact, the robot on the other side would perceive the configuration C and, by definition of C SM , we have C SM = C < C, as the configuration is asymmetric. Then, the procedure moves the robot towards the supermin. In symmetric configurations, the test at line 1 returns true for both robots adjacent to the unique supermin or for the two symmetric robots that perceive C SM in case that

|I C | = 2.
It is worth to note that, from a symmetric configuration, always two robots can perform the reduction when it is possible to perform it. If only one of them does it, the obtained configuration will contain exactly one supermin. However, if the perceived configuration contains Procedure: reduction Input : C = (q0, q1, . . . , qj)

1 if C = C SM then move towards q0;
only one supermin and it is not symmetric, the robots are able to understand whether there might be a pending move to re-establish the original symmetry or not. This constitutes one of the main results of the paper and it is obtained from the following lemma. Lemma 3.1 Let C be a configuration with more than 2 single robots and let C be the one obtained from C after a reduction performed by a single robot. Then: If C is asymmetric then C is at least at two moves from a symmetric configuration; if C is symmetric then C is at least at two moves from any other symmetric configuration with an axis of symmetry different from that of C.

Proof By Lemma 2.2, 2 cases may arise: there exists only 1 supermin in C or the configuration is symmetric and contains exactly 2 supermins.

We now show that in the case that there exists only 1 supermin in C, then C is at least 2 moves from any axis of symmetry different from that passing through the supermin. By Lemma 2.2, it is enough to show that C requires more than 1 move to create another supermin different from that of C. Let us consider the supermin configuration view C SM = (q 0 , q 1 , . . . , q j ). For the sake of simplicity, let us assume that, for each i = 1, 2, . . . , j, (C SM ) i < (C SM ) i , the case where, for some i, (C SM ) i > (C SM ) i is similar. The case that (C SM ) i = (C SM ) i cannot occur as, otherwise, there exists an axis of symmetry passing through q i , but, by Lemma 2.2, as |I C | = 1, the possible axis of symmetry can only pass through q 0 . By definition of supermin, for each (C SM ) i , i = 1, 2, . . . , j, there exists k i ∈ {0, 1, . . . , j} such that: q = q (i+ ) mod j+1 , for each < k i ; and q ki < q (i+ki) mod j+1 . Note that (i + k i ) mod j + 1 = 0 as otherwise it contradicts the hypothesis of minimality of q 0 . Moreover, k i = j as otherwise

j =0 q = ki =0 q < ki =0 q (i+ ) mod j+1 = j =0 q (i+ ) mod j+1
, that is a contradiction. From C , the supermin configuration view is C SM = (q 0 , q 1 , . . . , q j ) = (q 0 -1, q 1 , . . . , q j + 1) and we have that, for each i = 1, 2, . . . , j, 2 cases may arise: if k i > 0, then q 0 = q 0 -1 < q i = q i and q ki = q ki < q (i+ki) mod j+1 = q (i+ki) mod j+1 ; if k i = 0, then q 0 = q 0 -1 < q i -1 = q i -1. In any case, C SM differs from (C SM ) i by 2 units. It follows that C is at least 2 moves from any axis of symmetry different from that passing through the supermin. In fact, in order to obtain another axis of symmetry by performing only 1 move on C , (C SM ) i has to differ from C SM by at most 1 unit. This is enough to show the statement for the case of symmetric configurations with exactly 1 supermin. Regarding the asymmetric case, it remains to show that C is at least 2 moves from the axis passing through the supermin. In an asymmetric configuration C SM = (q 0 , q 1 , . . . , q j ) there exists a q k , 1 ≤ k ≤ j 2 , such that q = q (j+1-) mod j+1 , for each < k, and q k < q j+1-k . From C , the supermin configuration view is C SM = (q 0 , q 1 , . . . , q j ) = (q 0 -1, q 1 , . . . , q j + 1) and 2 cases may arise: if k > 1, then q 1 = q 1 = q j < q j + 1 = q j and q k = q k < q j-1-k = q j-1-k ; if k = 1, then q 1 = q 1 < q j = q j -1. It follows that C is at least 2 moves from the axis of symmetry passing through the supermin.

Regarding the case of symmetric configurations with exactly 2 supermins, we use similar arguments as above. Let us consider the supermin configuration view C SM = (q 0 , q 1 , . . . , q j ) and let us assume that h is the index such that C SM = (C SM ) h . By definition, for each (C SM ) i , i ∈ {1, 2, . . . , j} \ {h}, there exists k i ∈ {0, 1, . . . , j} such that: q = q (i+ ) mod j+1 , for each < k i , and q ki < q (i+ki) mod j+1 . As above we are assuming that (C SM ) i < (C SM ) i and we can show Inria that k i = j, k i = (j + h) mod j + 1, (k i + i) mod j + 1 = 0, and (k i + i) mod j + 1 = h. From C , the supermin configuration view is C SM = (q 0 , q 1 , . . . , q j ) = (q 0 -1, q 1 , . . . , q j + 1) we have that, for each i ∈ {1, 2, . . . , j} \ {h} 2 cases may arise: if k i > 0, then q 0 = q 0 -1 < q i = q i and q ki = q ki < q (i+ki) mod j+1 = q (i+ki) mod j+1 ; if k i = 0, then q 0 = q 0 -1 < q i -1 = q i -1. In any case, C SM differs from (C SM ) i by 2 units. Similar arguments to the ones used for the asymmetric case can show that C is at least 2 moves far apart from the axis passing through the supermin.

Procedure: multiplicity-creation Input : CT, C = (q0, q1, . . . , qj) (symmetric(q0, q1, . . . , q k + 1, q k+1 -1, . . . qj) and q k + 1 is odd) or (symmetric(q0, q1, . . . , q k -1, q k+1 + 1, . . . qj) and q k+1 + 1 is odd); It follows that we can derive C from C by enlarging the supermin of C . This equals to reduce the largest adjacent interval (i.e., by performing the reduction backwards) hence deducing the possible original axis of symmetry and then performing the possible pending reduction. Before providing the designed procedures, we need the following definition: Definition 3.2 Given a configuration C = (q 0 , q 1 , . . . , q j ), the view defined as Each time a robot wakes up, it needs to find out which kind of configuration it is perceiving, and, if it is allowed to move, it needs to compute the right move to perform. We need to distinguish among several types of configurations, requiring different strategies and moves. In this phase, as there are no multiplicities, a robot must distinguish among the following configurations: W1 Symmetric configurations with an odd number of robots; W2 Configurations with 4 robots; W3 Configurations with 6 robots; W4 Symmetric configurations with an even number of robots greater than 6, only one supermin of size 0 or with two supermins of size 0 divided by one interval of even size with no other intervals of size 0;

1 case CT =W1 2 if C = Cj then move towards q0; 3 case CT =W2
C SSM = min{C i , (C i ) | C i = C SM and (C i ) = C SM , 0 ≤ i ≤ j} is
W5 Symmetric configurations with an even number of robots greater than 6, only one supermin of size 0 or with two supermins of size 0 divided by one interval of even size, and other intervals of size 0;

W6 Asymmetric configurations with an even number of robots greater than 6 and: a) only one interval of size 0, and it is in between two intervals of equal size b) only two intervals of size 0, with only one in between two intervals of equal size c) only two intervals of size 0, with one even interval in between d) only three intervals of size 0, with only two of them separated by an even interval e) only three consecutive intervals of size 0 f) only four intervals of size 0, with only three of them consecutive;

W7 Remaining gatherable configurations.

From configurations in W1, only the robot on the axis can move in one of the two directions, arbitrarily. After this move either the configuration contains one multiplicity or it belongs to W1 or W7. Configurations in W7 will be described later in this section and the configurations with multiplicities will be described in the next section. Regarding configurations in W1, from Property 1.1, we know that the number of times that the obtained configuration can belong again to W1 after this move is bounded.

When the configuration is in W2 or W3, a modified version of algorithms in [START_REF] Koren | Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydzialu ETI Politechniki Gdanskiej[END_REF] and [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF] are performed, respectively. In particular, both the algorithms are able to manage symmetric configurations and to check whether in an asymmetric configuration there is a possible pending move. If the configuration is not symmetric and there are no pending moves, then reduction is performed. The resulting configuration is still in W2 or W3 or at least one multiplicity is created. From the correctness of algorithms in [START_REF] Koren | Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydzialu ETI Politechniki Gdanskiej[END_REF] and [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF] and from the fact that performing reduction results in reducing the supermin, it follows that eventually at least one multiplicity is created.

When the configuration is in W7 and it is symmetric, then the algorithm performs reduction on two symmetric robots that leads to another symmetric configuration in W7, or to a configuration with at least one multiplicity, or to an asymmetric configuration with a pending move. In this latter case, by Lemma 3.1 the algorithm recognizes that the configuration is at one "allowed" move from symmetry and performs the pending move (even though it was not pending, indeed). When the configuration is asymmetric, again reduction is performed. By performing the described movements, at least one multiplicity is created.

Configurations in W4-W6 correspond to the cases where reduction is not allowed to be performed. In fact, if the configuration is symmetric and there is only one supermin of size 0, then reduction may result in swapping the robots at the borders of the supermin, hence obtaining infinitely many times the same configuration. Similarly, if the configuration is symmetric and there are two symmetric supermins of size 0 divided by one interval of even size, then reduction would produce two multiplicities divided by the interval of even size and we won't be able to join such multiplicities afterwards.

From W4, the algorithm performs xn, hence leading to configurations in W4, W6 or to configurations with one multiplicity on the axis.

From W5, the algorithm performs reduction on the configuration obtained without considering the supermin (that is, it reduces the second supermin, according to Definition 3.2). Note that, as in this case the second supermin has size 0, we obtain at least one multiplicity.

The asymmetric configurations in W6 are either asymmetric starting configurations or are obtained from the symmetric configurations in W4 after performing xn. In this cases, the algorithm checks whether the configuration is obtained after an xn move. This is realized by moving backward the robot closest to the other pole of the axis of symmetry that is assumed to pass through: The supermin in case a); The only interval of size 0 adjacent to two intervals of equal size in case b); The even intervals mentioned in cases c) and d); the only interval of size 0 in between other two intervals of size 0 in cases e) and f). If a backwards xn produces a symmetric configuration, then the symmetric xn is performed, otherwise, reduction is performed and this move creates a multiplicity.

For each configuration type, the algorithm checks whether the robot perceiving the configuration C is allowed to move and eventually, performs the move. This phase of the algorithm is summarized in Fig. 4, and it is realized by means of Procedure multiplicity-creation given in Figure 3. The next lemma states that multiplicity-creation eventually finishes with at least one multiplicity and hence one of the other phases starts. Lemma 3.2 Phase multiplicity-creation terminates with at least one multiplicity after a finite number of moves.

Proof From the description it follows that the graph in Fig. 4 models the execution of phase multiplicity-creation. We now show that all the cycles are traversed a finite number of times. This implies that eventually at least 1 multiplicity is created.

From Property 1.1, and results in [START_REF] Koren | Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydzialu ETI Politechniki Gdanskiej[END_REF], and [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF] follows that the self-loops in W1, W2, and W3, respectively, are traversed a finite number of times.

The self-loop in W7 is traversed by performing reduction or pending_reduction. Each time such moves are performed, the supermin decreases until, after a finite number of moves, it either creates a multiplicity or leads to configurations in W4 or W6. The number of moves is at most 2 times the size of the initial supermin and this is obtained for symmetric configurations with the axis not passing through the supermin.

The self-loop in W4 and the cycle between W4 and W6 are traversed by performing xn. Each time this happens, the interval between the 2 symmetric robots closest to the axis of symmetry (excluding those adjacent to the supermin) is reduced until creating a multiplicity on the axis. The number of moves performed equals the initial size of such an interval.

Phase collect

Before proceeding with the description of this phase, we need to distinguish among the 2 poles of an axis of symmetry in the case that there are 2, 3 or 4 multiplicities. We call one of the poles north, according to the following definition. Definition 3.4 In a symmetric, aperiodic configuration with 2, 3 or 4 multiplicities, if the axis is of type • node-edge, then the north is the middle node of the odd interval crossed by the axis;

• node-node or robot-robot, then let us consider the 2 sub-rings which are crossed by the axis and between 2 symmetric multiplicities. The north is the middle node of the smallest sub-ring, if the 2 sub-rings have different sizes. If the 2 sub-rings have the same size, in case the symmetry is of type robot-robot, then the north is the node occupied by the robot crossed by the axis from which by reading all the configuration 1 obtains the lexicographically smallest string; in case the symmetry is of type node-node, then the north is the middle node of the interval crossed by the axis from which by reading all the configuration 1 obtains the lexicographically largest string.

The other node or edge crossed by the axis is called south.

We assume that in symmetric configurations with multiplicities, a robot reads a configuration starting from the northern interval between the 2 adjacent ones, we also assume that if the robot belongs to a multiplicity the first interval q 0 is equal to -1. For instance, robots x and z of Fig. 1b,read (1,1, -1, 0, 1, 3, 1, 0, -1, 1) and (0, -1, 1, 1, 1, -1, 0, 1, 3, 1), respectively. In asymmetric configurations with multiplicities, we need to recognize the north of a possible symmetric configuration from which the current configuration has been obtained. In case that there is only 1 multiplicity, let us consider the configuration read by a robot in an arbitrary order C = (q 0 , q 1 , . . . , q i , . . . , q j ), where q i = -1. The robot first verifies whether there is another symmetric multiplicity to be created by checking whether the configuration C defined as C = (q 0 , q 1 , . . . , q i-1 -1, 0, . . . , q j ) if q i-1 > q i+1 or C = (q 0 , q 1 , . . . , 0, q i+1 -1, . . . , q j ) if q i-1 < q i+1 is symmetric. In the affirmative case, the robot chooses the proper reading between C and C j according to the minimal between C and C j . Otherwise and in the case that q i-1 = q i+1 , it chooses C if i-1 =0 q ≤ j i+1 q and C j otherwise, i.e. the 1 towards the multiplicity. In case there are 2 multiplicities, we need to define a north node allowing a robot to read the configuration starting from the northern interval among its adjacent ones. To this aim, the robot looks for an interval or a robot which is at the same distance from the 2 multiplicities. If there exists an interval of even size at the same distance from the 2 multiplicities, then the middle edge of such interval is identified as south and the node at distance n 2 from the south is identified as the north. In any other case, we compare the sizes of the 2 sub-rings between the 2 multiplicities. If they are different, we consider the configuration obtained by removing all the single robots adjacent to the multiplicities and the middle robot or the middle node of the middle interval of the smallest sub-ring is identified as the north. If they are equal, the algorithm ensures that there always exists an odd size interval or a robot at the same distance from the 2 multiplicities. Therefore, we lexicographically compare the configurations read by such interval (robot, resp.) with that read from the node at distance n 2 from the middle of this interval (from the robot, resp.) and consider the largest (smallest, resp.) as the north (south, resp.) and the other as south (north, resp.).

Phase collect is performed if one of the next configurations occurs:

Coll-a-1 Asymmetric configurations with more than 6 nodes occupied, 1 multiplicity at more than 1 move from the symmetry passing through the multiplicity and at one move from the symmetry before performing reduction or reducing the second supermin;

Coll-s-2 Symmetric configurations with 2 multiplicities and a) more than 6 nodes occupied; b) 6 nodes occupied and more than 1 single robot at distance grater than 0 from any multiplicity on the northern side; c) 6 nodes occupied and more than 2 single robots at distance grater than 0 from any multiplicity on the southern side;

Coll-a-2 Asymmetric configurations with 2 multiplicities and a) more than 6 nodes occupied; b) 6 nodes occupied and 0, 1 or 3 single robots adjacent to a multiplicity.

When the configuration is in Coll-a-1, then the algorithm leads to a symmetric configuration within 1 move which is necessarily containing 2 multiplicities. In fact, the original configuration was at more than 1 move from the symmetry passing through the multiplicity. After this move, a configuration in Coll-s-2 is obtained. Then, the algorithm generates only configurations in Coll-s-2 or in Coll-a-2.

Inria

Lemma 3.3 Phase collect terminates after a finite number of moves by reaching a symmetric configuration with 6 nodes occupied by 2 multiplicities and 4 single robots, with at least 2 of them neighbors to the multiplicities. If there are at least 2 single robots on the northern side, then 2 of them are neighbors to the multiplicities.

Proof From the above description, it follows that the graph in Figure 5 models the execution of phase collect. We now show that all the cycles are traversed a finite number of times until one of the two configurations in the statement is created.

There are only 2 cycles in the graph: the self-loop in Coll-s-2 and the bidirectional edge between Coll-s-2 and Coll-a-2. Each time that one of these 2 cycles is traversed, either the distance between a multiplicity and a robot or the number of single robots is decreased until 6 nodes are occupied and 4 single robots with at least 2 of them are neighbors to the multiplicities. In fact, if at least 2 of the 4 single robots reside on the northern side, then 2 of them must be neighbors to the multiplicities, as otherwise the configuration would belong to Coll-s-2, and the corresponding move can be performed, hence reducing the distance between single robots and multiplicities.

Phase multiplicity-convergence

Phase multiplicity-convergence is performed if one of the next configurations occurs: Mc-a-1 Asymmetric configurations with more than 7 nodes, five nodes occupied, 1 multiplicity at more than 1 move from the symmetry passing through the multiplicity and at one move from a symmetry allowed by algorithm in [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF].

Mc-s-x
From Mc-s-x, if there are 2 multiplicities, the algorithm moves them towards north if exactly 4 nodes are occupied, or if exactly 6 nodes are occupied with 1 single robot adjacent to the northern side of each multiplicity. If exactly 6 nodes are occupied with 1 single robot adjacent to the southern side of each multiplicity, the algorithm moves towards north the 2 symmetric robots adjacent to the multiplicities, making such robots joining the multiplicities.

This operations may lead to configurations in Mc-s-x (with the northern side reduced), or in Mc-a-x.

The configurations in Mc-s-x with 3 multiplicities or 2 multiplicities and exactly 5 nodes occupied can occur only when the 3 multiplicities are consecutive or there are 3 consecutive Inria nodes occupied with 1 single robot is in the middle of 2 multiplicities. In both cases, the middle robot/multiplicity is crossed by the axis. In these cases, the algorithm moves the 2 external multiplicities towards the middle robot/multiplicity leading to a symmetric configuration with only 1 multiplicity crossed by the axis or to an asymmetric configuration with 2 multiplicities, at one move from the symmetry passing through one of the two multiplicities.

If the configuration is in Mc-s-x and it has 4 multiplicities the algorithm moves the southern multiplicities towards the 2 symmetric northern ones, hence obtaining a configuration still in Mc-s-x with 4 multiplicities (but with less robots to move upwards), or in Mc-s-x with 2 multiplicities (but with a largest southern side), or to an asymmetric configuration in Mc-a-x with 2 or 3 multiplicities.

From Mc-a-x, the algorithm allows only moves towards north that can re-establish the symmetry. Note that, unless the configuration is made of just 6 robots, there will always be at least 2 multiplicities. The case of 6 robots, instead, may lead to a configuration in W3 or in Mc-a-x. The pseudo-code of Procedure multiplicity-convergence is given in Fig. 7.

Procedure: multiplicity-convergence Input : CT, C = (q0, q1, . . . , qj) Proof From the above description, it follows that the graph in Figure 8 models the execution of phase multiplicity-convergence. We have already shown that all the cycles are indeed traversed a finite number of times until a configuration as described in the statement is achieved. In fact, for each described configuration, a set of robots is allowed to move towards north, reducing the northern part, or enlarging the southern part, or decreasing the number of robots that have to move towards north. The only exception is given by the 6 robots case, which however is guaranteed to converge to the desired symmetric configuration by means of the arguments in [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF].

1 case CT =Mc-s-x 2 if q0 = -1

Phase convergence

Phase convergence is performed if one of the next configurations occurs:

Conv-a-s Asymmetric configurations with 1 multiplicity at one xn move from configurations also achievable when gathering from six robots, as described in Figure 9. Formally, the configurations are: (-1, q 1 , q 1 -1, 0, q 4 , q 4 + 2), (-1, q 1 , q 2 , q 1 -2, 0, q 5 ), and (-1, q 1 , q 2 , q 1 -1, 0, q 5 , 0).

Conv-s-1 Symmetric configurations with 1 multiplicity having a number of nodes different from 7 or a number of nodes occupied different from 5;

Conv-a-1 Asymmetric configurations with 1 multiplicity; a) at one xn move from the symmetry passing through the multiplicity and different from the configurations in Conv-a-s; b) at more than 1 move from any symmetry.

In this phase, the idea is to gather all the remaining single robots to the only multiplicity by performing xn. However there might occur some exceptions that must be carefully considered. In fact, whenever the gathering leads to configurations with only 5 nodes occupied, these might be "confused" with configurations in phase multiplicity-convergence obtainable when initially only 6 robots occur. In order to address such occurrences, we better avoid these situations. In particular, the algorithm do not perform an xn move whenever it leads to configurations to 1 move from a symmetric configuration with 2 multiplicities achievable when gathering from 6 robots (shown in Figure 9). These are the configurations in Conv-a-s: in this case we perform another move. That is, we allow again an xn move, but without considering the original robot which was supposed to move. In practice, this equals to move the first robot on the other side of the 1 planned to move with respect to the multiplicity. It is worth to note that the configurations in Conv-a-s are the only ones to take care of. The other 2 possible configurations are shown in Fig. 10. After the xn move, they led to a configuration to 1 move from a symmetric configuration with 2 multiplicities, but, in this case, the algorithm in [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF] would never generate it and then there is no possible misclassification.

It must be observed that the above method applied from Conv-a-s decreases the number of moves required to move the single robots to the only multiplicity. Figure 10: The 2 other special asymmetric configurations. After the moves indicated by the arrows the resulting configuration is at one move from a symmetric configuration with 2 multiplicities, but this symmetric configuration is never generated by the algorithm in [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF].

leads, after a reduction, to a configuration in Coll-a-1. However this may happen only once.

Phase seven-nodes

Phase seven-nodes is performed if one of the next configurations occurs:

7N-2 Configurations with 2 multiplicities on a ring of 7 nodes;

7N-1 Configurations with 1 multiplicity and 5 nodes occupied on a ring of 7 nodes.

All the above configurations can occur only when there are 6 robots on a ring of 7 nodes. In fact, for 7N-2 there cannot be initially more than six robots on a ring of 7 nodes, and no strategy leads to have 2 multiplicities apart from the case of 6 robots. For 7N-1, it may only happen starting from 6 single robots. In these cases, the algorithm for 6 robots from [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF] is used.

Selecting the type of configuration

In this, section we show how to recognize the type of configurations among those described above.

We first show that all the above types are pairwise disjoint and that they cover all the possible configurations achieved by the algorithm. Proof It is easy to see that the configurations in W1-W7 cover all the possible initial configurations, as by hypothesis, any initial configuration has no multiplicities. All the configurations in phases collect, multiplicity-convergence, and convergence are generated by the algorithm. In the description of the phases, it has been shown that from any configuration, the configuration after the performed move is in CTP. Therefore, the statement follows. The asymmetric configuration types with 1 multiplicity are Coll-a-1, Mc-a-1, Conv-a-1, Conv-a-s, and 7N-1. Configurations Mc-a-1, Conv-a-s, and 7N-1 are disjoint with respect to the others as they differ for the number of nodes or the number of nodes occupied. Among them, 7N-1 has a different number of nodes from Mc-a-1 and it differs from Conv-a-s as it is at one move from a symmetry with 2 multiplicities, whereas Conv-a-s needs at least 2 moves to generate a symmetric configuration with 2 multiplicities. For the same reason Mc-a-1 differs from Conv-a-s.

Let CTP = {W 1, W 2, . . ., W 7, Coll-a-1, Coll-a-2, Coll-s-2, Mc-s-x, Mc-a-x, Mc-a-1, Conv-a-s, Conv-a-1, Conv-s-1, 7N -2, 7N -1}
It remains to compare configuration types belonging to Conv-a-1 and to Coll-a-1a and Coll-a-1b (these latter configurations are clearly different). Configurations in Conv-a-1 are at more than 1 move from the symmetry passing through the multiplicity, and this is not the case for configurations in Coll-a-1a. Moreover, they are at one move from a symmetry whereas Coll-a-1b are at more than 1 move from any symmetry.

The asymmetric configuration types with 2 multiplicities are Coll-a-2, Mc-a-a, Mc-a-b, and 7N-2 which are disjoint as they differ for the number of nodes or the number of nodes occupied, or the distance between the single robots and the multiplicities. There is only 1 remaining asymmetric configuration type with 3 multiplicities.

By the proof of the above lemmata, follows that in order to distinguish among the configuration types, it is sufficient to compute, given a configuration C = (q 0 , q 1 , . . . , q j ), the following parameters:

1. number of nodes in the ring, n(C); 2. number of multiplicities, m(C); 3. number of nodes occupied or number of robots in the case without multiplicities, occupied(C);

4. distance between single robots and multiplicities;

5. if C is symmetric;

6. if C belongs to Conv-a-s;

7. if C is at one move from one of the symmetries allowed by the algorithm;

Parameters 1-3 can be computed by formulas n(C) = qi≥0 (q i + 1), m(C) = |{q i = -1, 0 ≤ i ≤ j}|, and occupied(C) = j + 1 -m(C), respectively. The distance between single robots and multiplicities is easily computed by summing the intervals between a single robot and a multiplicity. The symmetry of a configuration is computed by procedure symmetric(C). If C belongs to Conv-a-s can be easily checked by comparing all the intervals of C i and C i , for each i ∈ {0, 1, . . . , j} to the configurations in Conv-a-s. To understand whether C is at one move from a symmetry allowed by the algorithm, it is sufficient to perform such move backwards and checking whether the obtained configuration is symmetric. As an example, to check whether C is at one move from reduction, Procedure check reduction is used.

The complete algorithm

In this section, we show how the above phases interact and how the algorithm can switch from 1 phase to another. We show that starting from any initial configuration among W1-W7, we necessarily end up with configurations in either Conv-a-1 or Conv-s-1 (possibly passing through phases collect and multiplicity-convergence), hence finalizing the gathering.

By Lemmata 3.2-3.5, follows that the interaction between the phases is that given in the graph in Figure 2. In what follows we show how the edges of such graph are traversed.

The starting configuration can only belong to W1-W7. By Lemma 3.2, follows that after a finite number of moves any other phase can be reached. Moreover, once reached a configuration with at least 1 multiplicity, the algorithm never goes back to configurations without multiplicities, Inria but in the case of 6 robots. In this latter case in fact, the configurations can swap between those in W3 and those in Mc-a-1 or in Mc-s-a. However, the number of times that this cycle can be traversed is finite as each time the north interval is reduced, until creating 1 single multiplicity on the final gathering node (that is, when the system moves to convergence).

By Lemma 3.3, follows that phase collect terminates after a finite number of moves in a configuration in phase multiplicity-convergence. In particular, the algorithm can only move from configurations in Coll From [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF], follows that configurations in seven-nodes terminates in configurations in convergence.

Finally, from configurations in convergence, the algorithm terminates the gathering with the only exception of the case where a configuration in Conv-a-b can lead, after a reduction, to a configuration in Coll-a-1. Note that this case can occur only when there are more than 6 nodes occupied. As the transition from phase multiplicity-convergence to phase convergence can occur only when there are at most 6 nodes occupied, it follows that the edge between convergence and collect can be traversed only once.

Conclusion

Our distributed algorithm answers to the posed conjectures concerning the gathering on the studied model by providing a complete characterization for gatherable configurations. The obtained result is of main interest for robot-based computing systems. In fact, it closes all the cases left open while providing new analytical approaches. Our technique, mostly based on the supermin concept, provides a powerful mean for investigating related distributed problems. Moreover, the concept of supermin combined with the reduction move can be used to solve other problems in the Look-Compute-Move model.

Figure 1 :

 1 Figure 1: a) The intervals between robots y, z and y , z are the supermins, while the supermin configuration view is (1, 2, 1, 2, 1, 3). b) Black nodes represent multiplicities.

Figure 2 :

 2 Figure 2: Phases interchanges.

4 8 if

 8 if gather-four-nodes(C) then reduction (C);5 case CT =W3 6 if gather-six-nodes(C) then reduction (C);7 case CT =W4 Cj = Cj and qj is odd then move towards qj; 9 if C = C and q0 is odd then move towards q0; 10 case CT =W5 11 if C = C SSM then move towards q0; 12 case CT =W6 13 Let k the index such that

14

 14

15 if k = 0

 150 or k = j then move towards q k ; 16 if no such k exists then reduction (C);

Figure 3 :

 3 Figure 3: Procedure multiplicity-creation.

Definition 3 . 3 1 •

 331 called the second supermin configuration view.Procedure: pending reduction Input : C = (q0, q1, . . . , qj)1 (b, Ĉ) = check_reduction (C) ;2 if b and ( min{ Ĉ, Ĉj} = ĈSM or min{ Ĉ, Ĉj} = ĈSSM ) and min{C, Cj} = C SM then move towards q0; Let C be a configuration:• If C is symmetric and there are no multiplicities, xn corresponds to move towards the axis the two symmetric robots closest to the axis of symmetry that are divided by at most one robot and are not adjacent to a supermin; If C is symmetric and there is only one multiplicity, xn corresponds to move towards the multiplicity the two symmetric robots closest to the multiplicity;• If C is asymmetric and it has been possibly obtained by applying xn from a symmetric configuration C (that is, from C only one of the two robots on the above cases has moved), then xn on C corresponds to move the second closest robot towards the axis/multiplicity;• If C is asymmetric with a multiplicity and it cannot be obtained by applying xn from a symmetric configuration, then xn corresponds to move the robot lexicographically closest to the multiplicity towards it.

Inria

Figure 4 :

 4 Figure 4: Phase multiplicity-creation.

  Symmetric configurations with a) 2 multiplicities with more than 7 nodes and exactly 4 nodes occupied, b) 2 multiplicities and 6 nodes occupied with at least 1 single robot adjacent to each multiplicity; c) 3 multiplicities or 2 multiplicities and exactly 5 nodes occupied; d) 4 multiplicities; Mc-a-x Asymmetric configurations with a) 2 multiplicities, more than 7 nodes and less than 6 nodes occupied; b) 2 multiplicities, 6 nodes occupied and at most 2 robots at distance grater than 0 from the multiplicities; c) 3 multiplicities;

3 move towards q0 4 else 5 if 6 move towards q0 7 else 8 if 9 move towards q0 10 else 11 if

 34567891011 and occupied(C) = 4 and |{qi = -1, 0 ≤ i ≤ j}| = 2 then q0 = -1 and C = C and (|{qi = -1, 0 ≤ i ≤ j}| = 3 or (occupied(C) = 5 and |{qi = -1, 0 ≤ i ≤ j}| = 2)) then q0 = -1 and |{qi = -1, 0 ≤ i ≤ j}| = 4 and q1 = -1 then (q0 = 0 and q1 = -1) or (q0 = -1 and q1 = 0) then 12 move towards q0 13 case CT =Mc-a-x 14 if occupied(C) < 6 and q i ≥0 (qi + 1) > 7 and |{qi = -1, 0 ≤ i ≤ j}| = 2 then 15 if occupied(C) = 5 and ((q0 = 0 and q1 = -1) or (q0 = -1 and q1 = 0)) then 16 move towards q0 17 if occupied(C) = 4 and q0 = -1 and symmetric((-1, q1 + 1, -1, q3 -1, q4, q5)) then 18 move towards q0 19 else 20 if |{qi = -1, 0 ≤ i ≤ j}| = 3 and q0 = -1 and q1 = -1 then 21 move towards q0 22 else 23 if (q0 = 0 and q1 = -1) or (q0 = -1 and q1 = 0) then 24 move towards q0 25 case CT =Mc-a-1 26 gather-six-nodes(C)

Figure 7 :Lemma 3 . 4

 734 Figure 7: Procedure multiplicity-convergence.

Figure 8 :

 8 Figure 8: Phase multiplicity-convergence.

Figure 9 :

 9 Figure9: The 3 special types of configurations. A white circle represents an empty node, a grey 1 a node with a robot, and a black 1 a multiplicity. A dashed arc indicates an arbitrary sequence of empty nodes, a plain arc 2 consecutive nodes. If during the convergence phase a robot should move towards the multiplicity, as indicated by the arrow, then the resulting configuration is at one move from a symmetric configuration with 2 multiplicities achievable when gathering from six robots. The symmetric configurations arise when, in each shown configuration, the 2 adjacent robots join into a multiplicity.

Corollary 3 . 6

 36 be the set of all the possible configuration types above. Configurations in CTP covers all the possible configurations achieved by the algorithm.

Lemma 3 . 7

 37 Configuration types in CTP are pairwise disjoint.Proof We compare only the configuration types with the same number of multiplicities and degree of symmetry. The only configuration types with no multiplicities are W1-W7 and they are clearly pairwise disjoint. The symmetric configuration types with 1 multiplicity are Conv-s-1 and 7N-1 which are disjoint as they differ for the number of nodes or the number of nodes occupied. The symmetric configuration types with 2 multiplicities are Coll-s-2,Mc-s-a, Mc-s-b, Mc-s-c, and 7N-2 which are disjoint as they differ for the number of nodes or the number of nodes occupied, or the distance between the single robots and the multiplicities. The remaining symmetric configuration types have 3 or 4 multiplicities.

  -a-1, Coll-s-2-b, Coll-s-2-c and Coll-a-2-b, to configurations in Mc-s-b. By Lemma 3.4, follows that multiplicity-convergence terminates after a finite number of moves in a configuration in phase convergence. In particular, the algorithm can only move from configurations in Mc-s-a, Mc-s-c, Mc-a-a, and Mc-a-1, to configurations in Conv-s-and Conv-a-a.

  and only if C is either asymmetric and aperiodic or it admits only one axis of symmetry passing through the supermin; 2. |I C | = 2 if and only if C is either aperiodic and symmetric with the axis not passing through any supermin or it is periodic with period n 2 ; 3. |I C | > 2 if and only if C is periodic, with period at most n 3 .

RR n°7963

By Lemma

2.2, in gatherable configurations, the axis of symmetry cannot pass through two supermins hence there are always two robots allowed to move.RR n°7963

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

Function: symmetric Input : C = (q0, q1, . . . , qj) Output : true if C is symmetric, false otherwise 1 for i = 0, 1, . . . , j do 2 if q (k-1) mod j+1 > q (k+1) mod j+1 then 3 Ĉ := (q0, q1, . . . , q (k-1) mod j+1 -1, q k + 1, . . . , qj);

4 else 5 if q (k-1) mod j+1 < q (k+1) mod j+1 then 6 Ĉ := (q0, q1, . . . , q k + 1, q (k+1) mod j+1 -1, . . . , qj); As shown above, Procedure symmetric checks whether a configuration C is symmetric by exploiting Property 2.1. Procedure check_reduction checks whether an asymmetric configuration C has been obtained from some symmetric configuration Ĉ by performing reduction. Procedure pending_reduction performs the pending reduction.

At line 1, Procedure check_reduction looks for the index k such that q k is the supermin, as it is the only candidate for being the interval that has been reduced by a possible reduction. Then, at lines 2-6, it computes the configuration Ĉ before the possible reduction. This is done by enlarging q k and reducing the largest interval among q (k-1) mod j+1 and q (k+1) mod j+1 . If q (k-1) mod j+1 = q (k+1) mod j+1 or Ĉ is not symmetric, then C has not been obtained by performing a reduction from a symmetric configuration. In this case, the procedure returns (false, ∅).If Ĉ is symmetric, then C has been obtained by performing reduction on Ĉ and hence the procedure returns (true, Ĉ).

Procedure pending_reduction uses check_reduction to check whether C has been obtained by performing reduction on a configuration Ĉ (lines 1 and 2). At line 2 the procedure checks whether the robot is at a side of one of the two supermins of Ĉ (min{ Ĉ, Ĉj } = ĈSM ) and if it has not yet performed reduction (min{C, C j } = C SM ). In the affirmative case, the robot has to move towards the supermin (line 2). The robot moves towards q 0 also if it is at the side of the second supermin of Ĉ (min{ Ĉ, Ĉj } = ĈSSM ). This corresponds to a move different from reduction that will be explained later in this section.

In general it is not always possible to perform reduction. In fact, there are cases where it may lead to not gatherable configurations. These cases will be managed separately. However, we will show that a robot is always able to understand that there might be a pending move also for the other moves allowed by our algorithm from symmetric configurations.

When it is not possible to perform reduction, we either reduce the second supermin or we perform the xn move that is defined in the following: When the configuration is in Coll-s-2 we need to distinguish among the types of symmetry. In node-node and node-edge symmetries, we consider the 2 symmetric robots which are the closest to the multiplicities among those in the nodes between the multiplicities and the north. The algorithm moves this 2 robots symmetrically (generating again configurations in Coll-s-2 or in Coll-a-2 if the symmetric robots move synchronously or not, respectively) until they join the 2 multiplicities. This operation is iteratively performed by all the robots between the multiplicities and the north. The last 2 robots are allowed to join the multiplicities only if there are more than 6 nodes occupied. Otherwise, these 2 robots are moved until they become neighbors of the multiplicities. Then, the robots between the multiplicities and the south, except for the 2 southern symmetric robots, perform the same operation in turn, starting by the 2 symmetric robots closest to the multiplicities.

In robot-robot symmetric configurations, the behavior is similar but it is realized by first collecting the robots on the south and then those on the north, apart from the robots on the axis. In both cases, the algorithm eventually leads to a symmetric configuration with six nodes occupied by 2 multiplicities and 4 single robots, with at least 2 of them neighbors to the multiplicities. If there are at least 2 single robots on the northern side, then 2 of them are neighbors to the multiplicities. The pseudo-code of procedure collect is given in Fig. 6. The next lemma shows that this phase eventually terminates in the described symmetric configuration.

RR n°7963

From Conv-s-1, the algorithm allows by an xn move the 2 closest single robots to the multiplicity (or the only remaining 1) to move towards the multiplicity. If both make synchronously the move, then the obtained configuration is still in Conv-s-1, but with 1 move less before the final gathering. If only 1 robot performs the allowed move, then the configuration is in Conv-a-1. From Conv-a-1a, either there is only 1 single robot left, which will be the only 1 allowed to move towards the multiplicity until the gathering is completed, or there are at least 2 single robots, each of which has no other robots in between itself and the multiplicity. If the farthest among those 2 robots re-build the symmetry by 1 move towards the multiplicity, then it will be the only 1 allowed to move and the obtained configuration is in Conv-s-1, otherwise the other single robot is the only 1 allowed to move towards the multiplicity and the obtained configuration might either remain in Conv-a-1 or move to Conv-s-1. Also from Conv-a-1b, the xn move is performed.

In any case, the property that less moves remain is preserved until the final gathering. The pseudo-code of Procedure convergence is given in Fig. 11.

Procedure: convergence Input : CT, C = (q0, q1, . . . , qj) Proof From the above description, it follows that the graph in Figure 12 models the execution of phase convergence. We have already shown that all the cycles are indeed traversed a finite number of times until the gathering is completed. In fact, for each described configuration, 1 or 2 robots are allowed to move towards the multiplicity, reducing the number of moves necessary for each single robot to reach the multiplicity. Eventually the gathering is necessarily accomplished. The only exception occurs when a configuration in Conv-a-b with more than 6 nodes occupied