Moustafa Zerarka

Patrick Austin

Frédéric Morancho

Karine Isoird

Houssam Arbess

Josiane Tasselli

Analysis study of sensitive volume and triggering criteria of SEB in super-junction MOSFETs

Keywords: Power MOSFET, Super-Junction MOSFET, SEB, sensitive volume, SOA, TCAD simulations, triggering criteria

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

Introduction

Power MOSFET is a very important device in many power-electronics applications, widely used in space and atmospheric applications.Its reliability is limited by the effect of natural radiation environment (NRE). This environment is composed of particles of various nature and energy such as heavy ions which can cause the destruction of this device. In order to protect against NRE effects, many studies have been carried out to understand the failure modes. Single Event Burnout (SEB) is one of the catastrophic effects which could cause power devices failure in space systems. Heavy-ions induced destructive failures in power MOSFETs have been extensively studied and are related to the existence of a parasitic bipolar junction transistor (BJT) inherent to the device [START_REF] Keshavarz | Computer Simulations of Ionizing Radiation Burnout in Power MOSFETs[END_REF][START_REF] Roubaud | Experimental and 2D simulation Study of the Single Event Burnout[END_REF]. In IGBTs, destructive electrical failures have already been observed [START_REF] Iwamuro | Numerical Analysis of Short-circuit Safe Operating Area for P-channel and N-channel IGBTs[END_REF], and those induced by heavy ions were observed in 1992 and 1993 by Rockwell and Boeing Company [START_REF] Nichols | Observations of Single Event Failure in Power MOSFETs[END_REF]. The first adopted triggering criterion was only a critical LET (Linear Energy Transfer) before the influence of the ion penetration depth was investigated. Experimental observation of SEB in high voltage devices MOSFET and IGBT was reported in [START_REF] Lorfevre | Heavy ion induced failures in a power IGBT[END_REF], demonstrating that avalanche conditions are not needed to trigger the IGBT, a heavy ion being able to induce latchup contrarily to power MOSFETs. SEGR (Single Event Gate Rupture) and SEB testing have been carried out by P.T. McDonald et al [START_REF] Mcdonald | Destructive heavy ion SEE investigation of 3 IGBT devices[END_REF] on three types of commercial 600-1200V planar IGBTs. They found that they are all sensitive to SEB and SEGR but measurements at a reduced V CE value, from 330V to 270V indicated a significant reduction in both measured SEB/SEGR sensitivity allowing to use them in space applications.

Currently, the trend is to use rather long ranges, able to cross the epitaxial layer of the classic VDMOS planartype. S. Liu, however, investigated the range effect on both SEB and SEGR phenomena [START_REF] Liu | Recommended test conditions for SEB evaluation of planar power DMOSFETs[END_REF] and recommends the use of light, short-range ions, not to be confused with the appearance of SEGR during SEB tests. The test results carried out on 600 V prototypes show no significant effect of the range on the SEB safe operating area (SOA) (for ranges from 30 to 300 μm). , together with Marec et al. in [START_REF] Marec | Methodology to predict the SEE rate in vertical MOSFET with deep charge collection[END_REF] which suggest that the criteria is a critical deposited charge in the epitaxy, the latter defining also the sensitive volume. On the other hand, A. Luu et al. in [START_REF] Luu | Sensitive Volume and Triggering Criteria of SEB in Classic Planar VDMOS[END_REF] show an influence of the ion range in commercial MOSFETs; they define the epitaxial layer as the sensitive volume.We also have reported on the effect of the ion range on 400V-IGBTs [START_REF] Zerarka | Comparative study of sensitive volume and triggering criteria of SEB in 600 V planar and trench IGBTs[END_REF]. Few works are related to SJ-MOSFET. Huang et al showed that the presence of the horizontal electric field and the smaller vertical electric field in the SJ-device reduce its vulnerability to SEB and SEGR significantly compared to the standard power MOSFET [START_REF] Huang | Analysis of SEB and SEGR in Super-Junction MOSFETs[END_REF]. N.Ikeda et al showed experimentally that there was not much difference in SEB tolerance between the two. However, SJ-MOSFET could have better SEB tolerance by decreasing the die size while maintaining low on-resistance and applying the hardening technique for the standard power MOSFET structure [START_REF] Ikeda | Single-Event Burnout of Super-Junction Power MOSFETs[END_REF].

In this context, using 2D Synopsis TCAD tools, a simulation work has been conducted to define the sensitive volume and the criteria for SEB triggering induced by heavy ions in standard MOSFET and SJ-MOSFET devices. The first part of this paper presents the 2D simulation results for the definition of the sensitive volume defined by the minimum LET triggering a SEB, according to the range and depth of ion generation. The analysis of these results also allows comparing the electric behaviour of these cells for different configurations of ionizing tracks. In the second section, the drain voltage has been varied for different ranges in order to define the SOA of these devices. Finally, the broad range of temperatures that may occur on a board system necessitates an investigation of the temperature dependence of the SEB mechanism in each component.

Simulation tool and test vehicle

Simulations were carried out with 2D Sentaurus simulator using the heavy-ion model. The physics models used are:

 Mobility models: Electrical field, doping and carrier-carrier scattering effects.

 Generation /Recombination models: Auger generation and recombination, SRH and Impact Ionization models.

 Electronic Band structures: Band gap narrowing effects, Intrinsic density and Fermi stats.

Structures under study are standard MOSFET (VDMOS) and SJ-MOSFET power devices as shown in Figure 1: they are based on a flexible technology developed at LAAS laboratory and are rated for a breakdown voltage of 700~800 V. Figure 1 shows a cross-section of the half-cell structures.

Conditions of simulations

Throughout these simulations, all ionization traces are only generated in the intercellular region right next to the channel. This position is the most sensitive as shown in previous works [START_REF] Lorfevre | Heavy ion induced failures in a power IGBT[END_REF][START_REF] Mcdonald | Destructive heavy ion SEE investigation of 3 IGBT devices[END_REF][START_REF] Liu | Recommended test conditions for SEB evaluation of planar power DMOSFETs[END_REF]. In a first step, we studied the case of ions generated vertically in the volume of the half-cell of standard and SJ MOSFETs with track lengths of 10 μm generated from different depths within the epitaxial region (see Fig 2.a). The objective is to locate the sensitive volume.

In a second step, we simulated the impact of ions penetrating from the front side with different track lengths (see Fig 2.b). The aim is to see from which value of LET SEB triggering is initiated for each range and how each component behaves for different values of range. Initially, for easier comparison of the results, all simulations are performed at the same drain polarization of 400 V in blocking state. The horizontal x-position of the generation is the one defined in the first step simulation (range is the word used in this type of studies to indicate the track length).

In a third step, we simulated these structures with different drain voltages (100 V, 200 V, 300 V and 400 V) for various ranges (10 μm, 30 μm and 60 μm) while keeping the same conditions defined in the preceding second step simulation.

Finally, the temperature dependence of the model is taken into account to simulate the structures with a temperature rise from 300 K to 400 K.

Sentaurus-TCAD simulation results and discussion

Determination of the Sensitive Volume in each device

Considering a track length of 10 μm separately, for a 400 V bias, the space charge region expands across less than 50 μm. Figure 3 clearly shows that the tracks located inside this area require lower values of LET and they vary relatively little between each depth. Outside the space charge region, the tracks require a much larger LET since only one type of carrier, holes, is at the origin of the impact multiplication phenomena within the electric field zone. Moreover, the charges located outside the depletion region need more time to recombine before reaching the electric field region. As a result, there are likely fewer holes and electrons available to begin the impact ionization cascade.

One can see, from the analysis of these results, that the most efficient way to trigger a SEB in standard MOSFET is to deposit a quantity of charges into the space charge region. In the SJ-MOSFET the sensitive volume is located in the top half of the epitaxial region. In this case, the electric field is distributed homogeneously along the vertical PN junction, and the sensitive volume can be independent of its effect. We remind that electrons and holes are collected at drain and source contacts respectively. Generally, in order for the carrier density to be multiplied by the impact ionization mechanism, carriers need to cover a certain distance to acquire the required energy for creating an electron-hole pair [START_REF] Kuboyama | Improved model for single-event burnout mechanism[END_REF]. The more carriers travel in the space charge region, the more they are multiplied. Moreover, in SJ-MOSFET all carriers are at the origin of the impact multiplication phenomena in crossing the space charge region. But the tracks positioned in the bottom half of the epitaxial region require a much larger LET since the holes generated in this depth have more time to recombine before reaching the ground via the lateral pbase region. systematically deposited minimum charges triggering a SEB are systematically deposited within the space charge region which explains the saturation of LET in standard MOSFET. This is not the case for the SJ-MOSFET wherein there is no saturation of LET since the space charge region expands completely into the structure. However in SJ-MOSFET, values of minimum LET vary relatively little between each range excepted for the 10µm-range. Therefore, the range has a little effect in SJ-MOSFET compared with the standard one. The track range influence on the SEB phenomenon can be explained by the following. The SEB mechanism is linked to the avalanche one and the forward biasing of Fig. 3. Minimum LET triggering a SEB of the ion coming from the front side in normal incidence generated from different depths in the epitaxial region with (range=10 μm, Vds=400 V) for planar (top) and SJ (bottom) MOSFETs Figure 4 shows the minimum LET triggering a SEB as a function of the ion range for both components. The simulations show that the LET required for SEB initiation decreases with increasing ion range in the Nepitaxial region. A minimum LET saturation exists for 50 μm in planar MOSFET and 80 μm in SJ-MOSFET.

These ranges correspond to the depth of the space charge region which width is 50 μm and 80 μm, respectively, at 400 V for both cells. An important range allows the generation of carriers by avalanche in the space charge region and therefore requires a low LET. Conversely, a small range requires a large LET since the path of charges deposited in the space charge region is lower and there is less generation by the avalanche phenomenon. Therefore, the sensitive case of SEB triggering is when the ion penetrates a great part of the space charge region. A minimum charge exists for ranges lower than 50 μm in planar MOSFET, 20 μm and 80 μm in SJ-MOSFET. It is clear that with the same LET whatever the increase in range, minimum charges triggering a SEB are systematically Fig. 4. Minimum LET and quantity of charges triggering a SEB depending on the penetration depth of the ion coming from the front side in normal incidence (Vds=400 V) for planar (top) and SJ (bottom) MOSFETs

