{'fraction_non_alphanumeric': 0.05672350319705483, 'fraction_numerical': 0.007314473939159078, 'mean_word_length': 3.93238561701111, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Wait-Free Gathering of Mobile Robots

The problem of gathering multiple mobile robots to a single location, is one of the fundamental problems in distributed coordination between autonomous robots. The problem has been studied and solved even for robots that are anonymous, disoriented, memoryless and operate in the semi-synchronous (ATOM) model. However all known solutions require the robots to be faulty-free except for the results of [Agmon and Peleg 2006] who solve the gathering problem in presence of one crash fault. This leaves open the question of whether gathering of correct robots can be achieved in the presence of multiple crash failures. We resolve the question in this paper and show how to solve gathering, when any number of robots may crash at any time during the algorithm, assuming strong multiplicity detection and chirality. In contrast it is known that for the more stronger byzantine faults, it is impossible to gather even in a 3-robot system if one robot is faulty. Our algorithm solves the gathering of correct robots in the semi-synchronous model where an adversary may stop any robot before reaching its desired destination. Further the algorithm is self-stabilizing as it achieves gathering starting from any configuration (except the bivalent configuration where deterministic gathering is impossible).


Introduction
Robot Networks. We consider autonomous robots that are endowed with visibility sensors (but that are otherwise unable to communicate) and motion actuators. Those robots must collaborate to solve a collective task, namely gathering, despite being limited with respect to input from the environment, asymmetry, memory, etc. The area where robots have to gather is modeled as a continuous two-dimensional Euclidean space, and the gathering task requires every robot to reach a single point that is unknown beforehand, and to remain there hereafter.
Robots operate in cycles that comprise look, compute, and move phases. The look phase consists in taking a snapshot of the other robots positions using its visibility sensors. In the compute phase, a robot computes a target destination among its neighbors, based on the previous observation. The move phase simply consists in moving toward the computed destination using motion actuators. We consider an asynchronous computing model, i.e., the ratio between the speed of the fastest robot and that of the slowest robot is finite but unbounded (and unknown to the robots), however each cycle is considered atomic (robots may nevertheless execute cycles concurrently). This model is referred to as the semi-synchronous ATOM model in the literature [21]. When cycle phases may not be atomic, it is possible for a robot to observe another robot while it moves, or to perform the computing (and moving) phase with an outdated observation. This non-atomic but still asynchronous model is known as the CORDA model [19]. Of course, all executions in the ATOM model are also valid in the CORDA model. So, impossibility results for the ATOM model remains true in the CORDA model, and protocols for the CORDA model are also valid for the ATOM model, but the converse is not true.
In addition to the temporal uncertainty resulting from system asynchrony, the lack of a common coordinate system leads to a second kind of uncertainty which is spatial: there is no common notion of distance (robots do not share a common metric system) or direction (robots do not have a common compass). Another aspect of spacial uncertainty stems from the common assumption that an adversary has the ability to stop a robot movement before it reaches its planned destination. This implies that the distance effectively travelled by a robot at each cycle of operation is unpredictable.
Finally, the robots that we consider here have weak capacities: they are anonymous (they execute the same protocol and have no mean to distinguish themselves from the others), oblivious (they have no memory that is persistent between two cycles). In some problem instances such as gathering, robots may share the same position, which is called a multiplicity point. The ability for a robot to detect multiplicity is crucial to solve some particular tasks. We distinguish weak and strong multiplicity detection. The weak multiplicity detector detects whether there is zero, one or more than one robot at a particular location. The strong multiplicity detector senses the exact number of robots at a particular location.
Fault-tolerance and Wait-freedom. As the output of an individual robot is its movement, faults in robot networks are characterized by the possibilities allowed for unexpected behavior. The most simple fault is the halting (or crash) fault (a robot simply stops moving forever). A halting fault-tolerant (or simply fault-tolerant) robot protocol permits robots that do not crash (that is, the correct robots) to properly complete a given task (such as gathering). The waitfreedom property is the strongest non-blocking guarantee in "classical" distributed computing [15], as a wait-free algorithm guarantees that every execution completes in a finite number of steps, even if halting faults or simply adversarial scheduling occur. Simply put, in the context of robot networks, an arbitrary and unexpected delay observed at one robot may not prevent other robots from making progress toward the solution (in our case, gathering), even if n − 1 robots are delayed or crashed (n being the number of robots).
Another kind of fault is the transient fault (that is, a fault of arbitrary nature that places the robot in some arbitrary state). Since we assume robots are oblivious (and do not remember their past states), a transient fault may simply put the robots in some arbitrary initial positions. A selfstabilizing robot protocol permits all robots to properly complete a given task after all transient faults are finished (that the whole set of robots has been placed in arbitrary locations). The most malicious kind of fault is that of Byzantine fault, which can make a robot move arbitrarily (both considering location and speed).
Related Work. The (fault-free) gathering problem was introduced in the seminal paper of [21] in the ATOM model. Deterministic gathering of 2 oblivious robots was proved to be impossible to solve in a deterministic setting [21], while deterministic gathering with at least 3 robots was shown to be feasible both in the ATOM [21] and CORDA [9] models. Randomization [12] or adding persistent memory to robots permit to solve 2-gathering both in ATOM [21] or CORDA model [5].
With the possibility of even a single Byzantine fault, gathering becomes impossible [1,16], even when considering more than 2 robots, the simple ATOM model, randomization capabilities, and persistent memory. So, positive results consider either weaker problems (such as convergence [7,5], that only requires robot to approach a single point, rather than reaching it) with Byzantine faults, or

Reference Model Chirality Multiplicity
Halting Self-Stabilizing Detection Faults [1] ATOM No Weak (binary) f ≤ 1 No [13] ATOM No Strong f = 0 If n is odd This paper ATOM Yes Strong f < n If not Bivalent  [1,13] consider deterministic gathering with faults in robot networks, both in the ATOM model. With respect to halting faults, Agmon and Peleg [1] solve gathering with at most one halting fault in a network where robots may not share the same chirality (that is, they may not agree about their handedness), yet assume that no two robots are located on the same position initially (so, the protocol is not self-stabilizing). Dieudonné and Petit [13] present a self-stabilizing algorithm for gathering, again without chirality assumption, but assuming that there is no halting fault and that the number of robots is odd.
The gathering problem has also been studied in models with other limitations, such as robots having limited visibility [4,14] or robots that are not dimensionless (i.e. they block both the motion and visibility of other robots) [10]. Another scenario that has been studied is when robots are given the additional capability of using a directional compass which is however subject to inaccuracies and failure [20].
Our Contribution. We investigate the possibility of handling more than one halting fault in robot networks in a deterministic setting. In more details, we present a deterministic protocol for gathering that can handle up to n − 1 halting faults (that is, the protocol is wait-free). It is known that deterministic gathering is impossible if the robots are equally distributed in two points on the plane (the so-called Bivalent configuration). We consider protocols for robots that start from any arbitrary configuration other than the (impossible) Bivalent one. Thus, our protocol recovers from any transient faults as particular initial configurations are unnecessary. We use the ATOM model as in [1,13], yet tolerate more halting faults and more potential initial configurations. The main additional assumption that we make is a common chirality for all robots that participate to the protocol. We also assume, as in [13], a strong multiplicity detection mechanism. Our results are summarized in table 1.
Our protocol is based on spatial invariants that are both simple to compute and are preserved by robot movements induced by the protocol. One of the most natural candidates for the case of gathering is the Weber point [22]. Given a set of points P , the Weber point c minimizes r∈P distance(x, r) over all points x in the plane. The Weber point has the key property of remaining unchanged under straight movements of any of the points towards or away from it. If the Weber point can be computed, it is simple to devise a robot protocol that solves gathering: all robots simply move toward the Weber point. Unfortunately, computing the Weber point is known to be difficult and was solved in special cases such as regular polygons [3], line [8], and a number of symmetric and regular configurations [6]. A key result of this paper is a technique to compute the Weber point of a newly defined class of configurations, referred in the sequel as quasi-regular configurations, which are less symmetric than both symmetric and regular configurations.
Using this building block, the protocol for gathering can then be informally described as follows: (i) if the configuration has some amount of symmetry, that is, it is symmetric, regular, or quasiregular, then the robots move to the Weber point, (ii) if the configuration is completely asymmetric, it is possible to unanimously elect one unique robot location and all robots may move towards this leader robot (or robots, in case of multiplicities). However these movements may not keep the leader invariant. Note that it is not possible to maintain a leader by moving individual robots in a preferred order (such a protocol would not be wait-free/crash-tolerant). Moreover, since the robots may be stopped by the adversary before reaching the destination, we risk forming the bivalent configuration from which the robots cannot recover and it would be impossible to achieve gathering. Thus, the algorithm involves several technicalities to ensure that the robots progress towards a gathered configuration in a wait-free manner, while avoiding the catastrophic bivalent configuration.

The Model and Notations
Robot Model: There are n robots modeled as points on a geometric plane. A robot can observe its environment and determine the location of other robots in the plane, relative to its own location. All robots are identical (and thus indistinguishable) and they follow the same algorithm. However each robot has its own local coordinates system and measure of unit distance (which may be distinct from that of other robots). The robots only share a common sense of handedness (i.e. they agree on the clockwise direction). Time is divided to discrete intervals called rounds and in each round a robot be either active or inactive. In each round, each active robot r makes exactly one step which consists of LOOK, COMPUTE and MOVE actions. During the LOOK stage, robot r gets a complete snap-shot containing the locations of every other robot in terms of the local coordinate system and unit distance used by robot r. (Note that multiple robots may occupy the same location in the plane and a robot can determine exactly how many robots are located at the same point.) During the COMPUTE stage, the robot executes its algorithm, using the snapshot as input and determines its next destination point. (Note that robots do not need to remember their previous steps.) During the MOVE stage, the robot moves towards the computed destination 1 . A move may end before the robot reaches its destination. However there exists an (arbitrarily small) constant δ > 0 such that if the destination point is closer than δ, the robot will reach it; otherwise, it will move a distance of at least ∆ towards its destination. A robot that is inactive in a round does not take any actions during that round. Each (correct) robot is active in infinitely many rounds.
We denote the above model of computation as AT OM [⋄M ] model (i.e. the ATOM model enhanced with strong multiplicity detection).
Fault Model: We consider the crash fault model. A robot is faulty if there is a time at which it stops taking actions (i.e. it crashes). However, a crashed robot remains visible to other robots in the system. A robot that does not crash is correct. An algorithm is f -resilient if it works correctly when the number of faulty robots does not exceed f < n. We may consider more general models of faults in which the adversary is allowed to fail subsets of robots that are not necessarily uniform. An adversary can thus be characterized using its faulty sets [17]: the set of subsets of robots it is allowed to fail during an execution. Sometimes, it is more convenient to describe adversaries using the set of their cores. A core [17] is a minimal subset of robots that can not all fail in any execution. For example, for the f -resilient adversary, any set of f + 1 robots is a core.
Notations: R = {r 1 , . . . , r n } is the set of robots and T is the set of positive natural numbers, denoting time instances. At any time τ ∈ T , the configuration of the set of robots is given by the multiset C R (τ ) = {p 1 , . . . , p n } where each p i ∈ R 2 . We shall drop the subscript R when it is 1 If the computed destination is the current location, then the robot does not move. obvious from context. Let P be the set of all possible configurations of n robots. Formally, P = R 2 n where R is the set of real numbers. A configuration is linear if all its robots lie on the same line.
Given any robot r, mul(r) denotes the multiplicity of the location occupied by r. Given a multiset of robot positions Q, we denote by U (Q) the corresponding set of positions in Q removing multiplicities (i.e. each point is U(Q) contains at least one robot). Given a configuration C, let sec(C) denote the smallest enclosing circle of the point set U (C). The center of a circle G is denoted by center(G). CH(Q) denotes the convex hull of the points in Q. Given two distinct points u and v on the plane, let line(u, v) denote the straight line passing through these points and (u, v) (resp. [u, v]) denote the open (resp. closed) interval containing all points in this line that lie between u and v. The half-line starting at point u (but excluding the point u) and passing through v is denoted by With respect to some point c ∈ R 2 \ {u, v}, the angle in the clockwise direction between line segments [c, u] and [c, v] is denoted by ∢(u, c, v). The Euclidean distance between u and v is denoted by |u, v|.

Some Definitions
Configurations may exhibit several kinds of symmetry. In this section, we consider a specific form of symmetry called rotational symmetry which we define in a precise sense and show how to quantify it. This is based on the concept of views [21], as described below.
Definition 1 (Views) Let C = {p 1 , . . . , p n } be a configuration of robots. Given a position p ∈ U (C), define the view of p, denoted V(p), as the expression of C in the polar coordinate system whose center is p and whose point (1, 0) is defined as follows. Let c = center(sec(C)). If (c = p), Note that in the definition above, the point (1, 0) is not uniquely defined, however the view of any point p ∈ C is uniquely defined. Based on the definition of views, we can define an equivalence relation ∽ r on the set of robot locations, as follows: The corresponding equivalence class for u is denoted by [u] r . The following definition formalizes the notion of rotational symmetricity.
Definition 2 (Rotational Symmetricity) The (rotational) symmetricity of a configuration C, denoted sym(C), is the cardinality of the biggest equivalence class defined by ∽ r on U (C). That is, Our definition of symmetricity differs slightly from the one presented in [11,21] but only for those configurations that contain either points of multiplicity or a point located in the center of their SEC. The following result follows from the definition of symmetricity. Lemma 3.1 Let C be a configuration with k = sym(C) > 1 and let c = center(sec(U (C))). For every u ∈ U (C) with (u = c), it holds that [u] r a k-gon with center c and whose corners have the same multiplicity.
Regularity: We now define some weaker forms of symmetry called regularity and quasi-regularity and show how to compute a unique gathering point (the so-called Weber point) in such configurations. If we consider any circle G that encloses the points in a configuration C, we may order the points by sweeping the circle G in a clockwise direction and ordering points on the same radius w.r.t. their distance from the center. This idea leads to the following definitions (extending the concepts in [2,18]).
• [Successor] The clockwise successor of p i ∈ C around c, denoted by S(p i , c) is equal to the point p j ∈ C defined as follows: The string of angles around c started in The greatest k for which SA is k-periodic is called the periodicity of SA and is denoted by per(SA). Definition 4 (Regularity) A configuration C of n points is regular if there exists a point c ∈ R 2 and ∃m > 1 such that per(SA(c)) = m > 1. In this case, the regularity of C, denoted reg(C), is equal to m. Otherwise, reg(C) = 1. The point c is called the center of regularity and is denoted by CR(C).
Definition 5 (Quasi Regularity) A configuration C of n points is quasi-regular (or Q-regular) iff there exist (1) a point c ∈ R 2 and (2) a regular configuration C ′ with center of regularity c which can be obtained from C be moving only points located at c if any. Formally, C is quasi-regular with center c ∈ R 2 iff ∃C ′ ∈ P such that reg(C ′ ) > 1, CR(C ′ ) = c and ∀p ∈ C ′ \ C, p = c. In this case, the quasi-regularity of C, denoted qreg(C) = reg(C ′ ) and the center of quasi-regularity denoted CQR(C) = c. If C is not quasi-regular then qreg(C) = 1.
Note that each configuration that is symmetric is also regular. More precisely, (sym(C) > 1) ⇒ (reg(C) = sym(C)). Each regular configuration is also quasi-regular (with C ′ = C).
Definition 6 (Weber Points) The Weber points of a configuration C, denoted W P (C), are the set of points that minimize the sum of distances with points of C. Formally, W P (C) = argmin Non-linear configurations are known to have a unique Weber point while linear configurations may have infinitely many Weber points. The Weber points of a linear configuration C are points in the interval [min(M ed(C)), max(M ed(C))], where M ed(C) the set of median points. If a linear configuration C has a single median, then this point is the unique Weber point W P (C). We now show how to compute the Weber-point of some special non-linear configurations.

Computation of Weber Points
Given a set of points C and any arbitrary point p ∈ R 2 , we define SEC(C, p) as the smallest circle centered at c that encloses all points in C. Given a point x ∈ C and some α ∈ [0, 2π], the successor of x with respect to point p and angle α, denoted by S(x, p, α) is the point y such that |p, x| = |p, y| and ∢(x, p, y) = α.
By definition, the points of W P (C) are those points x that minimize n i=1 |x, p i |. Moreover, the points of Y are those that minimize n i=1 (|x, p ′ i | − |x, p i |). Hence, the points of X = Y ∩ W P (C) minimize the two sums and minimize their sum also. It follows that the points that minimize n i=1 |x, p ′ i | are those in X. Thus, W P (C ′ ) = X.
Corollary 3.1 If C is a configuration with a unique Weber point c and if C ′ is a configuration that is obtained from C by moving robots towards c, then the Weber point of C ′ is also unique and is equal to c.
In the following Lemma we show that the center of quasi-regularity of a configuration is also its Weber point. Proof : Let c = CQR(C) and qreg(C) = k > 1. We have to prove that c = W P (C). By definition of quasi-regularity, there exists a regular configuration C ′ whose center of regularity is c and which can be obtained from C by moving only points located at c if any. Seen in the reverse sense, C can obtained from C ′ under straight movement of points towards c. Hence, by Corollary 3.1, W P (C) = c if and only if W P (C ′ ) = c.
Therefore, it suffices to prove that the center of regularity of any configuration C ′ is also its Weber point. This claim was already proved in [6] but for a slightly different definition of regularity that does not allow the presence of multiplicity points nor points lying on c. However, the argument is the same and does not depend on these factors. We reproduce it here for completeness. Let C ′′ be a configuration obtained from C ′ as follows: For each point p ∈ C not located at c, move p towards the point that is at the intersection of HF (c, p) and SEC(C, c). Clearly, the obtained configuration C ′′ is symmetric with center of symmetricity c and sym(C ′′ ) = reg(C ′ ). Note that C ′ can be obtained from C ′′ only by moving points in C ′′ towards c. Again, by Corollary 3.1 implies that W P (C ′′ ) = c implies W P (C ′ ) = c.
To finishes our proof, it suffices then to show that the center of R-symmetricity of any configuration C ′′ is also its Weber point. Assume for contradiction that W P (C ′′ ) = c ′ = c. Let k = sym(C ′′ ) > 1. Let P k by the regular k-gon whose center is c and one of whose vertices is c ′ . By symmetricity, if c ′ is a Weber point of C ′′ , so are all points of P k . But the Weber point of a non-linear configuration is necessarily unique -A contradiction!
The following lemma proves a property about regular configurations: Lemma 3.4 Let C be any configuration and let p ∈ R 2 . Let m > 1. C is regular with center p and reg(C) = m iff ∀x = p ∈ R 2 : ∀k ∈ [1, m] : ∀y = S(x, p, 2kπ m ) : it holds that HF (p, x) and HF (p, y) contain the same number of robots of C.
Proof : C is regular with reg(C) = m and center p iff there exists a configuration C ′ that is symmetric with the same center of regularity and such that C can be obtained from C ′ by moving robots of C ′ towards p without reaching it. Moreover sym(C ′ ) = m.
Fix x, y ∈ R 2 such that y = S(x, p, 2kπ m ) for some k ∈ [1, m]. We have to prove that HF (p, x) and HF (p, y) contain the same number of robots of C. But observe that the number of robots in HF (p, x) and HF (p, y) remains invariant when we transform C ′ into C as robots are allowed to move only towards p without reaching it. So no robot joins or leaves either HF (p, x) or HF (p, y). Hence,to prove our claim it suffices to show that HF (p, x) and HF (p, y) contain the same number of robots of C ′ .
Since sym(C ′ ) = m, it follows that C ′ remains invariant if we rotate it around p with an angle of 2kπ m . Note that HF (p, x) can be seen as the result of rotating HF (p, y) by an angle of 2kπ m . Hence HF (p, x) contains the same number of robots of C ′ as HF (p, y). This proves the lemma.
Definition 7 Let C a configuration with |U (C)| > 1 and let p ∈ C. Let m > 1. We define X m (C, p) as the following set of points {x ∈ sec(C, p) | ∃k ∈ [1, m] : ∃y ∈ S(x, p, 2kπ m ) : (p, y] contains at least one robot}. For each point x ∈ X m (C, p), let loc(C, x, p) (or loc(C, x)) denote the number of robots of C that are located in (p, x] and let obj(C, x) denote max{loc(C, y)|(y = S(x, p, 2kπ m )) ∧ (k ∈ [1, m])}.
Lemma 3.5 Given a configuration C and a point p ∈ C, C is q-regular with center p and qreg(C) = m > 1 iff mult(p) ≥ x∈Xm(C,p) (obj(C, x) − loc(C, x)) (α) Proof : According to Definition 4, C is q-regular with center p and qreg(C) = m iff (i) there exists a configuration C ′ that is regular with center p, (ii) reg(C ′ ) = m and (iii) C can be transformed into C ′ by moving only robots located at p. To prove the lemma it suffices to show that (i)∧(ii)∧(iii) ⇔ (α).
⇐) Assume (α) holds. For each x ∈ X m (C, p), we move (obj(C, x) − loc(C, x)) robots from p to x. Since (α) is satisfied, there are enough robots located in p to perform this action. Let C ′ be the resulting configuration. This proves (iii). Note that X m (C ′ , p) = X m (C, p).
⇒) Assume (i) ∧ (ii) ∧ (iii). Since C ′ can be obtained from C by moving only robots located at p according to (iii), it follows that X m (C, p) ⊆ X m (C′, p). Moreover, Since C ′ is regular with center p and reg(C ′ ) = m, it holds according to Lemma 3.4 that ∀x ∈ X m (C, p) : ∀k ∈ [1, m] : ∀y ∈ S(x, p, 2kπ m ) : loc(C ′ , x) = loc(C ′ , y). But loc(C ′ , y) ≥ loc(C, y) according to Equation (). Hence loc(C ′ , x) ≥ loc(C, y). It follows that: But all the robots that are in (loc(C ′ , x) − loc(C, x)) moved there from p. Consequently: We now state the main result of this section.
Theorem 3.1 Given a non-linear configuration C of n robots, there exists an algorithm that detects if C is quasi-regular and if so it outputs its center of q-regularity CQR(C).
Proof : As shown in Lemma 3.3, CQR(C) = W P (C) hence it is unique. If W P (C) ∈ C, then it can be found by applying Lemma 3.5 as follows: for each p ∈ C we test p is the center of q-regularity of C. Otherwise, W P (C) ∈ C which means that C is regular. Consequently, W P (C) can be computed as shown in [6].