The track range influence on the SEB phenomenon can be explained by the following. The SEB mechanism is linked to the avalanche one and the forward biasing of the parasitic bipolar transistor which provides charges to each other. For the SEB phenomenon to become irreversible, the avalanche and conduction mechanisms of the bipolar transistor must be maintained so that the avalanche has to be fed by the electron current provided by the bipolar transistor and the parasitic transistor has to be fed by the hole current coming from the avalanche mechanism. Figure 5 illustrates a systematic observation of the electric field in the simulated structures following a burnout showing that the electric field is always maximum at the P + body/ N -drift junction at the end of the simulation, whatever the range in the standard MOSFET. This is due to the highly localized current in the right side of each structure i.e. most of the current flows through the inherent parasitic npn transistor (n + cathode/p -body/ n -drift). The electric field is also maximum at the homo-junction (n -drift/n + substrate) at the end of the simulation, whatever the range in the planar and SJ-MOSFETs. This electric field allows the establishment of a strong avalanche rate since the ionization coefficients are exponentially related to the electric field. The currents thus generated lead to thermal runaway and burnout [START_REF] Luu | Sensitive Volume and Triggering Criteria of SEB in Classic Planar VDMOS[END_REF].

The displacement of the electric field peak and its increase at the junction in each case as shown in Figure 5 are due to the Kirk effect [START_REF] Hohl | Feature of the triggering mechanism for single event burnout of power MOSFETs[END_REF][START_REF] Johnson | A review of the techniques used for modeling single event effects in power MOSFETs[END_REF] and the build-up of a negative space charge region. Thus, a track with high range will be more susceptible to the Kirk effect for the establishment of a current than a limited and localized charge deposition. Observations show also that in the case of low range, the electric field peak moves from P - body junction to the substrate junction. However, this does not extend to the case of high range hence the maximum reached by the electric field at the ndrift/substrate junction appears from the outset. This explains the rapidity of SEB triggering in the case of high range after each first current peak, the low range taking more time after this latter. Fig. 5. Evolution of the electric field following a vertical ionizing impact with a big range (left) and small range (right) in each half cell biased at 400 V.

Results analysis for different drain-source biases

Figure 6 presents the simulation results for different drain-source biases (100 V, 200 V, 300 V and 400 V) and for three ranges (10 µm, 30 µm and 60 µm). In these cases, the space charge region proportionally extends to each bias. It is clear that the threshold LET decreases accordingly with the bias increase in the standard MOSFET. On the other hand, the minimum LET triggering a SEB is fixed whatever the bias voltage value for the SJ-MOSFET. Some of the observations previously made are confirmed: LET decreases with the range increase whatever the bias voltage value. However, increasing the bias voltage proportionally extends the space charge region within the cell that reduces the existing differences of LET between the various ranges in the case of standard MOSFET. However for the SJ-MOSFET, the differences of LET between the various ranges is the same regardless of the bias voltage since a we said previously, the electric field is distributed homogeneously along the vertical PN junction and the space charge region expands completely in the cell.

There is no important difference in the SEB threshold voltage as shown in figure 6. The SJ-MOSFET has a same SOA than the standard one that is consistent with the fact that these structures have the same parameters such as "Rp", the resistance of the P-well under the source which is the crucial factor for increasing the SEB threshold voltage. Figure 7 summarizes the sensitivity variation for the two structures for an ion penetrating 70 µm into the epitaxial region. The sensitivity evolution depends on the bias voltage applied:

-Under a low bias voltage (<400 V), SJ-MOSFET is more sensitive than the standard one; -At 400 V, the sensitivity is similar for of both devices;

-Under high bias voltage (>400V), the standard MOSFET is more sensitive than the SJ-MOSFET.

This may be the reason why S. Huang et al. In [START_REF] Huang | Analysis of SEB and SEGR in Super-Junction MOSFETs[END_REF] found that the SJ-MOSFET is less vulnerable to the SEB compared to the standard one. But on the other side N. Ikeda et al [START_REF] Ikeda | Single-Event Burnout of Super-Junction Power MOSFETs[END_REF] demonstrated that there was no structural advantage in SEB tolerance for the SJ-MOSFET and there was not much difference in SEB tolerance between the two technologies.

Results Analysis for different temperature value

Figure 8 clearly shows that the minimum LET required to generate a SEB decreases as the temperature increases. This is to say, the most critical case found at low temperature which is consistent with previous works [START_REF] Johnson | Temperature dependence of single-event burnout in NChannel Power MOSFETs[END_REF]. For the standard and SJ MOSFETs, the impact ionization rate (number of electron-hole pairs generated per unit path length) decreases with increasing temperature [START_REF] Crowell | Temperature Dependence of Avalanche Multiplication in Semiconductors[END_REF]. This is attributed to the shorter mean free path of the carriers. Since the impact ionization rate is used explicitly in the solution to the Poisson equation, the avalanche generated hole current density decreases with increasing temperature for the same injected electron current density and applied drain-source bias.

Conclusion

The sensitive volume of standard and SJ MOSFETs has been defined by delimiting the depth and thickness of this volume using 2D electrical simulations. The most critical case for triggering a SEB at 400V in standard MOSFET is related to an ion crossing the entire space charge region. However for SJ-MOSFET, the range has a little effect compared with the standard one. SOA is the same for the two studied devices, but there is a significant difference of behaviour and sensitivity depending on the applied bias voltage. This can be an advantage for the SJ-MOSFET SEB tolerance only at high voltage.

Fig 1 .

 1 Fig 1. Standard and SJ MOSFETs half cell layout.

Fig 2 .

 2 Fig 2. Schematic of ionizing tracks impacting on normal incidence on the device front side

Fig. 6 .Fig. 7 .

 67 Fig. 6. Minimum LET triggering a SEB at different Vds and various ranges for the ion coming from the front side in normal incidence for standard (top) and SJ (bottom) MOSFETs

Fig. 8 .

 8 Fig. 8. Comparison of the sensitivity at different temperature value (minimum LET (T)/LET (T°)) with ion range=70µm

Acknowledgements