Classes of Configurations
In the gathering algorithm, robots compute their next destinations based on the current configuration. Before presenting the algorithm, we present a classification of the robot configurations which will simplify the algorithm description. In the following, we formally define six classes of configurations and prove that they constitute a partition of the set P of all possible configurations of n robots.
Bivalent(B) B = {C ∈ P | (∀u ∈ U (C) : mul(u) = n/2)}. B is the set of configurations where the robots are equally distributed over two points in the space.
Multiple (M) M = {C ∈ P | ∃u ∈ U (C) : ∀v = u ∈ U (C) : mul(v) < mul(u)}. A configuration C belongs to M if it has a point u whose multiplicity is greater than that of any other distinct point in C.
We define the subsets L1W and L2W of colinear configurations depending on whether their Weber point is unique or not. That is, Let X = {B, M, L, QR, A}. It is easy to see that X is a partition of P. By definition, the classes are mutually disjoint. All linear configurations belong to the set B ∪ M ∪ L. For a non-linear configuration C either sym(C) > 1 which implies C ∈ QR ∪ B ∪ M, or sym(C) = 1 which implies that C ∈ A ∪ B ∪ M. Thus X = P.
The notion of safe points is important because any safe point can be used as a gathering point without the possibility that the robots form the bivalent B configuration while moving towards it. We can show the following properties for safe points. Proof : Let C be a non linear configuration. We say that Q ⊆ C is a quorum iff: (i) |Q| ≥ ⌊n/2⌋+1 and (ii) all points of Q are collinear and Q is maximal for this property, that is, for any Q ′ ⊃ Q, the points of Q ′ are not collinear. Let line(Q) denote the line in which are located the points of Q.
Let Q 1 and Q 2 any two distinct quorums of C. Condition (i) implies that Q 1 and Q 2 intersect, i.e. Q 1 ∩ Q 2 = ∅ and the maximality condition in (ii) implies that line(Q 1 ) = line(Q 2 ).
We show in the following that any point that is not safe belongs necessarily to a quorum. Let p ∈ C that is not free. We prove the existence of quorum Q to which p belongs. Since p is not safe, there exists q ∈ R 2 \ {p} such that HF (p, q) contains at least (⌈n/2⌉) robots located in it. Hence, p ∪ HF (p, q) contains at least ⌈n/2⌉ + 1 robots. Let S denote the multiset of positions of these robots. Since (|S| ≥ ⌈n/2⌉ + 1) and the points of S are collinear, there exists a set Q with Q ⊇ S that is a quorum with p ∈ Q.
We prove the lemma by contradiction. Assume that no point of C is safe, i.e. each point belongs to a quorum. This implies, as C is not linear, that there are at least two distinct quorums because a single quorum cannot contain all elements of C, otherwise the configuration would be linear. Let Q 1 and Q 2 be any two quorums of C with Q 1 = Q 2 and let p be a point in Q 1 ∩ Q 2 . Since p is not safe according to the contradiction assumption, there exists some q ∈ R 2 \ {p} such that HF (p, q) contains at least ⌈n/2⌉ robots positions. Denote by X the multiset containing these positions. Note that |X| ≥ ⌈n/2⌉ As Q 1 = Q 2 , it follows according to the maximality of property (ii) of quorums that line(Q 1 ) = line(Q 2 ). Hence, either line(p, q) = line(Q 1 ) or line(p, q) = line(Q 2 ). Assume w.l.o.g that line(p, q) = line(Q 1 ). Since p ∈ line(p, q), p ∈ Q 1 and line(p, q) = line(Q 1 ) it follows that line(p, q) ∩ line(Q 1 ) = {p}. Hence, the robots positions that are in HF (p, q) do not belong to Q 1 which means that X ∩ Q 1 = ∅. Hence, |X ∪ Q 1 | = |X| + |Q 1 | ≥ (⌈n/2⌉) + (⌊n/2⌋ + 1). That is |X ∪ Q 1 | ≥ n + 1. But |X ∪ Q 1 | ⊆ C, a contradiction! Thus the lemma holds. Proof : Assume towards contradiction that there exists a position p ∈ C that is safe. Since C is linear, this means that |{q ∈ C | q < p}| ≤ (⌈n/2⌉ − 1) and |{q ∈ C | q > p}| ≤ (⌈n/2⌉ − 1).
But C ∈ B ∪ L2W, it follows that C has two distinct median positions, let them be u 1 and u 2 and assume that u 1 < u 2 . It holds that either (u 2 > p) or (u 1 < p). Assume w.l.o.g. that (u 1 < p). Since u 1 is a median position in C, it holds that |{q ∈ C | q ≤ u 1 }| ≥ ⌈n/2⌉. Hence, as u 1 < p, it follows that |{q ∈ C | q < p}| ≥ ⌈n/2⌉; A Contradiction!