This work has been sponsored by Fondation de Recherche pour l'Aéronautique et l'Espace (http://www.fnrae.org/) within the framework of EPOPE project.


S Devismes

A Lamani

F Petit

S Tixeuil

Optimal Torus Exploration by Oblivious Mobile Robots

Keywords: Robot, Torus, Exploration, Obliviousness

We consider autonomous robots that are endowed with motion actuators and visibility sensors. The robots we consider are weak, i.e., they are anonymous, uniform, unable to explicitly communicate, and oblivious (they do not remember any of their past actions). In this paper, we propose an optimal (w.r.t. the number of robots) solution for the terminating exploration of a torus-shaped network by a team of k such robots. In more details, we first show that it is impossible to explore a simple torus of arbitrary size with (strictly) less than four robots, even if the algorithm is probabilistic. If the algorithm is required to be deterministic, four robots are also insufficient. This negative result implies that the only way to obtain an optimal algorithm (w.r.t. the number of robots participating to the algorithm) is to make use of probabilities. Then, we propose a probabilistic algorithm that uses four robots to explore all simple tori of size ℓ × L, where 7 ≤ ℓ ≤ L. Hence, in such tori, four robots are necessary and sufficient to solve the (probabilistic) terminating exploration. As a torus can be seen as a 2-dimensional ring, our result shows, perhaps surprisingly, that increasing the number of possible symmetries in the network (due to increasing dimensions) does not come at an extra cost w.r.t. the number of robots that are necessary to solve the problem.

Introduction

We consider autonomous robots that are endowed with motion actuators and visibility sensors, but that are otherwise unable to communicate. They evolve in a discrete environment, where the space is partitioned into a finite number of locations, conveniently represented by a graph, where the nodes represent the possible locations that a robot can take and the edges the possibility for a robot to move from one location to another. Those robots must collaborate to solve a collective task despite being limited with respect to inputs from the environment, asymmetry, memory, etc. In particular, the robots we consider are anonymous, uniform, yet they can sense their environment and take decisions according to their own ego-centered view. In addition, they are oblivious, i.e., they do not remember their past actions. The three execution models are denoted (using recent taxonomy [START_REF] Flocchini | Distributed Computing by Oblivious Mobile Robots[END_REF]) FSYNC, for fully synchronous, SSYNC, for semi-synchronous, and ASYNC, for asynchronous. In the ASYNC model, robots execute their phases in a completely independent manner. In the SSYNC model an arbitrary non-empty subset of robots execute the three phases synchronously and atomically. In the FSYNC model all robots execute the three phases synchronously.

In this context, typical problems are terminating exploration [START_REF] Chalopin | Network exploration by silent and oblivious robots[END_REF][START_REF] Devismes | Optimal grid exploration by asynchronous oblivious robots[END_REF][START_REF] Devismes | Optimal probabilistic ring exploration by semi-synchronous oblivious robots[END_REF][START_REF] Flocchini | Remembering without memory: Tree exploration by asynchronous oblivious robots[END_REF][START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF], exclusive perpetual exploration [START_REF] Baldoni | Anonymous graph exploration without collision by mobile robots[END_REF][START_REF] Baldoni | On the solvability of anonymous partial grids exploration by mobile robots[END_REF][START_REF] Gianlorenzo | A unified approach for different tasks on rings in robot-based computing systems[END_REF], exclusive searching [START_REF] Gianlorenzo | Gathering and exclusive searching on rings under minimal assumptions[END_REF][START_REF] Gianlorenzo | A unified approach for different tasks on rings in robot-based computing systems[END_REF], and gathering [START_REF] Gianlorenzo | A unified approach for different tasks on rings in robot-based computing systems[END_REF][START_REF] Haba | On gathering problem in a ring for 2n autonomous mobile robots[END_REF][START_REF] Klasing | Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring[END_REF]. Here, we study the terminating exploration (or simply exploration) problem, which requires that robots collectively explore the whole graph and stop upon completion. We focus on the case when the network is an anonymous unoriented torus. Since 1 the robots are unable to communicate explicitly and have no persistent memory, they are unable to remember the various steps taken before. Therefore, the positions of the other robots are the only way to distinguish the different stages of the exploration process. The main complexity measure is then the minimum number of robots that are required to achieve exploration. Since numerous symmetric configurations induce a large number of required robots, minimizing the number of robots turns out to be a difficult problem.

Related Work. With respect to the (terminating) exploration problem, minimizing the number of robots for exploring particular classes of graphs led to contrasted results. The only result available for exploration in general graphs [START_REF] Chalopin | Network exploration by silent and oblivious robots[END_REF] considers that edges are labeled in such a way that the network configuration (made of the topology, the edge labeling, and the robot positions) is asymmetric. In this extended model, three robots are not sufficient to explore all asymmetric configurations, and four robots are sufficient to explore all asymmetric configurations. Note that exploring the set of asymmetric configurations is strictly weaker than exploring the complete underlying graph, especially when the graph is highly symmetric. The rest of the literature is thus dedicated to a weaker model, where edges are not labeled (or equivalently, the labeling is decided by an adversary anytime a robot is activated). One extreme case in this weak model is the set of tree-shaped networks, as in general, Ω(n) robots are necessary and sufficient to explore a tree network of n nodes deterministically [START_REF] Flocchini | Remembering without memory: Tree exploration by asynchronous oblivious robots[END_REF]. The other extreme case is the set of grid-shaped networks [START_REF] Devismes | Optimal grid exploration by asynchronous oblivious robots[END_REF], where three robots are necessary and sufficient to explore deterministically any grid of at least three nodes (except for the grids of size 2 × 2 and 3 × 3, where four -respectively five -robots are necessary and sufficient). However, this result is mainly due to the fact that grids are not regular graphs: they contain nodes of degrees 2, 3, and 4. This topological property implies less symmetries. In contrast, rings and tori are regular graphs, and consequently more intricate. In ring-shaped networks [START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF], the fact that the number k of robots and the ring size n must be coprime yields a Ω(log n) lower bound, since the smallest non-divisor of n evolves as log n in the worst case. The case where k and n are coprime has been studied in the deterministic setting [START_REF] Lamani | Optimal deterministic ring exploration with oblivious asynchronous robots[END_REF], and five asynchronous robots are necessary and sufficient in this case. The large number of robots induced by the deterministic setting in ring-shaped networks hinted at a possible more efficient solution when robots can make use of probabilities [START_REF] Devismes | Optimal probabilistic ring exploration by semi-synchronous oblivious robots[END_REF]. As a matter of fact, four robots are necessary and sufficient to probabilistically explore any ring of size at least four. While the gain in going probabilistic is only one robot when k and n are coprime, a logarithmic factor is obtained in all remaining cases. Aforementioned deterministic solutions typically operate in the ASYNC model, while probabilistic ones can only cope with the weaker SSYNC model. Actually, an impossibility result [START_REF] Devismes | Optimal probabilistic ring exploration by semi-synchronous oblivious robots[END_REF] explicitly states that randomization does not help in the ASYNC model (that is, there exists a scheduling such that random choices are all nullified). So far, no research explored the feasibility of exploring a torus-shaped network with a team of k robots. The theoretical interest of such a setting lies in the additional axes of symmetry (w.r.t. ring shaped networks). As previously stated, the exploration (with stop) process is intrinsically related to the ability to differentiate consecutive phases of the exploration. More possible symmetries hint that more robots than in rings are required to complete exploration: As robots have no way to distinguish and to agree on some kind of orientation, e.g., North-South/Est-West, somehow the current robot configuration has to encode consistent information for both axes.

Contribution. We propose an optimal (w.r.t. the number of robots) solution for the terminating exploration of a torus-shaped network by a team of k such robots. In more details, we first show that it is impossible to explore a simple torus of arbitrary size with less than four robots, even if the algorithm is probabilistic. If the algorithm is required to be deterministic, four robots are also insufficient. This negative result implies that the only way to obtain an optimal algorithm (w.r.t. the number of robots participating to the algorithm) is to make use of probabilities, and thus, within SSYNC, due to aforementioned impossibilities [START_REF] Devismes | Optimal probabilistic ring exploration by semi-synchronous oblivious robots[END_REF].

So, we propose a probabilistic algorithm designed for the SSYNC model that uses four robots to explore all simple tori of size ℓ × L, where 7 ≤ ℓ ≤ L. Hence, in such tori, four robots are necessary and sufficient to solve the (probabilistic) terminating exploration. As a torus can be seen as a 2-dimensional ring, our result shows, perhaps surprisingly, that increasing the number of possible symmetries in the network (due to increasing dimensions) does not bring an extra cost with respect to the number of robots that are necessary to solve the problem.

Roadmap. Section 2 presents the system model and the problem to be solved. Lower bounds are shown in Section 3. The general solution using four robots is given in Section 4. The correctness of this solution is given in Section 5. Section 6 gives some concluding remarks. We assume that G is an (ℓ, L)-Torus (or a Torus, for short), where ℓ and L are two positive integers, i.e., G satisfies the following two conditions: (i) n = ℓ × L and (ii) there exists an order v 1 , . . . , v n on the nodes of V such that ∀i ∈ [1..n]:

• If i + ℓ ≤ n, then {i, i + ℓ} ∈ E, else {i, (i + ℓ) mod n} ∈ E. • If i mod ℓ = 0, then {i, i + 1} ∈ E, else {i, i -ℓ + 1} ∈ E.
Given the previous order v 1 , . . . , v n , for every j ∈ [0..(L -1)], the sequence v 1+j×ℓ , v 2+j×ℓ , . . . , v ℓ+j×ℓ is called an ℓ-ring. Similarly, for every k ∈ [1..ℓ], v k , v k+ℓ , v k+2×ℓ , . . . , v k+(L-1)×ℓ is called an L-ring. Note that when ℓ = L, any ℓ-ring is also an L-ring and conversely. More generally, we use the term ring to arbitrarily designate an ℓ-ring or an L-ring.

Remark 1 As an (ℓ, L)-torus is a simple graph, every node has four distinct neighbors, and consequently we have:

3 ≤ ℓ ≤ L and n = ℓ × L ≥ 9.
Nodes are assumed to be anonymous (they have no access to identifiers or other symmetry breaking capabilities). Moreover, given two neighboring nodes u and v, we assume that there is no explicit or implicit labeling allowing the robots to determine whether u is either on the left, on the right, above, or below v. However, for the purpose of proof description, we may use indices for nodes or robots.

An isomorphism of graphs G and H is a bijection f between the vertex sets of G and H such that any two nodes u and v of G are neighbors in G if and only if f (u) and f (v) are neighbors in H. When G and H are one and the same graph, f is called an automorphism of G. Remark that an (ℓ, L)-Torus and an (L, ℓ)-Torus are isomorphic. Hence, as the nodes are anonymous, an (ℓ, L)-Torus cannot be distinguished from an (L, ℓ)-Torus. So, without loss of generality, we always consider (ℓ, L)-Tori, where ℓ ≤ L.

Robots and Computation.

Operating on G are k robots. The robots do not communicate in an explicit way; however they see the position of all other robots in their ego-centered coordinate system and can acquire knowledge from this information.

Each robot operates according to its (local) program. We call protocol a collection of k programs, each one operating on a single robot. Here we assume that robots are uniform and anonymous, i.e., they all have the same program using no parameter allowing to differentiate them.

The program of a robot consists in executing Look-Compute-Move cycles infinitely many times. That is, the robot first observes its environment (Look phase). Based on its observation, a robot then (probabilistically or deterministically) decides to move or stay idle (Compute phase). When a robot decides to move, it moves toward its destination during the Move phase.

During the Compute phase, the decision between moving or staying idle is either deterministic or probabilistic. In the latter case, the robot decides between moving and staying idle using some fixed probability p, with 0 < p < 1; and we say that the robot tries to move.

We assume that robots cannot remember any previous observation nor computation performed in any previous cycle. Such robots are called oblivious.

We consider the semi-synchronous model [START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF]. In this model, time is represented by an infinite sequence of instants 0, 1, 2, . . . No robot has access to this global time. At each instant, a non-empty subset of robots is activated. Every robot that is activated at instant t atomically executes a full cycle between t and t + 1. Activations are determined by an adversary.

Note that in this model, any robot performing a Look operation sees all other robots on nodes and not on edges.

Multiplicity. We assume that during the Look phase, every robot can perceive whether several robots are located on the same node. This ability is called (global) multiplicity detection. We shall indicate by d i (t) the multiplicity of robots present in node v i at instant t. We consider two versions of multiplicity detection: the strong and weak multiplicity detections. Under the weak multiplicity detection, for every node v i , d i is a function N → {•, ⊥, ⊤} defined as follows: d i (t) is equal to either •, ⊥, or ⊤ according to v i contains none, one or several robots at instant t. If d i (t) = •, then we say that v i is free at instant t, otherwise v i is occupied at instant t. If d i (t) = ⊤, then we say that v i contains a tower at instant t. Under the strong multiplicity detection, for every node v i , d i is a function N → N where d i (t) = x indicates that there are x robots in node v i at instant t. If d i (t) = 0, then we say that v i is free at instant t, otherwise v i is occupied at instant t. If d i (t) > 1, then we say that v i contains a tower (of d i (t) robots) at instant t.

Configurations, Views and Executions. To define the notion of configuration, we need to use an arbitrary order ≺ on nodes. The system being anonymous, robots do not know this order. Let v 1 , . . . , v n be the list of the nodes in G ordered by ≺. The configuration at instant t is d 1 (t), . . . , d n (t). We denote by initial configurations the configurations from which the system can start at instant 0. Every configuration from which no robot moves or tries to move if activated is said to be terminal.

The view of robot R at instant t is a labeled graph isomorphic to G, where every node v i is labeled by d i (t), except the node where R is currently located, this latter node v j is labeled by d j (t), * . (Indeed, the coordinate system is ego-centered.) Hence, from its view, a robot can compute the view of each other robot, and decide whether some other robots have the same view as its own. The views V and V ′ are identical if and only if there exists an isomorphism f of V and V ′ such that every node v of V has the same label in V as node f (v) in V ′ . For example, in Figure 1, the robots located at node v 1 and v 5 respectively have identical views: to see this, apply the isomorphism

f such that f (v 1 ) = v 5 , f (v 2 ) = v 2 , f (v 3 ) = v 8 , f (v 4 ) = v 4 , f (v 5 ) = v 1 , f (v 6 ) = v 7 , f (v 7 ) = v 6 , f (v 8 ) = v 3 ,
and f (v 9 ) = v 9 on the view of the node located at v 1 . Conversely, the view of the node located at v 2 is different of the two others. Every decision to move is based on the view obtained during the last Look action. However, it may happen that some edges incident to a node v currently occupied by the deciding robot look identical in its view, i.e., v lies on a symmetric axis of its view. In this case, if the robot decides to take one of these edges, it may take any of them. We assume the worst-case decision in such cases, i.e., the actual edge among the identically looking ones is chosen by the adversary. Consider two indistinguishable configurations γ and γ ′ . Assume that some robot R is located at node v i in γ. Then, by definition, there is some robot R ′ located at node f (v i ) in γ ′ . Moreover, the view of R in γ is the same as the view of R ′ in γ ′ . So, if R is activated in γ and may decide to move to some neighboring node v j , then it is the same for R ′ : if R ′ is activated in γ ′ , it may decide to move to f (v j ). For example, assume that the robot located at v 1 in Configuration (a) of Figure 2 is activated and decides to move toward v 4 . Then, there is a possible step where the robot located at node

V → V such that ∀i ∈ {1, . . . , n}, d i = d ′ j where v j = f (v i ).
f such that f (v 1 ) = v 2 , f (v 2 ) = v 5 , f (v 3 ) = v 8 , f (v 4 ) = v 3 , f (v 5 ) = v 6 , f (v 6 ) = v 9 , f (v 7 ) = v 1 , f (v 8 ) = v 4 , and f (v 9 ) = v 7 . Conversely, configuration (c) is distinguishable from (a) (resp., (b)).
v 2 = f (v 1 ) in Configuration (b) moves toward v 3 = f (v 4 ).
A scheduling is a list of activation's choices that can be made by the adversary, i.e., a scheduling is any infinite list of non-empty subset of robots σ 0 , σ 1 , . . ., where ∀i ≥ 0, σ i is the set of robots activated at instant i. An infinite list of configurations γ 0 , γ 1 , . . . can be generated from the scheduling σ 0 , σ 1 , . . . if and only if ∀i ≥ 0, γ i+1 can be obtained from γ i after each robot in σ i is activated at instant i to atomically perform a cycle (in this case, γ i γ i+1 is step).

We call execution any infinite list of configurations γ 0 , γ 1 , . . . that can be generated from an arbitrary scheduling and such that γ 0 is a possible initial configuration. An execution e terminates if e contains a terminal configuration.

We restrict the power of the adversary by assuming that schedulings are fair: a scheduling σ 0 , σ 1 , . . . is fair if and only if for every robot R, for every instant i, there exists an instant j ≥ i such that R ∈ σ j . An execution e is fair if and only if e can be generated by a fair scheduling.

A particular case of fair scheduling is the sequential fair scheduling: a scheduling σ 0 , σ 1 , . . . that is fair and such that ∀i ≥ 0, |σ i | = 1. An execution e is sequential fair if it can be generated from a sequential fair scheduling.

Exploration. We consider the exploration problem, where k robots, initially placed at different nodes of a graph G = (V, E), collectively explore G before stopping moving forever. By "collectively" we mean that every node of G is eventually visited by at least one robot. More formally, we say that a protocol P deterministically (resp., probabilistically) solves the exploration problem assuming a fair scheduling if and only if every fair execution e of P starting from a towerless configuration satisfies: (1) e reaches a terminal configuration in finite time (resp., with probability one1 ), and (2) every node is visited by at least one robot during e. Note that the previous definition implies that every initial configuration are towerless. Note also that in case of probabilistic exploration, termination is not certain, however the overall probability of non-terminating executions is 0. Observe that the exploration problem is not defined for k > n and is straightforward for k = n. (In this latter case, the exploration is already accomplished in the initial towerless configuration.)

Lower bound

In this section, we first generalize to arbitrary topologies a result from [START_REF] Devismes | Optimal probabilistic ring exploration by semi-synchronous oblivious robots[END_REF], that was given for rings. We then instantiate this result to obtain a lower bound (actually 4) on the number of robots required to solve (deterministic or probabilistic) exploration in any torus.

To be as general as possible, we assume here that the multiplicity detection of robots is strong. Moreover, we consider any (deterministic or probabilistic) exploration protocol P using a team of k robots in an arbitrary topology G = (V, E) of n nodes (i.e., n = |V |).

First, assume that n > k. Then, the exploration is not (trivially) accomplished in an initial configuration. As robots are oblivious, any terminal configuration of P in that case should be different from any possible initial configuration. Now, the set of possible initial configurations is exactly the set of all towerless configurations. So, any terminal configuration necessarily contains a tower:

Remark 2 If n > k,

any terminal configuration of P contains at least one tower.

Consider an instant t. Despite a non-empty subset of robots being activated at instant t, it is possible that no robot moves between t and t + 1. Such "empty" steps being useless, we may consider the minimal relevant subsequence of the execution defined below, where all "empty" steps have been removed: Definition 1 (MRS) Let s be a sequence of configurations. The minimal relevant subsequence of s, noted MRS(s), is the maximal subsequence of s where no two consecutive configurations are identical.

Lemma 1 Assume that n > k. Let e be any sequential fair execution e of P that terminates,2 MRS(e) has at least nk + 1 configurations containing a tower of less than k robots.

Proof. Assume, by the contradiction, that there is a sequential fair execution e of P that terminates and such that MRS(e) has less than nk + 1 configurations containing a tower of less than k robots.

Take the last configuration α without tower that appears in e and all remaining configurations that follow in e (all of them contains a tower) and form e ′ (e ′ necessarily exists, by Remark 2). As α could be an initial configuration and e is a sequential fair execution that terminates, e ′ is also a sequential fair execution of P that terminates.

By definition, MRS(e ′ ) is constituted of a configuration with no tower only followed by configurations with tower and nk new nodes (remember that k nodes are already visited in the initial configuration) must be visited before e ′ reaches its terminal configuration.

Consider a step ββ ′ in e ′ .

1. If β = β ′ , then no node is visited during the step.

2. If β = β ′ , then there are three possible cases:

(a) β contains no towers. In this case, β = α (the initial configuration of e ′ ) and β ′ contains a tower.

As only one robot moves in ββ ′ to create a tower (e ′ is sequential), no node is visited during this step.

(b) β contains a tower and β ′ contains a tower of k robots. As e ′ is sequential and all robots are located at the same node in β ′ , one robot moves to an already occupied node in ββ ′ and no node is visited during this step.

(c) β contains a tower and β ′ contains a tower of less than k robots. In this case, at most one node is visited in ββ ′ because e ′ is sequential.

To sum up, only the steps from a configuration containing a tower to a configuration containing a tower of less than k robots (Case 2.(c)) allow to visit at most one node each time. Now, in MRS(e ′ ) there are less than nk + 1 configurations containing a tower of less than k robots and the first of these configurations appearing into e ′ is consecutive to a step starting from the initial configuration (Case 2.(a)). Hence, less than nk nodes are dynamically visited during e ′ and, as exactly k nodes are visited in the initial configuration, less than n nodes are visited when e ′ terminates, a contradiction. ✷ Lemma 2 If n > k, then for every sequential fair execution e of P that terminates, MRS(e) has at least nk + 1 configurations containing a tower of less than k robots and any two of them are distinguishable.

Proof.

Consider any sequential fair execution e = γ 0 , γ 1 , . . . of P that terminates. As e terminates, MRS(e) has a finite number of configurations. So, let x be the number of configurations in MRS(e) containing a tower of less than k robots. By Lemma 1, x ≥ nk + 1.

We first show that (*) if MRS(e) contains at least two configurations having a tower of less than k robots that are indistinguishable, then there exists a sequential fair execution e ′ that terminates and such that MRS(e ′ ) has x ′ configurations containing a tower of less than k robots, where x ′ < x.

Assume that there are two indistinguishable configurations γ t = d t 1 , . . . , d t n and γ t ′ = d t ′ 1 , . . . , d t ′ n in MRS(e) having a tower of less than k robots. Without loss of generality, assume that t ′ > t. By definition, there exists an automorphism f on G such that ∀i ∈ {1, . . . , n},

d t i = d t ′ j where v j = f (v i ).
Then,

e ′ = γ 0 , . . . , γ t , γ ′ t ′ +1 , γ ′ t ′ +2 , .
. . is a sequential fair execution of P, where that ∀z ≥ t ′ + 1, we have

γ ′ z = d z g(1) , . . . , d z g(n)
where g is a bijection such that ∀s ∈ [1.

.n], f (v s ) = v g(s) and γ z = d z 1 , . . . , d z n . Moreover, MRS(e ′ ) has x ′ configurations containing a tower of less than k robots, where x ′ < x.

By (*), if MRS(z) contains less than n-k +1 distinguishable configurations altogether with a tower of less than k robots, it is possible to (recursively) construct a sequential fair execution e ′ of P that terminates such that MRS(e ′ ) has less than nk + 1 configurations containing a tower of less than k robots, a contradiction to Lemma 1. Hence, the lemma holds. ✷

From Lemma 2, we can deduce the following corollary:

Corollary 1 Considering any (probabilistic or deterministic) exploration protocol for k robots on a graph of n > k nodes working under any fair scheduling, there exists a set S of at least nk + 1 configurations such that:

1. any two different configurations in S are distinguishable, and 2. in every configuration in S, there is a tower of less than k robots.

Theorem 1 Assuming fair schedulings, ∀k, 0 ≤ k < 3, there is no protocol to (deterministically or probabilistically) explore any torus of n nodes using k robots.

Proof.

First, k < 9 ≤ n = ℓ × L (see Remark 1). Then, for k = 0, the theorem is trivially verified. Consider now the case k = 1 and k = 2. With one robot it is impossible to construct a configuration with a tower; and with two robots it is impossible to construct a configuration with a tower of less than k robots (k = 2). Hence, for k = 1 and k = 2, the theorem is a direct consequence of Corollary 1. ✷

The previous theorem excludes that P works with k < 3. Let now assume that k = 3 and consider any arbitrary (ℓ, L)-torus (remember that n = ℓ × L ≥ 9, Remark 1). Then, by Corollary 1, we should be able to exhibit a set S of n -2 configurations such that:

1. Any two different configurations in S are distinguishable, and 2. In every configuration in S, there is a tower of 2 robots. Such configurations differ according to the relative positions of the tower and the robot which is alone. Two cases are then possible depending on whether ℓ = L or ℓ < L. In the former case, the size of S is bounded by Figure 3: For every value i inside a white node, every two configurations where (1) the black node contains the tower of two robots and (2) any white node of number i contains the single robot are indistinguishable.

⌊ L 2 ⌋+1 i=2 i = ⌊ L 2 ⌋×(⌊ L 2 ⌋+3) 2
In the latter case, the size of S is bounded by

(⌊ ℓ 2 ⌋ + 1)(⌊ L 2 ⌋ + 1) -1.
For example (refer to Figure 4), in a (5, 6)-torus, the size of S is at most 11. Let now study the case where ℓ = L. Then,

⌊ L 2 ⌋×(⌊ L 2 ⌋+3) 2
should be greater or equal to n -2, i.e., L 2 -2. ]. Now L ≥ 3 (Remark 1) and 6+ √ 484 14 = 2. So, we obtain a contradiction: there is neither probabilistic nor deterministic exploration protocol in that case, even assuming a fair scheduling.

⌊ L 2 ⌋×(⌊ L 2 ⌋+3) 2 ≥ L 2 -2 ⌊ L 2 ⌋ × (⌊ L 2 ⌋ + 3) ≥ 2L 2 -4 L 2 4 + 3L 2 ≥ 2L 2 -4 L 2 +6L 4 ≥ 2L 2 -4 L 2 + 6L ≥ 8L 2 -16 7L 2 -6L -16 ≤ 0 ∆ = 484 > 0, so 7L
Let now study the case where ℓ < L. Then,

(⌊ ℓ 2 ⌋ + 1)(⌊ L 2 ⌋ + 1) -1 should be greater or equal to n -2, i.e., ℓ × L -2. (⌊ ℓ 2 ⌋ + 1)(⌊ L 2 ⌋ + 1) -1 ≥ ℓ × L -2 ℓ×L 4 + ℓ 2 + L 2 + 1 ≥ ℓ × L -1 ℓ×L+2ℓ+2L 4 ≥ ℓ × L -2 ℓ × L + 2ℓ + 2L ≥ 4ℓ × L -8 2ℓ + 2L + 8 ≥ 3ℓ × L
Now, as 3 ≤ ℓ < L (Remark 1), 2ℓ + 2L + 8 ≥ 3ℓ × L has no solution: there is neither probabilistic nor deterministic exploration protocol in that case, even assuming a fair scheduling.