The Algorithm
The following lemma is a simple generalization of Lemma 3.1 in [1] that takes into account configurations containing multiplicity points and general adversaries characterized using their cores. Given a configuration P , an algorithm A, denote by M (P, A) the set of positions of robots that A instructs to move in P [1].
Lemma 5.1 A convergence or gathering algorithm A is tolerant against an adversary X only if at each configuration P , either (1) M (P, A) is a superset of a core of X or (2) |U (P \ M (P, A))| ≤ 1).
Proof : The proof is similar to that of [1]. Consider a configuration of P . Let M and M denote respectively the subsets M (P, A) and P \ M (P, A). Assume for contradiction that (1) M is not a superset of a core of X , i.e. M is a faulty set and (2) |U (M )| ≥ 2. Hence, X is allowed to fail the robots of M when the current configuration is P (we assume that all robots of M are correct). Since no robot in M is allowed to move, the next configuration is identical to P . Therefore, the system will remain in the configuration P indefinitely. But |U (M )| ≥ 2, thus the robots of M remain indefinitely separated from each others and no convergence nor gathering can be ever achieved. This contradicts the assumption of A being a convergence or gathering algorithm.
As a consequence, since we want our algorithm to be wait-free ((n − 1)-tolerant), it must be the case that at each configuration C, there is at most one location c ∈ U (C) such that the robots at c are allowed to stay in the same position when activated, while all other robots must choose a destination different from the one they are currently occupying. The algorithm must also ensure that robots never reach the configuration B, due to the following impossibility result. Lemma 5.2 [13] Starting from a configuration of type B, there is no algorithm that achieves gathering even in fault-free AT OM [⋄M ] model.
We now define more precisely the objective of a fault-tolerant gathering algorithm. At any time τ during the execution of the algorithm, we define F (r, τ ) = true if robot r has crashed at time t i ≤ τ . The set of non-faulty robots at time τ is denoted by Live(R, τ ) = {r i ∈ R|F (r i , τ ) = f alse}.