Hence, there is neither probabilistic nor deterministic protocol to explore any torus with 3 robots and, with Theorem 1, we can conclude:

Theorem 2 Assuming fair schedulings, ∀k, 0 ≤ k < 4, there is no protocol to (deterministically or probabilistically) explore any torus of n nodes using k robots.

Consider now the deterministic exploration with k = 4 robots. Assume any (ℓ, L)-Torus such that ℓ = L and ℓ is even. Then, it is possible to initially place the four robots in such way that they have all identical views and all their possible destinations looked identical (just form a square whose adjacent sides have length ℓ

2 ). In this case, the adversary can choose to synchronously activate all robots at each step in such way that the initial symmetry continues: we obtain a fair execution which does not terminate. Hence, following the idea of [START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF], we have: Theorem 3 Assuming fair schedulings, ∀k, 0 ≤ k ≤ 4, there is no protocol to deterministically explore all tori of n nodes using k robots.

Notice that the previous impossibility result can be circumvented, for example, by making restrictions on possible initial configurations [START_REF] Gianlorenzo | Gathering and exclusive searching on rings under minimal assumptions[END_REF].

Optimal Algorithm

We propose in Algorithm 1 a probabilistic protocol to explore with k = 4 robots any (ℓ, L)-torus such that 7 ≤ ℓ ≤ L, assuming weak multiplicity detection.

Definitions

We call a block a maximal elementary path along some ring of the torus B = u i , u i+1 , . . . , u i+m with m > 0, where each node is occupied by exactly one robot. In B, the nodes u i and u i+m are termed as the extremities of B. The size of a block is the number of robots it contains. We call x-block any block of size x. A robot that does not belong to any block is said to be isolated.

We call hole any maximal non-empty elementary path of free nodes that is along some ring of the torus. The size of a hole is the number of nodes that it contains. We call x-hole any hole of size x. In the hole H = u i , . . . , u k (k ≥ i) the nodes u i and u k are termed as the extremities of H. We call neighbor of a hole any node that does not belong to the hole but is neighbor of one of its nodes. In this case, we also say that the hole is a neighboring hole of the node. By extension, any robot that is located at a neighboring node of a hole is also referred to as a neighbor of the hole.

A node is safe if there is at most one robot that is located within distance one from it. We call Couple any ℓ-ring that contains exactly two robots.

Overview of the algorithm

Our algorithm works in three distinct successive phases: Phase SetUp, Phase Tower, and Phase Exploration.

Starting from any towerless configuration, the aim of the Phase SetUp is to arrange the robots in such a way that they eventually form a ♦.Configuration, without creating any tower during the process. This phase is probabilistic. A ♦.Configuration is any configuration, where (1) there are two ℓ-rings of the torus that both contain a 2-block, and (2) there are two robots that have two robots in their neighborhood. An example of a ♦.Configuration is given in Figure 5. Once a ♦.Configuration is reached, Phase Tower begins. This phase is also probabilistic and consists in creating a tower using the two neighboring robots that have exactly two robots in their neighborhood. Once the tower is created, the location of robots give an explicit orientation to the torus; and the last phase, Phase Exploration, begins. This phase is deterministic. The two isolated robots collaborate together to deterministically explore the torus and eventually stop.

Below, we detail each phase of our algorithm.

Algorithm 1 Main Program.

Phase SetUp

Phase SetUp is formally described in Algorithms 2-7.

Configurations

The behavior of Phase SetUp is led by the configurations. Below, we define the main classes of configurations.

A configuration is called Double-Trap1 (refer to Figure 6) iff there exists a ℓ-ring R that contains a 3-block having exactly one extremity with a neighboring robot that is not in R. A configuration is called Double-Trap2 (refer to Figure 7) iff there is one isolated robot at some node z and two 2-blocks B1 = u, v and B2 = x, y such that (1) v = x, (2) B1 is on a ℓ-ring, (3) z and y are on a ℓ-ring parallel to the one containing B1, and (4) z is at distance 2 of both u and y. A configuration is called Isolated iff there exists at most one robot on each ring of size ℓ. A configuration is called Triplet iff it is not a Double-Trap1 configuration and there is a ℓ-ring R that contains 3 robots. When R contains neither a 3-block nor a 2-block, we define the Wall as the ring perpendicular to R that contains at most one or two robots (refer to Figure 8). A configuration is called Twin (refer to Figure 9) iff it contains a couple but it is neither a Double-Trap2 nor a ♦.configuration. A configuration is called Quadruplet iff there exists a ℓ-ring R that contains 4 robots.

Description of Phase SetUp

Recall that the aim of the SetUp phase is to create a ♦.Configuration, starting from an arbitrary towerless configuration and without creating any tower during the phase. As a matter fact, we try to make robots move deterministically as much as possible. However, there are symmetric configurations that require robots to move probabilistically. The main one is the following:

(a) The configuration is of type Identical. That is, all robots have identical views. To break this symmetry, each robot tries to move to a safe node. Doing so, the symmetry is broken after one step with positive probability.

So, with probability one (or almost surely, see [START_REF] Stroock | Probability theory : an analytic view[END_REF], page 186), the system eventually leaves Case (a) to a configuration that matches one of the following cases:

(b) The configuration is of type Double-Trap2. In this case, only one robot moves as shown in Figure 7, we obtain a ♦.Configuration, and the SetUp phase is done.

(c) The configuration is of type Double-Trap1. In this case, only one robot moves as shown in Figure 6 and we obtain a Double-Trap2 configuration. After one more move, we obtain a ♦.Configuration and the SetUp phase is done.

(d) The configuration is of type Triplet. In this case, there are three robots in the same ℓ-ring R and we deterministically build a Double-Trap1 configuration.

If three robots on R already forms a 3-block, the remaining robot (not part of R) moves to the adequate position to build a Double-Trap1 configuration.

Otherwise, if R contains a 2-block, then the robot in R that is not part of the 2-block moves to create the 3-block. Otherwise, a Wall is defined and we use it to create a 2-or 3-block on R: if the node v that both intersects the Wall and R is occupied by some robot, the two other robots on R move towards the Wall to create a 2-or a 3-block (depending on the choices of the scheduler); otherwise, each robot of R that is not neighbor of v moves towards v until a 2-block is created on R.

(e) The configuration is of type Twin. In this case, the aim is to reach a Triplet configuration with positive probability.

If the configuration contains only one couple, the two robots that are not part of the couple compete together (using try to move) so that eventually one of them is closer from the couple than the other.