Gathering Algorithm
We now describe the algorithm in terms of actions taken by a robot r based on the current configuration and the position of the robot r within the configuration. A more technical description is given in Figure 2.
Configuration C ∈ M Let c be the unique point of maximum multiplicity in C. If robot r is located at c, it does not move. Otherwise, if there are no robots between r and c, robot r moves directly towards c and if not, it does a side-step i.e. it moves to the closest point d on a half-line HF (c, d) such that the angle between half-line HF (c, d) and half-line HF (c, r) is less than or equal to 1/3 of the angle between half-line HF (c, p) and half-line HF (c, r), for any other robot location p ∈ C. This ensures the robot does not collide with another robot, i.e. it does not create a new point of maximum Input: C (The observed configuration during the precedent look phase). Output: The destination of the robot. compute(): (1) r ← My position in C return d Figure 2: Gathering Algorithm: compute Phase multiplicity. Note that there may be multiple robots colocated with r, these robot may make the same move as r. However the value of mul(r) would never increase unless r reaches the point c.
Thus, the algorithm ensures that the robots remain in a configuration of type M until gathering is achieved.
Configuration C ∈ L1W By definition, we know that configuration C contains a unique Weber-point c which is also the median and can be computed easily. Each robot r moves directly towards the Weber point c which remains invariant during the movement. Eventually the configuration changes to M or a gathered configuration.
Configuration C ∈ QR In this case, robot r moves to the center c of quasi-regularity of C (which is also the Weber-point).
Thus, the Weber-point c remains invariant during the movement and eventually the configuration changes to M or a gathered configuration.