Then, the closest one moves to create the triplet configuration. Now, the configuration may contain two or three couples (but not four, otherwise we would be on case (a)). In such cases, we consider the smallest rectangle, SER, that encloses the 4 robots. If there are robots that are located at a corner of SER and belong to only one couple, such robots try to move to a neighboring safe node outside their couple. With a positive probability, only one of them moves and we retrieve a twin configuration that contains only one couple. In the case where there is no robot at the corner, then the two robots that are part of different couple being the farthest from each other try to move to a safe node.

In all remaining configurations, the aim is to reach either a triplet or twin configuration.

(f) The configuration is of type Quadruplet. In such a configuration, the four robots belong to some ℓ-ring R. We then consider the subgraph G R induced by the nodes of R. This graph is isomorphic to an elementary cycle. Now, as not all robots have identical views, we can discriminate either one unique robot or two robots (using the sizes of the holes in G R ). We let those robots move outside R. Hence, the system reaches either a twin or a triplet configuration.

(g) The configuration is of type Isolated. We consider two subcases:

ℓ > L. In this case, we try to discriminate the L-rings according to the number of robots on them. When some but not all robots are alone in their L-rings, they move along their L-ring to eventually form a triplet or a twin configuration with the blocked ones.

In the case where one L-ring R contains the four robots, we proceed as in Case (f ).

In the case where either every L-ring contains at most one robot, or two L-rings contain 2 robots, we again consider the smallest rectangle, SER, that encloses the 4 robots. We can then discriminate robots according to their place in SER: at a corner, on a side, or inside of SER. This allows us to block some of them. The other ones move to create either a triplet or a twin configuration.

ℓ = L. Again, we consider the smallest rectangle, SER, that encloses the 4 robots. We discriminate robots as previously. However, note that this case is simpler than the previous one because all rings have the same size (ℓ), while in the previous case we had to take care that robots gather on a "small" ring.

Algorithm 2 SetUp.

2.01

Let C be the current configuration Algorithm 3 Procedure ♦-Creation.

3.01

Let C be the current configuration and R be the ring of the torus that contains 3 robots then move towards the a free node that closest from the 3-block and not part of R Algorithm 4 Procedure Couple.

3.02 if R contains no 3-block 3.03 then if R contains no 2-block 3.04 then if R ∩ Wall= Free-Node

4.01

Let C be the current configuration Algorithm 5 Procedure Quadruplet.

5.01

We consider the subgraph G R induced by the nodes of the ring R that contains the 4 robots

5.02

(G R is isomorphic to a cycle) then move to an adjacent free node outside R Algorithm 6 Procedure Isolated-1 (Case ℓ = L).

6.01

Let SER the smallest rectangle that encloses the four robots

6.02

We call internal robot any robot that is not on any side of SER

6.03

there is exactly one robot that is at a corner c of SER then move towards the closest corner of SER Algorithm 7 Procedure Isolated-2 (Case ℓ < L).

7.01

Let SER the smallest rectangle that encloses the four robots then Let r 1 , r 2 , r 3 , and r 4 be the four robots

7.04

There are two robots, say r 1 and r 2 , that are on two parallel sides of SER that are on ℓ-rings else // there one L-ring R that contains all robots 7.17

Let G R be the subgraph induced by R

7.18

Apply Procedure Quadruplet on G R

Tower Phase

This phase starts from any ♦.Configuration, see for example Figure 5. Let u 1 and u 2 be the two occupied neighboring nodes having themselves two occupied neighboring nodes. Let r 1 and r 2 be the two robots located at u 1 and u 2 , respectively. During this phase, r 1 and r 2 try to move towards each other anytime they are activated; the other two robots do not move if activated. If only one of them is activated, a tower is created. If both are activated simultaneously, there is a positive probability that only one of those moves; otherwise the system remains in a ♦.Configuration. As the scheduler is fair, both of them are activated regularly until a tower is created. So, this latter event eventually occurs with probability one. Therefore, a tower T is created with probability one on either u 1 or u 2 -refer to Figure 10 -and the Tower phase is finished.

Algorithm 8 Phase Tower.

8.01

if I am neighbor of two occupied nodes

Phase Exploration

We first need some definitions. Given two nodes u and v, let R uv be the smallest enclosing rectangle that includes both u and v, see Figure 11. Let α uv (β uv ) be the length in terms of hops of one of the smallest (resp., greatest) side of R uv , e.g., α uv = 2 and β uv = 4 in Figure 11. R uv is an (α uv , β uv )-rectangle. The (Manhattan) distance between two nodes u and v, denoted by d uv , is equal to α uv + β uv , e.g., d uv = 6 in Figure 11. We define a total order on distances as follows: given four nodes u, v, u ′ , and v ′ ,

d uv ≤ d u ′ v ′ iff either d uv < d u ′ v ′ or d uv = d u ′ v ′ and β uv ≤ β u ′ v ′ . β uv α u v uv uv R Figure 11: Smallest Enclosing Rectangle.
The deterministic exploration starts assuming that two robots form a tower. Denote the node holding the tower by T. The two rings passing through T are called coordinate rings. In the sequel, 'o' (respectively, ' * ') denotes the nearest (respectively, farthest) single node (or robot) from T, i.e., d oT < d * T . Note that our algorithm ensures that both 'o' and ' * ' remain the same robots until the end of the exploration. Given a node u, if α T u < β T u and {α T u , β T u } = {⌊ ℓ 2 ⌋, ⌊ L 2 ⌋}, then there exists an orientation of the coordinate rings such that u = (α T u , β T u ), see for example Figure 12. In the following, when it is possible, we build a coordinate system over R T u by setting the x-axis (the y-axis) as the coordinate rings that is parallel to the smallest (resp., greatest) side of R T, * and by orienting both axis so that the coordinates of u are positive.

The formal algorithm in shown in Algorithms 9 to 14. The main idea of Phase Exploration is the following: both robots that are not part of the tower collaborate together in order to explore the whole torus.

They alternate between two roles: Explorer and Leader. Leader L allows to build a coordinate system S L Next, Robot * moves to node (2, 3) passing through node (1, 3), see Movings 3 ′ and 3 ′′ in Lines 9.08 and 9.14. Then, Robot o visits the nodes that form the second surrounding square around T and stops at (-2, -2), see Moving #4 in Lines 9.26. Finally, Robot * moves back to (1, 3), followed by Robot o that moves back to (-2, -1), see Movings #5 and #6 in Lines 9.24 and 9.17. This ends the first phase. Note that our method requires that Robot * must be able to move at least three lines away from the tower. Furthermore, Robot o must be able to visit the two squares centered on the tower and the orientation built by Robot * must be unambiguous. These three conditions constrain the torus to be of size at least 7 × 7.

Phase 2: In this phase, Robot o is the leader. R To provides a coordinate system S o , where Robot o is located at [START_REF] Flocchini | Distributed Computing by Oblivious Mobile Robots[END_REF][START_REF] Chalopin | Network exploration by silent and oblivious robots[END_REF]. Robot * now proceeds to the spiral exploration by visiting surrounding squares around T one after another, see Figures 14 and15. This process is initiated at Line 9.20 and managed by Procedures 2ndSpiralM ngmt and 2ndSpiral (Algorithms 11 and 12). Robot * first explores the third surrounding square around T, then the fourth, and so forth, until it visits the (⌊ ℓ 2 ⌋ -1)-th square. Then, there are two cases depending on the parity of ℓ: If ℓ is odd, then Robot * visits the whole ⌊ ℓ 2 ⌋-th square and finish at the negative (w.r.t S o ) corner of the square, see for example Figure 14. Otherwise (ℓ is even), Robot * visits half of the ⌊ ℓ 2 ⌋-th square only and stops at the positive corner (w.r.t. S o ) of the square, see for example Figure 14. In both cases, if ℓ = L, then the exploration is done, see Line 11.10.

Phase 3: This last phase is performed only if ℓ = L. In that case, Robot * terminates the exploration by going alternatively from the left to the right and from the right to the left among the nodes forming the remaining of the rectangle. If ℓ is odd, then Robot * progresses towards the negative (w.r.t. S o ) side of the torus, see Figure 14 and Algorithm 13. Otherwise (ℓ is even), the progression is made on the positive side, see Figure 15 and Algorithm 14. In both cases, the exploration ends either on the positive side or the negative side of the L-th line, depending on either L is odd or even, see Figures 1415that shows two of the four possible cases of termination depending on the parity of both ℓ and L. Proof. Let R be the ring that contains three robots in C. The cases below are possible:

1. R contains a 3-block. In this case the robot that is not part of R is the only one allowed to move (refer to Algorithm 3, Line 15). Its destination is its adjacent node on the shortest path towards the closest free node neighbor of one extremity of the 3-block (let us refer to this free node by U ). Observe that this robot is the only one allowed to move unless it reaches U . Now, the scheduler being fair, the target node is reached in finite time and then a Double-Trap1 configuration is created. By Lemma 4, we are done in this case. 2. R contains a 2-block. In this case, the robot that is on R, but not part of the 2-block is the only one allowed to move (refer to Algorithm 3, Line 11). Its destination is its adjacent free node on the shortest path towards the 2-block (on R). Note that this robot is the only one allowed to move unless it becomes part of a 3-block. Now, as the scheduler is fair, we retrieve Case 1 in finite time and we are done.

The other cases.

(a) If R ∩ wall= Occupied-Node. Then, the robots allowed to move are the two robots on R that are not located at Occupied-Node (refer to Algorithm 3, Line 8). Their destination is their adjacent free node towards the wall. According to the choices of the fair scheduler, either a 3-block is created and we retrieve Case 1, or a 2-block is created and we retrieve Case 2. (b) If R ∩ wall= Free-Node then, every robot of R that is not neighbor of Free-Node moves towards Free-Node until a 2-block is created on R (refer to Algorithm 3, Line 5). As the scheduler is fair, a 2-block is created on R in finite time, and we retrieve Case 2. ✷

From the other towerless configurations (Identical, Twin, Quadruplet, and Isolated), the convergence to a ♦.Configuration is probabilistic. Now, when considering any arbitrary fair execution, (1) the topology is fixed with, in particular, a finite number of nodes and (2) recall that the number of robots is the constant 4. So, the number of towerless configurations is also finite. Now, while a configuration of type Double-Trap1, Double-Trap2, Triplet, or ♦.Configuration is not reached, the SetUp phase remains trapped in the finite subset of towerless configurations defined as the distinct union of Configuration Identical, Twin, Quadruplet, and Isolated, by Remark 4. So, in order to demonstrate that the system eventually reaches a ♦.Configuration with probability one, we show below that from any configuration of type Identical, Twin, Quadruplet, or Isolated, there always exists a positive probability to reach a configuration of type Double-Trap1, Double-Trap2, or Triplet in finite time and despite the choices of the fair scheduler. (Remember that once such a configuration is reached, a ♦.Configuration is reached within finite time, by Lemmas 3-5.) Lemma 6 If C is of type Twin then, with positive probability, a configuration of type Triplet is reached in finite time.

Proof. When the configuration C is of type Twin, the cases bellow are possible (C cannot contains four couples, otherwise it would be of type Identical):

1. C contains a unique couple, R. (a) If there is a unique robot r that is outside R and the closest to R, then r is the only robot allowed to move, and if activated, it moves towards the closest free node in R (refer to Lines from 4.03 to 4.05). Observe that by moving r becomes even close to R. Thus, r keeps being the only robot allowed to move until it becomes part of R. Hence, as the scheduler is fair, a Triplet configuration is reached, in this case, within finite time. (b) In either cases, the two robots that are outside R try to move to a safe node outside their current ring and that is parallel to R (refer to Lines from 4.06 to 4.07). Then, as the scheduler is fair, at least one of them is activated in finite time, and when activated, with positive probability (actually, a probability greater or equal to p(1p)), exactly one of those robots moves and we retrieve the previous case. Hence, we can conclude that, in this case, with positive probability, a configuration of type Triplet is reached in finite time. Observe that, in this case, there exist two robots that are the farthest from each other, otherwise the configuration would be of type Identical. These robots try to move to a neighboring safe node, if activated (refer to Algorithm 4, Lines 4.16 to 4.18). As the scheduler is fair, at least one of them is activated in finite time, and when activated, with positive probability (actually, a probability greater or equal to p(1p)), exactly one of them moves. In this case, i. either, the configuration remains with two couples but this time there are robots on the corner. Thus, we retrieve Case 2a, or ii. a Triplet configuration is reached. Hence, from the previous cases, we can conclude that, in this case, with positive probability, a configuration of type Triplet is reached in finite time. 3. C contains three couples. (In this case, the torus necessarily satisfies ℓ = L.) Observe that, in this case, there exist two robots that are part of two couples at the same time. The robots allowed to move are the other two robots. These robots try to move to a neighboring safe node. As the scheduler is fair, at least one of them is activated within finite time and when activated, with positive probability (actually, a probability greater or equal to p( Proof. Let us refer to the ring that contains four robots in C by R. We have the following possible cases:

• R contains exactly one smallest hole. In this case, the two robots neighbor to such a hole move to an adjacent free node outside R, if activated (refer to Lines from 5.03 to 5.05). As the scheduler is fair, at least one of them is activated within finite time. Then, if both robots move simultaneously, then the reached configuration is of type Twin. If only one robot moves, then the reached configuration is of type Triplet.

• R contains exactly one biggest hole. In this case too, the two robots neighbor to such a hole move to an adjacent free node outside R, if activated (refer to Lines from 5.06 to 5.08). As the scheduler is fair, at least one of them is activated within finite time. Then, if both robots move simultaneously, the reached configuration is of type Twin. If only one robot moves, then a Triplet configuration is reached.

• There is only one robot that is neighbor to the two smallest holes on R. This robot is the only one allowed to move. Its destination is its adjacent free node outside R (refer to Lines from 5.09 to 5.10).

As the scheduler is fair, this robot moves in finite time and then a configuration of type Triplet is reached.

From the cases above we can deduce that starting from C, either Twin or Triplet configuration is reached in finite time.

✷ By Lemma 6, we have the following corollary from the previous lemma: Proof. We split the study into two main cases: 1. ℓ = L. Let SER be the smallest rectangle that encloses the four robots, we call internal robot any robot that is not located on any side of SER. The following subcases are possible: (a) There is exactly one robot that is at a corner c of SER. In this case there is exactly one internal robot. It is the only robot allowed to move, its destination is the closest free node on a side of SER having c as extremity (refer to Lines from 6.03 to 6.05). Observe that this robot keep being enabled until it becomes on the same ring as c (the SER is invariant). Thus, as the scheduler is fair, a Twin configuration is reached in finite time and by Lemma 6, we are done. (b) There are exactly two robots at two corners c 1 , c 2 of SER. The other two robots are in this case internal (otherwise the configuration would contain a couple). The internal robots that are the closest to an occupied corner of the SER move towards the closest free node on a side of SER having c 1 or c 2 as an extremity (refer to Lines from 6.06 to 6.08). Note that in the case where there are two robots allowed to move, their target destination is different (recall that the configuration is of type Isolated). The robots that have moved keep moving towards the same target node until they become on the same ring as a robot on the corner of the SER. Thus, as the scheduler is fair, a Twin configuration is reached in finite time and by Lemma 6, we are done. from 7.11 to 7.13). As the scheduler is fair, in finite time one or both of them are activated and with positive probability (actually, a probability greater or equal to p(1p)), only one of them moves and we retrieve Case 2b. ii. There are two robots at corners, say r 1 and r 2 , that are part of different L-rings. r 1 and r 2 are the only robots allowed to move and their destination is their adjacent free node on the neighboring L-ring outside SER (refer to Lines from 7.14 to 7.15). As the scheduler is fair, in finite time, either r 1 , r 2 , or both are activated. In the two first cases, we retrieve Case 2b. In the latter case, we retrieve Case 2a. (e) There is one L-ring R that contains all robots. Let GR be the subgraph induced by R. The robots in this case apply Procedure Quadruplet on GR. By Corollary 2, we are done. ✷ From all previous lemmas and corollary, we can deduce that, with probability one, the SetUp phase eventually terminates in a ♦.Configuration. Hence, we can conclude with the following theorem: Theorem 4 Assuming any fair scheduler, Algorithm 1 is a probabilistic exploration protocol for 4 robots on any torus of size ℓ × L, where 7 ≤ ℓ ≤ L.

Concluding Remarks

While the solution we provided for the torus exploration problem is optimal with respect to the number of robots involved in the exploration, there remain challenging open questions:

1. We presented an algorithm for all tori of size ℓ × L, where 7 ≤ ℓ ≤ L. Determining if our results can be extended to smaller tori is an interesting problem, as previous results [START_REF] Devismes | Optimal grid exploration by asynchronous oblivious robots[END_REF] show e.g. that smaller grids require more robots. We expect mechanized approaches [START_REF] Franc ¸ois Bonnet | Brief announcement: Discovering and assessing fine-grained metrics in robot networks protocols[END_REF] to be valuable for investigating small size tori robot number requirements.

2. Going higher dimension (from a ring to a torus) did not increase the robot number complexity of the exploration problem. The issue of the d-dimensional tori (for d > 2) remains open.

Figure 1 :

 1 Figure 1: Configuration where two robots have identical views. Numbers inside nodes indicate the strong multiplicity value.

  For example, Configurations (a) and (b) in Figure 2 are indistinguishable: to see this, apply the automorphism

Figure 2 :

 2 Figure 2: Example of indistinguishable and distinguishable configurations in a (3,3)-torus. Numbers inside nodes indicate the strong multiplicity value.

Figure 4 :

 4 Figure 4: For every value i inside a white node, every two configurations where (1) the black node contains the tower of two robots and (2) any white node of number i contains the single robot are indistinguishable.

Figure 5 :

 5 Figure 5: A ♦.Configuration.

Figure 6 :

 6 Figure 6: Double-Trap1 Configuration.

Figure 7 :

 7 Figure 7: Double-Trap2 Configuration.

Wall

Figure 8 :

 8 Figure 8: A wall in a Triplet Configuration.

2 Figure 9 :

 29 Figure 9: Twin Configuration .

if

  I am on R, but not part of the 2-block

  every L-ring contains at most one robot 7.03

  if I am r 3 or r 4 7.06 then move towards a closest extremity of the side of SER where I am 7.07 else if there is exactly one L-ring R that contains 2 or 3 robots 7.08 then if I am alone in my L-ring 7.09 then move along my L-ring towards a closest free node that is adjacent to an occupied node of R 7.10 else if there are two L-rings that contain 2 robots 7.11 then if a L-ring contains two robots located at corners of SER 7.12 then if I am at a corner of SER 7.13 then try move to the adjacent L-ring outside SER 7.14 else if I am at a corner of SER7.15 then move to the adjacent L-ring outside SER 7.16

thenFigure 10 :

 10 Figure 10: Initial Configuration for Deterministic Exploration.

Figure 12 :Phase 1 :

 121 Figure 12: Coordinate System.over R TL . The explorer is in charge of deterministically exploring the torus over S L . The exploration works in three phases, executed in sequence:

1 Figure 13 :

 113 Figure 13: First phase of exploration.

Figure 14 :Figure 15 :Algorithm 9

 14159 Figure 14: Second and third phase of exploration, odd case.

then

  Move in the opposite direction than the direction provided by R T o //Fig. 13, Moving #1 9.04 else Let S * be the coordinate system built over RT * 9.05 if RT * is an (1, 2)-rectangle 9.06 then if o = (-1, -1) 9.07 then if I am *

then

  Move to Position (1, 3) //Fig. 13, Moving #3' 9.09 else if I am o 9.10 then 1stSpiral(1) //Fig. 13, Moving #2 9.11 else if RT * is an (1, 3)-rectangle 9.12 then if o = (-1, -1) 9.13 then if I am *

9 . 14 then

 914 Move to Position (2, 3) //Fig. 13, Moving #3"

then

  Move to Position (-2, -1) //Fig. 13, Moving #6 then 2ndSpiralM ngmt // Robot * executes the last spiral phase 9.21 else if RT * is an (2, 3)-rectangle 9.22 then if o = (-2, -2) 9.23 then if I am *

9 . 24 then

 924 Move to Position (1, 3) //Fig. 13, Moving #5 9.25 else if I am o 9.26 then 1stSpiral(2) //Fig. 13, Moving #4 in finite time and a configuration of type Double-Trap2 is then reached. Hence, by Lemma 3, we are done. ✷ Lemma 5 If C is of type Triplet, then a configuration C ′ of type ♦.Configuration is reached from C within finite time.

Corollary 2 Lemma 8 Lemma 9

 289 If C is of type Quadruplet then, with positive probability, a configuration of type Triplet is reached in finite time. If C is of type Identical then, with positive probability, a configuration of type Triplet or Double-Trap2 is reached in finite time.Proof. If C is of type Identical then every robot tries to move, if activated. Now, in this case, with positive probability, exactly one of them moves during the next step and a configuration of type either Double-Trap2 or Twin is then reached. In the latter case, we can conclude by Lemma 6.✷ If C is of type Isolated then, with positive probability, a configuration of type Triplet is reached in finite time.

  Two configurations d 1 , . . . , d n and d ′ 1 , . . . , d ′ n are indistinguishable (resp., distinguishable otherwise) if and only if there exists an automorphism on G, f :

  2 -6L -16 = 0 has two solutions:6-

	for L ∈ [ 6-	√ 14 484	; 6+	√ 14 484	√ 14 484	and 6+	√ 14 484	; and 7L 2 -6L -16 ≤ 0

  2. C contains two couples. Two cases are possible: (a) There is at least one robot at the corner of the SER. (SER is the smallest enclosing rectangle.)In this case, if one of the robots at the corner of the SER is not part of any Couple, then this robot is the only one allowed to move (refer to Algorithm 4, Lines 4.11 to 4.13). Its destination is its adjacent free node towards the closest couple. Then, as the scheduler is fair, it reaches a couple to form a Triplet configuration within finite time. (b) Otherwise, the two robots at the corner of the SER try to move to a neighboring safe node (refer to Algorithm 4, Lines 4.14 to 4.15), if activated. As the scheduler is fair, at least one of them is activated within finite time and when activated, with positive probability (actually, a probability greater or equal to p(1p)), exactly one of them moves. In this case, the system reaches either a Triplet or Case 1. Hence, with positive probability, a configuration of type Triplet is reached in finite time. (c) There is no robot at the corner of the SER. In this case, the torus necessarily satisfies ℓ = L.

  1p)), exactly one of them moves and the configuration reached is either Triplet or Twin but with only one or two couples, that is one of the previous cases. Hence, we can conclude that, in this case, with positive probability, a configuration of type Triplet is reached in finite time. ✷ Lemma 7 If C is of type Quadruplet then, a configuration C ′ of type either Twin or Triplet is reached from C within finite time.