Configuration C ∈ A
Since C is not linear, we know that there exists a safe point in U (C). When there are multiple safe points, the algorithm selects a unique point c from among the safe points in U(C). This is always possible since the configuration is asymmetric (i.e. the view of each point is unique). The algorithm chooses the point c based on the multiplicity(c), the sum of distances of all other robots to c, and finally the view of c (in this order, and maximizing the first parameter, minimizing the second parameter and maximizing the third parameter). Each robot r moves towards this unique point c. We will show that the configuration C ′ obtained after one step of the algorithm is of type M, QR, L1W, or A (but not B or L2W). Further if the next configuration is again of type A then either the maximum multiplicity increases or the minimum sum of distance decreases. This ensures that the algorithm converges towards a configuration of type M or a gathered configuration.

Configuration C ∈ L2W
In this case, there are at least 4 distinct points in the configuration. The algorithm instructs the robots at the two end-points of the line to move away from the line. Any robot that is not located in one of the end-points is instructed to move towards the center of the line. If any of the robots at the end-points move then the next configuration would be non-linear and thus, the algorithm switches to one of the other cases above. Otherwise, if the robots are the end-points never move (i.e. they are crashed) then the configuration remains linear but the sum of distances between correct robots decreases, and the robots would eventually converge to a gathered configuration or a configuration of type M.

Proof of Correctness
We now show that starting from any configuration except the bivalent configuration B, the algorithm described in Figure 2 eventually forms a gathered configuration. The proof is divided into several parts, each dealing with configurations of a different type.

Configurations of type M
There exists a time τ ′ > τ such that gathered(R, τ )=true.
Proof : Let elected(τ ) be the destination chosen by the robots in configuration C(τ ), i.e. elected(τ ) = argmax p∈C(τ ) mul(p). A robot position p ∈ C(τ ) is said to be free with respect to elected(τ ) if no robot is located in the interval (p, c). The lemma follows from the following two claims that we prove below: C1: (C(τ ) ∈ M) ⇒ ((C(τ + 1) ∈ M) ∧ (elected(τ + 1) = elected(τ ))) Proof of C1: Let c = elected(τ ) be the point of maximum multiplicity in the configuration C(τ ). We need to show that c remains the point of maximum multiplicity in C(τ + 1). In fact we show a stronger result that no two robots that were in distinct locations at τ can be at the same location at time τ + 1, unless the robots are at c. Let us assume the contrary, i.e. let r 1 and r 2 be robots that occupied distinct locations in C(τ ) but occupy the same location p = c in C(τ + 1). Note that neither of the robots r 1 and r 2 are located at c at time τ (since otherwise the algorithm would instruct them to remain at c and they would not be at p at τ + 1).
According to the algorithm any robot r in configuration C(τ ) ∈ M can make two possible moves: (i) either robot r moves directly towards c (Line (5) of algorithm) or, (ii) robot r moves to a point d such that rcd is an isosceles triangle with central angle 0 < θ < π/3 at c (Line (9) of algorithm). If both the robots r 1 and r 2 both make move of type (i), then they are distinct free points and in this case their paths may not intersect except at c. Otherwise, suppose one of the robots (say r 1 ) makes a move of type (ii) directly towards a point d. Consider the triangle r 2 cd and let ∢(r 2 , c, d) = θ. The other robot r 2 is located either on the half-line HF (c, r 1 ) or, on a different half-line HF (c, r 2 ) which forms an angle greater than 3 * θ with the half-line HF (c, r 1 ) w.r.t. point c. In the second case, the path of robot r 2 will never intersect the line segment between c and d.
In the first case, either robot r 2 is on a free point (and thus, it will move on the line segment [c, r 2 ] which does not intersect the line segment [c, d]) or robot r 2 is not free and thus it makes a move on a line segment parallel to [c, d]. In both cases, there is no common point p in the path of the two robots.
Proof of C2: In this case, if c = elected(τ ) is the point of maximum multiplicity in C(τ ) then c is the unique point of maximum multiplicity in all subsequent configurations. Whenever a robot on a free point is activated it moves closer to the point c. Whenever a blocked (i.e. not free) robot is activated, at least one robot moves from a blocked position to a free point. Once a robot r moves to a free point at time τ i , it may be blocked in subsequent steps by only robots that moved with robot r in that same time step (i.e. these robots were live at that time step). Thus an adversary can prevent a non-faulty robot r from reaching point c only by changing a live robot to a crashed robot after each step in which robot r is activated. After a finite time, the adversary will run out of live robots. Thus all live robots will eventually reach c. Once a robot reaches c, the algorithm never instructs the robot to move (since c is the unique point of maximum multiplicity). Thus, gathered(R, τ ) will be true at that time.
This proves the claim.
Proof of C3: Assume that (∀τ ′ ≥ τ : C(τ ′ ) ∈ A). We have to prove that: ∃τ g ≥ τ : ∀τ ′ ≥ τ g : (C(τ ′ )) = C(τ )) That is, the configuration does not change after τ g which implies the existence of a time after τ g at which all the live robots lie on the same position. That is ∃τ c ≥ τ g : gathered(R, τ c ) = true. The claim follows from claim C2 above. There exists a time τ 1 ≥ τ after which φ().mult cannot increase since the multiplicity of points is upper bounded by n. Moreover, there exists a time Lemma 5.9 Let C(τ ) ∈ L2W. There exists a time τ c > τ such that (C(τ c ) ∈ M ∪ L1W ∪ QR ∪ A) ∨ (gathered(R, τ c ) = true).
But since C(τ ) ∈ L2W and Lemma 5.7 says that a configuration of type B cannot come after a configuration of type L2W, it follows that: ∀τ ′ ≥ τ : (C(τ ′ ) ∈ L2W) ∧ (gathered(R, τ ′ ) = f alse) According to Lemma 5.8, this is only possible if the robots located at the endpoints are never activated, which means that they are all faulty. Hence, the center of the configuration c = center(C(τ )) remains constant during all the execution and all correct robots eventually reach this point (line 18 of the algorithm). Hence, there is a time τ c > τ at which all correct robots are located at c. Thus, gathered(R, τ c ) = true. A contradiction.