We recall that "with probability one" has the same meaning as "almost surely" or "almost certainly," but is different of "asymptotically almost surely," see[START_REF] Stroock | Probability theory : an analytic view[END_REF], page 186.

As explained in the model, in case where P is probabilistic, some of its executions may not terminate, even if the overall probability that such executions occur is 0.

Algorithm 10 Procedure 1stSpiral. then Move to Position (x -1, y) Recall that Algorithm 1 is made of three phases: SetUp, Tower, and Exploration. The first phase, SetUp, starts from any towerless configuration and ends in a ♦.Configuration. Moreover, this phase contains no configuration with a tower. (As a matter of fact, we show in Figure 16 the possible transitions between the different classes of configurations of SetUp; note that such transitions are either probabilistic or deterministic and may be performed in several steps.) The second phase, Tower, just consists in a single probabilistic transition (that may be performed in several steps) from a ♦.Configuration to the initial towered configuration of the Exploration phase. Finally, all configurations that appear during the Exploration phase contain a tower. Hence, we have the following property: Remark 3 The three phases of Algorithm 1 (SetUp, Tower, and Exploration) are unambiguous.

Consider any ♦.Configuration. Let u 1 and u 2 be the two occupied neighboring nodes having themselves two occupied neighboring nodes. Let r 1 and r 2 be the two robots located at u 1 and u 2 , respectively. During this phase, r 1 and r 2 try to move towards each other anytime they are activated; the other two robots do not move if activated. If either r 1 or r 2 , but not both, is activated, then a tower is created. If both r 1 and r 2 are activated simultaneously, then the following two events have positive probability to occur: either the system remains a ♦.Configuration (because r 1 and r 2 both decide to either move or not move) or a tower is created (because either r 1 or r 2 decides to move). As the scheduler is fair, r 1 and r 2 are activated regularly until a tower is created, and with probability 1, the initial towered configuration of the Exploration phase is eventually reached.

Then, from the initial configuration of the Exploration phase, robots * and o explore the torus in a fully deterministic manner. So, from such a configuration, the termination is guaranteed. Thus, we can conclude that starting from a ♦.Configuration, the torus is eventually explored with probability one.

Hence, the critical part of the algorithm is the SetUp phase, whose aims at converging to a ♦.Configuration starting from any initial (towerless) configuration. So, we now focus on this phase and show that, the convergence is obtained with probability one.

First, the SetUp phase exactly deals with the set of all towerless configurations. Now, by definition, we have:

Remark 4 The set of all towerless configurations is equal to the (disjoint) union of the following configuration sets:

1 The first part of the proof consists in showing that if the system is in a configuration of type Double-Trap1, Double-Trap2 or Triplet, then it (deterministically) reaches a ♦.Configuration in finite time.

In the following, we consider an arbitrary towerless configuration C.

Lemma 3 If C is of type Double-Trap2, then a configuration C ′ of type ♦.Configuration is reached from C within finite time.

Proof. When the configuration C is of type Double-Trap2, there is exactly one robot R that is allowed to move (refer to Algorithm 2, Line 8). R is the robot that has a neighboring robot and another robot at distance 2 on the same ring. Its destination is its adjacent free node towards the robot that is at distance 2.

As the scheduler is fair, R moves in finite time and then a configuration of type ♦.Configuration is reached.

Proof. When the configuration C is of type Double-Trap1, the only robot allowed to move is the robot R that is at the extremity of the 3-block having exactly one neighbor (refer to Algorithm 2, Line 5). Its destination is its adjacent free node on the ring containing a single robot. As the scheduler is fair, R moves (c) There is no robot at the corner of the SER. In this case, observe that all robots are located at different sides of the SER. Let d be the minimum distance between any occupied node and a corner of SER. The following subcases are then possible: i. There is a unique robot r that is at distance d from a corner of SER. r is the only robot allowed to move. Its destination is its adjacent free node towards the closest corner (refer to Lines from 6.11 to 6.13). Observe that by moving r becomes even close to the corner, thus r keeps being the only one enabled to move until it becomes neighbor of the closest corner. Hence, as the scheduler is fair, we retrieve Case 1a within finite time, and we are done. ii. There are two robots r 1 and r 2 that are at distance d from a corner.

A. If r 1 and r 2 are closest to the same corner c, then the two other robots, say r 3 and r 4 , move towards the corner that is common to their side of SER and the side of SER where either r 1 or r 2 are located, if activated (refer to Lines from 6.14 to 6.17). Note that since all robot are on the border of SER, r 3 and r 4 have different targets. Thus, as the scheduler is fair, a Twin configuration is reached in finite time and by Lemma 6, we are done. B. If r 1 and r 2 are closest to a corner of SER, but not the same then, then r 1 and r 2 are the only robots allowed to move. Their destination is their adjacent free node towards their closest corner (refer to Lines from 6.18 to 6.19). As the scheduler is fair, in finite time, either their both reach their target simultaneously and we retrieve Case 1b, or we retrieve Case 1a. Hence, from the previous cases, we are done. iii. There are three or four robots that are at distance d from a corner of SER. Observe that since that the configuration is not of type Identical, there is one or two corners that have only one robot at distance d from them. Such a robot is enabled to move and its destination is its closest corner (refer to Lines from 6.18 to 6.19). As the scheduler is fair, in finite time, we retrieve either Case 1a or Case 1b and we are done. 2. ℓ = L. In this case, according to the number of robots on L-rings, we can distinguish the following cases: (a) Every L-ring contains at most one robot. Every L-ring contains at most one robot. Let r 1 , r 2 , r 3 , and r 4 be the four robots. Observe that there are two robots, say r 1 and r 2 , that are on two parallel sides of SER that are on ℓ-rings. The robots allowed to move are r 3 and r 4 . They move towards a closest extremity of their side of SER (refer to Lines from 7.02 to 7.06). Note that by doing so, r 3 and r 4 keeps being allowed to move until they become on the same ℓ-ring as either r 1 or r 2 . Hence, as the scheduler is fair, Twin configuration is reached in finite time and by Lemma 6, we are done. (b) There is exactly one L-ring R that contains 2 robots. The robots that are alone on their L-ring move along their L-ring towards a closest free node that is adjacent to R (refer to Lines from 7.07 to 7.09). Observe that these robots keep the same target until one of them becomes on the same ℓ-ring as another robot. Then, in finite time, the system reaches either a Triplet or a Twin configuration depending of the activations decided by the fair scheduler. In the latter case, with a positive probability, a Triplet configuration is then reached in finite time by Lemma 6 and we are done. (c) There is exactly one L-ring R that contains 3 robots. The case is similar to the previous one, refer to Lines from 7.07 to 7.09: in finite time, the system reaches a Twin configuration and by Lemma 6, we are done. (d) There exist two L-rings that contain two robots. In this case, two cases are possible: i. There is a L-ring that contains two robots located at corners of SER. The robots that are at corners try to move, if activated, to their adjacent L-ring outside SER (note that there are only two robots at the corner of SER, otherwise the configuration is Twin) (refer to Lines