Compatibility of Convergence Algorithms for Autonomous Mobile Robots (Extended Abstract)

Abstract

We investigate autonomous mobile robots in the Euclidean plane. A robot has a function called target function to decide the destination from the robots’ positions, and operates in Look-Compute-Move cycles, i.e., identifies the robots’ positions, computes the destination by the target function, and then moves there. Robots can have different target functions. Let $\varPhi$ and $\varPi$ be a set of target functions and a problem, respectively. If the robots whose target functions are chosen from $\varPhi$ always solve $\varPi$, we say that $\varPhi$ is compatible with respect to $\varPi$. Suppose that $\varPhi$ is compatible with respect to $\varPi$. Then two swarms controlled by (possibly different) target functions in $\varPhi$ can merge to form a larger swarm, and a broken robot can be replaced with another robot with any target function in $\varPhi$, keeping the correctness of solving $\varPi$. We investigate the convergence, the gathering, and some fault tolerant convergence problems, assuming crash failures, from the view point of compatibility.

Due to the space limitation, we omit most of the proofs and some contributions. The full version of the paper [4] contains them.

1 Introduction

Over the last three decades, swarms of autonomous mobile robots have obtained much attention in a variety of contexts. Among them is understanding solvable problems by a swarm consisting of many simple and identical robots in a distributed manner, which has been constantly attracting researchers in distributed computing society [1,2,3, 5, 6, 8,9,10,11,12,13,14,15,16,17,18,19,20].

Many of the works mentioned above adopt the following robot model. The robots look identical and indistinguishable. Each robot is represented by a point that moves in the Euclidean plane. It lacks identifier and communication devices, and operates in Look-Compute-Move cycles. When a robot starts a cycle, it identifies the multiset of the robots’ positions in its local x-y coordinate system such that it is right-handed, and its origin is always the position of the robot, computes the destination point using a target function¹ based only on the multiset identified, and then moves towards the target position. If each cycle starts at a time t and finishes, reaching the target position, before (not including) $t+1$, for some integer t, the scheduler is said to be semi-synchronous ($\mathcal{SSYNC}$). If cycles can start and end any time (even on the way to the target point), it is asynchronous ($\mathcal{ASYNC}$).

This paper investigates several convergence problems, e.g., [2, 8,9,10, 13, 14, 16, 18]. The simplest convergence problem requires the robots to converge to a single point. For the $\mathcal{SSYNC}$ model, the problem is solvable for robots with unlimited visibility [18], and is also solvable for robots with limited visibility [2].

Under the $\mathcal{ASYNC}$ model, it is solvable by a target function called CoG, which always outputs the center of gravity of the robots’ positions [8]. In [8], the authors also showed that CoG correctly works under the sudden-stop model, under which the movement of a robot towards the center of gravity might stop on the way after traversing at least some fixed distance. This implies that the robots can correctly converge to a point, even when they are controlled by different target functions as long as they always move robots towards the current center of gravity over distance at least some fixed constant. This idea is extended in [10]: The authors proposed the $\delta$-inner property² of target functions, and showed that the robot system converges to a point if all robots take $\delta$-inner target functions, provided $\delta \in (0,1/2]$. Finally [16] gives a convergence algorithm for robots with limited visibility under the $\mathcal{ASYNC}$ model.

Consider a problem $\varPi$ and a set of target functions $\varPhi$. If the robots whose target functions are chosen from $\varPhi$ always solve $\varPi$, we say that $\varPhi$ is compatible with respect to $\varPi$. For example, every (non-empty) set of (1/3)-inner functions is compatible with respect to the convergence problem [10].

If a singleton $\{ \phi \}$ is compatible with respect to $\varPi$, we abuse to say that target function $\phi$ is an algorithm³ for $\varPi$. If a set $\varPhi$ of target functions is compatible with respect to $\varPi$, every target function $\phi \in \varPhi$ is an algorithm for $\varPi$. (The converse is not always true.) Thus there is an algorithm for $\varPi$, if and only if there is a compatible set $\varPhi$ with respect to $\varPi$. We say that a problem $\varPi$ is solvable, if there is a compatible set $\varPhi$ with respect to $\varPi$, meaning that there is an algorithm for $\varPi$.

We would like to find a large compatible set $\varPhi$ with respect to $\varPi$. That $\varPi$ has a large compatible set with respect to $\varPi$ implies that $\varPi$ has many algorithms. The difficulty of problems might be compared by the sizes of their compatible sets. A problem $\varPi$ with a large compatible set $\varPhi$ seems to have some practical merits. Two swarms both of which are controlled by target functions in $\varPhi$ (which may be produced by different makers) can merge to form a larger swarm, keeping the correctness of solving $\varPi$. When a robot breaks down, we can safely replace it with another robot, as long as it is controlled by a target function in $\varPhi$.

Fault Tolerant Convergence Problems. This paper investigates three fault-tolerant convergence problems, besides the convergence and the gathering problems. We consider only crash faults: A faulty robot can stop functioning at any time, becoming permanently inactive. A faulty robot may not cause a malfunction, forever. We cannot distinguish such a robot from non-faulty ones. Let n and $f (\le n-1)$ be the number of robots and the number of faulty robots.

The fault-tolerant (n, f)-convergence problem (FC(f)) is the problem to find an algorithm which ensures that, as long as at most f robots are faulty, all non-faulty robots converge to a single point. The fault-tolerant (n, f)-convergence problem to f points (FC(f)-PO) is the problem to find an algorithm which ensures that, as long as at most f robots are faulty, all robots (including faulty ones) converge to at most f points. All non-faulty robots need not converge to the same point. If f faulty robots have crashed at different positions, each non-faulty robot must converge to one of the faulty robots. The fault-tolerant (n, f)-convergence problem to a convex f-gon (FC(f)-CP) is the problem to find an algorithm which ensures that, as long as at most f robots are faulty, the convex hull of the positions of all robots (including faulty ones) converges to a convex h-gon CH for some $h \le f$, in such a way that, for each vertex of CH, there is a robot that converges to the vertex.

Since an algorithm for FC(1)-PO solves FC(1), the former is not easier than the latter. (Note that for $f \ge 2$, an algorithm for FC(f)-PO may not solve FC(f).) Since an algorithm for FC(f)-PO solves FC(f)-CP, again the former is not easier than the latter. In [8], the authors showed that, for all $f \le n-2$, CoG is an algorithm for FC(f) under the $\mathcal{ASYNC}$ model. As far as we know, FC(f)-PO and FC(f)-CP have not been investigated so far.

Gathering Problem. The gathering problem requires the robots to gather in the exactly the same location. For $\mathcal{SSYNC}$, the gathering problem is not solvable if $n = 2$. If $n > 2$, it is solvable, provided that all robots initially occupy distinct positions [18]. For $\mathcal{ASYNC}$, the same results hold [7]. The gathering problem has been investigated under a variety of assumptions [1, 5, 7, 11,12,13,14].

Contributions. Let R be the set of real numbers. Formally, a target function $\phi$ is a function from $(R^2)^n$ to $R^2 \cup \{ \bot \}$ for all $n \ge 1$ such that $\phi (P) = \bot$ if and only if $(0,0) \not \in P$. Here, $\bot$ is a special symbol to denote that $(0,0) \not \in P$. Suppose that a robot r identifies a multiset P of n points, which are the positions of the robots in its local x-y coordinate system Z, in Look phase. Then $(0,0) \in P$.⁴ Using its target function $\phi$, r computes the target point $\boldsymbol{x} = \phi (P)$ in Compute phase. Then it moves to $\boldsymbol{x}~(\not = \bot )$ in Z in Move phase.

Let the convex hull and the center of gravity of P be CH(P) and g(P), respectively. For any $0 \le d$, let $d * CH(P) = \{ d \boldsymbol{x} + (1-d)g(P) : \boldsymbol{x} \in CH(P)\}$. The scale $\alpha (\phi )$ of a target function $\phi$ is defined by

$$ \alpha (\phi ) = \sup _{P \in (R^2)^n} \alpha (\phi ,P), $$

where $\alpha (\phi ,P)$ is the smallest d satisfying $\phi (P) \in d * (CH(P))$.⁵ Then the scale of a set $\varPhi$ of target functions is defined by

$$ \alpha (\varPhi ) = \sup _{\phi \in \varPhi } \alpha (\phi ). $$

The only target function $\phi$ satisfying $\alpha (\phi ) = 0$ is CoG. Thus the set $\varPhi$ of target functions satisfying $\alpha (\varPhi ) = 0$ is a singleton $\{ \textrm{CoG} \}$. The idea of scale is similar to that of the $\delta$-inner property in [10], and more directly embodies the idea behind the $\delta$-inner target function.

Our contributions are summarized in Table 1. For example, the entry of Convergence and $\alpha (\phi ) = 0$ is A. Thus $\{ \textrm{CoG} \}$ is compatible with respect to the convergence problem, or CoG is an algorithm for the convergence problem, as [8] shows. Not only the case $\alpha (\phi ) = 0$, but also the case $0< \alpha (\varPhi ) < 1$, every $\varPhi$ is compatible with respect to the convergence problem.

Table 1. The compatibility of a set $\varPhi$ of target functions with respect to a problem $\varPi$, taking its scale $\alpha (\varPhi )$ as a parameter. Each entry contains the status A, E, N, or ? of the compatibility of $\varPhi$ with respect to $\varPi$ (and the theorem/corollary/observation/citation number establishing the result in parentheses). Letter ‘A’ means that every $\varPhi$ such that $\alpha (\varPhi )$ is in the range is compatible with respect to $\varPi$. Letter ‘N’ means that any $\varPhi$ such that $\alpha (\varPhi )$ is in the range is not compatible with respect to $\varPi$, which indicates the absence of an algorithm. Letter ‘E’ means that some $\varPhi$ is compatible, while some other is not, which indicates the existence of an algorithm. Letter ‘?’ means that the answer is unknown.

Organization. After introducing the robot model in Sect. 2, we investigate the convergence problem in Sect. 3. In Sect. 4, we discuss the compatibilities of two convergence problems FC(1) and FC(1)-PO. Sections 5 and 6 respectively investigate the compatibilities of FC(f) and FC(f)-CP for $f \ge 2$. Section 7 first shows that a target function $\phi$ is an algorithm for FC(f)-PO for $f \ge 2$, only if $\alpha (\phi ) \ge 1$. We then present an algorithm $\psi _{(n,2)}$ for FC(2)-PO. Section 8 investigates the gathering problem to show the difference between this and the convergence problems. We conclude the paper in Sect. 9.

2 The Model

Consider a robot system $\mathcal R$ consisting of n robots $r_1, r_2, \ldots , r_n$. Each robot $r_i$ has its own unit of length, and a local compass defining an local x-y coordinate system $Z_i$, which is assumed to be right-handed and self-centric, i.e., its origin (0, 0) is always the position of $r_i$. We also assume that $r_i$ has the strong multiplicity detection capability, i.e., it can count the number of robots resides at a point. Given a target function $\phi _i$, each robot $r_i \in \mathcal{R}$ repeatedly executes a Look-Compute-Move cycle:

• Look: Robot $r_i$ identifies the multiset P of the robots’ positions (including the one of $r_i$) in $Z_i$. Since $r_i$ has the strong multiplicity detection capability, it can identify P not only distinct positions of P.

• Compute: Robot $r_i$ computes $\boldsymbol{x}_i = \phi _i(P)$. (We do not mind even if $\phi _i$ is not computable. We simply assume that $\phi _i(P)$ is given by an oracle.)

• Move: Robot $r_i$ moves to $\boldsymbol{x}_i$. We assume that $r_i$ always reaches $\boldsymbol{x}_i$ before this Move phase ends.

We assume a discrete time $0, 1, \ldots$. At each time $t \ge 0$, the scheduler activates some unpredictable subset (that may be none or all) of robots. Then activated robots execute a cycle which starts at t and ends before (not including) $t+1$ (unless it has crashed), i.e., the scheduler is semi-synchronous ($\mathcal{SSYNC}$). Let $Z_0$ be the global x-y coordinate system, which is right-handed and is not accessible by any robot $r_i$. The coordinate transformation from $Z_i$ to $Z_0$ is denoted by $\gamma _i$. We use $Z_0$ and $\gamma _i$ just for the purpose of explanation.

The position of robot $r_i$ at time t in $Z_0$ is denoted by $\boldsymbol{x}_t(r_i)$. Then $P_t = \{ \boldsymbol{x}_t(r_i) : 1 \le i \le n \}$ is a multiset representing the positions of all robots at time t, and is called the configuration at t.

Given an initial configuration $P_0$, an assignment $\mathcal A$ of a target function $\phi _i$ to each robot $r_i$, and an $\mathcal SSYNC$ activation schedule, the execution of $\mathcal R$ is a sequence $\mathcal{E}: P_0, P_1, \ldots , P_t, \ldots$ of configurations starting from $P_0$. Here, for all $r_i$ and $t \ge 0$, if $r_i$ is not activated at t, $\boldsymbol{x}_{t+1}(r_i) = \boldsymbol{x}_t(r_i)$. Otherwise, if it is activated, $r_i$ identifies $Q^{(i)}_t = \gamma ^{-1}_i(P_t)$ in $Z_i$, computes $\boldsymbol{y} = \phi _i(Q^{(i)}_t)$, and moves to $\boldsymbol{y}$ in $Z_i$.⁶ Then $\boldsymbol{x}_{t+1}(r_i) = \gamma _i(\boldsymbol{y})$. We assume that the scheduler is fair: It activates every robot infinitely many times. Throughout the paper, we regard the scheduler as an adversary.

We introduce several notations. Let $P \in (R^2)^n$. The distinct points of P is denoted by $\overline{P}$. Then |P| (resp. $|\overline{P}|$) denotes the number of points (resp. the number of distinct points) in P. Let CH(P) be the convex hull of P. We sometimes denote CH(P) by a sequence of vertices of CH(P) appearing on the boundary counter-clockwise. The center of gravity g(P) of P is defined by $g(P) = \sum _{\boldsymbol{x} \in P} \boldsymbol{x}/n$. For two points $\boldsymbol{x}$ and $\boldsymbol{y}$ in $R^2$, $dist(\boldsymbol{x},\boldsymbol{y})$ denotes the Euclidean distance between $\boldsymbol{x}$ and $\boldsymbol{y}$. For a set $B (\subseteq R^2)$ of points and a point $\boldsymbol{a} \in R^2$, $dist(\boldsymbol{a},B) = \min _{\boldsymbol{x} \in B} dist(\boldsymbol{a},\boldsymbol{x})$. Finally, let $\mathcal {P} = \{ P \in (R^2)^n: (0,0) \in P,\ n \ge 1 \}$. We regard $\mathcal {P}$ as the domain of target functions.

3 Convergence Problem

We investigate the convergence problem, provided that all robots are non-faulty. For any $0 \le \alpha \le 1$, consider a target function CoG$_{\alpha }$ defined by $\textrm{CoG}_{\alpha }(P) = (1-\alpha )g(P),$ for any $P \in {\mathcal P}$. The scale of CoG$_{\alpha }$ is $\alpha$, and CoG$_0 =$ CoG. The following theorem holds, since CoG works correctly under the sudden-stop model.

Theorem 1

([8]). For any $0 \le \alpha < 1$, let $\varPhi _{\alpha } = \{ \textrm{CoG}_{\alpha } \}$. Then $\varPhi _{\alpha }$ is compatible with respect to the convergence problem, or equivalently, $\textrm{CoG}_{\alpha }$ is an algorithm for the convergence problem.

We extend Theorem 1 to have the following theorem.

Theorem 2

Let $\varPhi$ be a set of target functions such that $0 \le \alpha (\varPhi ) < 1$. Then $\varPhi$ is compatible with respect to the convergence problem.

Proof

(Sketch). Let $\phi _i \in \varPhi$ be the target function taken by robot $r_i$ for $i = 1, 2, \ldots , n$. Let $\alpha (\phi _i) = \alpha _i$ and $\alpha = \max _{1 \le i \le n} \alpha _i$. Then $\alpha \le \alpha (\varPhi ) < 1$. Consider any execution $\mathcal{E}: P_0, P_1, \ldots$ starting from any initial configuration $P_0$. We show that $P_t$ converges to a point.

Suppose that $P_t = \{ \boldsymbol{x}, \boldsymbol{x}, \ldots , \boldsymbol{x} \}$ at some time t, i.e., $|\overline{P_t}|=1$. Since $\boldsymbol{g}_t = g(P_t) = \boldsymbol{x}$, $P_{t+1} = P_t$. Thus convergence has already been achieved. We assume without loss of generality that $|\overline{P_t}| \ge 2$ for all $t \ge 0$.

Let $A_t \subseteq \mathcal{R}$ be the set of robots activated at time t. If $\boldsymbol{x}_t(r) = \boldsymbol{g}_t$ for all $r \in A_t$, $P_{t+1} = P_t$ holds. However, there is a robot r such that $\boldsymbol{x}_t(r) \not = \boldsymbol{g}_t$ since $|\overline{P_t}| \ge 2$, and r is eventually activated by the fairness of scheduler. Thus, without loss of generality, we assume that there is a robot $r \in A_t$ such that $\boldsymbol{x}_t(r) \not = \boldsymbol{g}_t$, and that $P_{t+1} \not = P_t$ holds for all $t \ge 0$.

We denote $CH(P_t)$ by $CH_t$. Since $\alpha < 1$, $CH_{t+1} \subseteq CH_t$, which implies that $CH_t$ converges to a convex k-gon CH (including a point and a line segment) for some positive integer k. We show that CH is a point, i.e., $k = 1$.

Let $\boldsymbol{p}_0, \boldsymbol{p}_1, \ldots , \boldsymbol{p}_{k-1}$ be the vertices of CH aligned counter-clockwise on the boundary. To derive a contradiction, we assume that $k \ge 2$. For any pair $(i,j)~ (0 \le i < j \le k-1)$, let $L_{(i,j)} = dist(\boldsymbol{p}_i, \boldsymbol{p}_j)$, and $L = \min _{0 \le i < j \le k-1} L_{(i,j)}$. Since $CH_t$ converges to CH, for any $0 < \epsilon \ll (1-\alpha )L/n$, there is a time instant $t_0$ such that, for all $t \ge t_0$, $CH \subseteq CH_t \subseteq N_{\epsilon }(CH)$. For any vertex $\boldsymbol{p}$ of CH, $dist(\boldsymbol{p},\alpha * CH_t) > (1 - \alpha )(L/n - \epsilon ) - \epsilon \gg \epsilon$, since $dist(\boldsymbol{p},\boldsymbol{g}_t) > L/n - \epsilon$.

Suppose that a robot r is activated at some time $t \ge t_0$. Then $\boldsymbol{x}_{t+1}(r) \in \alpha * CH_t$, which implies that $\boldsymbol{x}_{t+1}(r) \not \in N_{\epsilon }(\boldsymbol{p})$, for any vertex $\boldsymbol{p}$ of CH. If r is reactivated at some time $t' > t$ for the first time after t, since $CH_{t'} \subseteq CH_t$ and $\boldsymbol{x}_{t'+1}(r) \in \alpha * CH_{t'}$, $\boldsymbol{x}_{t'+1}(r) \not \in N_{\epsilon }(\boldsymbol{p})$, for any vertex $\boldsymbol{p}$ of CH. Therefore, for any $t' > t$ and any vertex $\boldsymbol{p}$ of CH, $\boldsymbol{x}_{t'}(r) \not \in N_{\epsilon }(\boldsymbol{p})$.

On the other hand, all robots will be activated infinitely many times after time t, by the fairness of scheduler. It is a contradiction to the assumption that $CH_t$ converges to CH, since there is a time instant $t' > t$ such that for any robot r and any vertex $\boldsymbol{p}$ of CH, $\boldsymbol{x}_{t'}(r) \not \in N_{\epsilon }(\boldsymbol{p})$ holds.    $\square$

Let $\varPhi$ and $\varPhi '$ be two sets of target functions. If $\alpha (\varPhi ) < 1$ and $\alpha (\varPhi ') < 1$, $\varPhi , \varPhi '$, and $\varPhi \cup \varPhi '$ are all compatible with respect to the convergence problem by Theorem 2. However, the following claim does not hold:

If both of $\varPhi$ and $\varPhi '$ are compatible with respect to the convergence problem, so is $\varPhi \cup \varPhi '$.

To observe this fact, examine two target functions $\phi _T$ and $\phi _S$. For a configuration P, define a condition $\varPsi$ as follows:

• $\varPsi$: $|P| = 7$, $(0,0) \in P$, $P = T \cup S$, T is an equilateral triangle, S is a square, T and S have the same side length, and T and S do not overlap.

[Target function $\phi _T$]

• 1. If P satisfies $\varPsi$:

  • (a) If $(0,0) \in T$, $\phi _T(P)$ is the middle point on the line segment connecting (0, 0) and g(T).

  • (b) If $(0,0) \in S$, $\phi _T(P) = g(P)$.

• 2. If P does not satisfy $\varPsi$: $\phi _T(P) = g(P)$.

[Target function $\phi _S$]

• 1. If P satisfies $\varPsi$:

  • (a) If $(0,0) \in S$, $\phi _S(P)$ is the middle point on the line segment connecting (0, 0) and g(S).

  • (b) If $(0,0) \in T$, $\phi _S(P) = g(P)$.

• 2. If P does not satisfy $\varPsi$: $\phi _S(P) = g(P)$.

Recall that g(P), g(T), and g(S) are the centers of gravity of P, T, and S, respectively, and that when a robot identifies P in Look phase, (0, 0) always in P, which corresponds to its current position.

Let us observe that $\alpha (\phi _T) = 1$. Since $\phi _T(P) \in CH(P)$ for all P, $\alpha (\phi _T) \le 1$. To see that $\alpha (\phi _T) \ge 1$, consider any number $0< a < 1$. It is easy to construct a P satisfying $\varPsi$ such that $\frac{dist((0,0),g(T))}{dist((0,0)),g(P))} < a$, which implies that $\alpha (\phi _T) > 1 - a$. Thus $\alpha (\phi _T) = 1$ by the definition of $\alpha$. By the same argument, $\alpha (\phi _S) = 1$.

Theorem 3

Both $\varPhi _T =\{\phi _T\}$ and $\varPhi _S = \{\phi _S\}$ are compatible with respect to the convergence problem, but $\varPhi = \varPhi _T \cup \varPhi _S$ is not.

4 Convergence When at Most One Robot Crashes

We investigate the fault-tolerant (n, 1)-convergence problem (FC(1)) and the fault-tolerant (n, 1)-convergence problem to a point (FC(1)-PO). There is an algorithm for FC(1) [8], but FC(1)-PO is not easier than FC(1). We have the following theorem, which implies the existence of an algorithm for FC(1)-PO.

Theorem 4

Let $\varPhi$ be a set of target functions such that $0 \le \alpha (\varPhi ) < 1$. Then $\varPhi$ is compatible with respect to FC(1)-PO.

Corollary 1

Let $\varPhi$ be a set of target functions such that $0 \le \alpha (\varPhi ) < 1$. Then $\varPhi$ is compatible with respect to FC(1).

Next we reconsider the target functions $\phi _T$ and $\phi _S$.

Theorem 5

Both $\varPhi _T = \{\phi _T\}$ and $\varPhi _S = \{\phi _S\}$ are compatible with respect to FC(1)-PO. However, $\varPhi = \varPhi _T \cup \varPhi _S$ is not. Recall that $\alpha (\varPhi _T) = \alpha (\varPhi _S) = \alpha (\varPhi ) = 1$.

5 FC(f) for $f \ge 2$

We go on the fault tolerant (n, f)-convergence problem (FC(f)) for $f \ge 2$. Since CoG is an algorithm for FC(f) [8], the next theorem holds.

Theorem 6

([8]). Suppose that $f \le n-1$. The set $\varPhi _0 = \{ \textrm{CoG} \}$ is compatible with respect to FC(f), or equivalently, a set $\varPhi$ of target functions is compatible with respect to FC(f), if $\alpha (\varPhi ) = 0$.

Corollary 1 states that every set $\varPhi$ of target functions such that $0 \le \alpha (\varPhi ) < 1$ is compatible with respect to FC(1). In contrast, for any $2 \le f \le n-1$ and $0< \alpha < 1$, there is a set $\varPhi$ of two target functions such that (1) $\alpha (\varPhi ) = \alpha$, (2) each target function in $\varPhi$ is compatible with respect to FC(f), but (3) $\varPhi$ is not compatible with respect to FC(f). We use target functions $\xi _{(\alpha ,n)}$ and $\xi '_{(\alpha ,n)}$. Let $\ell = \lfloor \frac{n-2}{2} \rfloor$ and $\ell ' = \lceil \frac{n-2}{2} \rceil$. Thus $\ell + \ell ' = n-2$. For a configuration P, define a condition $\varPsi ^+$ by a conjunction of two conditions (i) and (ii).

• $\varPsi ^+$ :

  • (i) $P = \{ \boldsymbol{p}_1, \boldsymbol{p}_2, \ldots , \boldsymbol{p}_n \} \subseteq \overline{\boldsymbol{p}_1 \boldsymbol{p}_n}$, where $\boldsymbol{p}_1, \boldsymbol{p}_{\ell +1}, \boldsymbol{p}_{\ell +2}, \boldsymbol{p}_{\ell +3}$ are distinct and aligned on $\overline{\boldsymbol{p}_1 \boldsymbol{p}_n}$ in this order, $\boldsymbol{p}_1 = \boldsymbol{p}_2 = \dots = \boldsymbol{p}_{\ell }$, i.e., the multiplicity of $\boldsymbol{p}_1$ is $\ell$, $\boldsymbol{p}_{\ell +3} = \boldsymbol{p}_{\ell +4} = \dots = \boldsymbol{p}_n$, i.e., the multiplicity of $\boldsymbol{p}_{\ell +3}$ is $\ell '$.

  • (ii) Let $L = dist(\boldsymbol{p}_1,\boldsymbol{p}_n)$. Then $dist(\boldsymbol{p}_1,\boldsymbol{p}_{\ell +1}) = \frac{1}{2}L$. If n is even, $dist(\boldsymbol{p}_{\ell +1},\boldsymbol{p}_{\ell +2}) = \frac{\alpha n}{2(\alpha +n-1)}L$; otherwise, if it is odd, $dist(\boldsymbol{p}_{\ell +1},\boldsymbol{p}_{\ell +2}) = \frac{(2 \alpha -1)n+(1-\alpha )}{2(\alpha (n+1)-1)}L$.

[Target function $\xi _{(\alpha ,n)}$ ]

• 1. If P satisfies $\varPsi ^+$, $\xi _{(\alpha ,n)}(P)$ is

  • (a) $\boldsymbol{p}_{\ell +2}$, if $\boldsymbol{p}_{\ell +1} = (0,0)$,

  • (b) (0, 0), if $\boldsymbol{p}_{\ell +2} = (0,0)$, and

  • (c) g(P), otherwise.

• 2. If P does not satisfy $\varPsi ^+$, $\xi _{(\alpha ,n)}(P) = g(P)$.

[Target function $\xi '_{(\alpha ,n)}$ ]

• 1. If P satisfies $\varPsi ^+$, $\xi '_{(\alpha ,n)}(P)$ is

  • (a) (0, 0), if $\boldsymbol{p}_{\ell +1} = (0,0)$,

  • (b) $\alpha \boldsymbol{p}_1 + (1-\alpha ) g(P)$, if $\boldsymbol{p}_{\ell +2} = (0,0)$, and

  • (c) g(P), otherwise.

• 2. If P does not satisfy $\varPsi ^+$, $\xi '_{(\alpha ,n)}(P) = g(P)$.

Theorem 7

For any $2 \le f \le n-1$ and $0< \alpha < 1$, (1) $\alpha (\xi _{(\alpha ,n)}) = \alpha (\xi '_{(\alpha ,n)}) = \alpha$, (2) both of $\varPhi = \{ \xi _{(\alpha ,n)} \}$ and $\varPhi ' = \{ \xi '_{(\alpha ,n)} \}$ are compatible with respect to FC(f), but (3) $\varPhi \cup \varPhi '$ is not.

Before closing this section, we examine the case $\alpha = 1$.

Corollary 2

For any $2 \le f \le n-1$, there are two target functions $\xi _{(1,n)}$ and $\xi '_{(1,n)}$ such that (1) $\alpha (\xi _{(1,n)}) = \alpha (\xi '_{(1,n)}) = 1$, (2) both of $\varPhi = \{ \xi _{(1,n)} \}$ and $\varPhi ' = \{ \xi '_{(1,n)} \}$ are compatible with respect to FC(f), but (3) $\varPhi \cup \varPhi '$ is not.

6 FC(f)-CP for $f \ge 2$

We next investigate the fault tolerant (n, f)-convergence problem to a convex f-gon (FC(f)-CP). FC(1)-CP is FC(1)-PO. FC(f)-CP seems to be substantially easier than FC(f) (and FC(f)-PO), since the convergence of $CH_t$ to a convex f-gon does not always mean the convergence of $P_t$. We have the following theorem.

Theorem 8

Let $\varPhi$ be any set of target functions such that $0 \le \alpha (\varPhi ) < 1$. Then $\varPhi$ is compatible with respect to FC(f)-CP for any $2 \le f \le n-1$.

Let $\varPhi$ and $\varPhi '$ be any sets of target functions such that $\alpha (\varPhi ) < 1$ and $\alpha (\varPhi ') < 1$ hold. Then all of $\varPhi , \varPhi '$, and $\varPhi \cup \varPhi '$ are compatible with respect to FC(f)-CP for all $2 \le f \le n-1$, since $\alpha (\varPhi \cup \varPhi ') < 1$, by Theorem 8. However, we cannot extend this observation to include the case $\alpha = 1$. Consider the following two target functions $\tau$ and $\tau '$ for three robots.

[Target function $\tau$ ]

• 1. If $P = \{ \boldsymbol{p}_1, \boldsymbol{p}_2, \boldsymbol{p}_3 \}$ is a triangle such that $\angle \boldsymbol{p}_1< \angle \boldsymbol{p}_2 < \angle \boldsymbol{p}_3$, where $\angle \boldsymbol{p}_i$ is the angle of vertex $\boldsymbol{p}_i$ of the triangle, $\tau (P)$ is

  • (a) g(P) if $\boldsymbol{p}_1 = (0,0)$, and

  • (b) $\boldsymbol{p}_1$, otherwise.

• 2. Otherwise, $\tau (P) = g(P)$.

[Target function $\tau '$ ]

• 1. If $P = \{ \boldsymbol{p}_1, \boldsymbol{p}_2, \boldsymbol{p}_3 \}$ is a triangle such that $\angle \boldsymbol{p}_1< \angle \boldsymbol{p}_2 < \angle \boldsymbol{p}_3$, where $\angle \boldsymbol{p}_i$ is the angle of vertex $\boldsymbol{p}_i$ of the triangle, then $\tau '(P) = \boldsymbol{p}_1$.

• 2. Otherwise, $\tau '(P) = g(P)$.

Let $\varPhi = \{ \tau \}$ and $\varPhi ' = \{ \tau ' \}$. Then $\alpha (\varPhi ) = \alpha (\varPhi ') = 1$. Sets $\varPhi$ is compatible with respect to the fault tolerant (3, 2)-convergence problem to a line segment, but $\varPhi$ is not.

7 FC(f)-PO for $f \ge 2$

This section investigates the fault tolerant (n, f)-convergence problem to f points (FC(f)-PO) for $f \ge 2$. At a glance, FC(f)-PO looks to have properties similar to FC(f), and readers might consider that the former would be easier than the latter, since in the former, the non-faulty robots are not requested to converge to a point. On the contrary, we shall see that FC(f)-PO is a formidable problem even if $f = 2$.

7.1 Compatibility

We show a difference between FC(f) and FC(f)-PO for $f \ge 2$.

Theorem 9

Let $f \ge 2$. Any target function $\phi$ is not an algorithm for FC(f)-PO, if $0 \le \alpha (\phi ) < 1$, or equivalently, $\varPhi$ is not compatible with respect to FC(f)-PO, if $0 \le \alpha (\varPhi ) < 1$.

Recall that $\varPhi = \{ \xi _{(\alpha , n)}\}$ (or $\varPhi ' = \{\xi '_{(\alpha , n)}\}$) is compatible with respect to FC(f) for all $2\le f \le n-1$ and $0 \le \alpha < 1$ by Theorem 7. Since $\alpha (\varPhi ) = \alpha$, by Theorem 9, we have:

Corollary 3

Neither $\varPhi$ nor $\varPhi '$ is compatible with respect to FC(f)-PO, for all $f \ge 2$ and $0 \le \alpha < 1$.

7.2 Algorithm for FC(2)-PO

In Sect. 7.1, we showed that, for any $f \ge 2$, there is no FC(f)-PO algorithm whose scale is less than 1. It is a clear difference between FC(f)-PO and FC(f), which is solved, e.g., by CoG$_{\alpha }$ for any $0 \le \alpha < 1$. This section proposes an algorithm $\psi _{(n,2)}$ with $\alpha (\psi _{(n,2)})=1$ for FC(2)-PO. Unfortunately, proposing an algorithm for FC(f)-PO for $f \ge 3$ is left as a future work.

Algorithm ${\boldsymbol{\psi }}_{\mathbf {(n,2)}}$. We propose an algorithm $\psi _{(n,2)}$ to solve FC(2)-PO. Since the case $n =3$ is easy, we assume $n \ge 4$. Algorithm $\psi _{(n,2)}$ calls another algorithm LN$_{(n,2)}$, which solves FC(2)-PO when an initial configuration $P_0$ is linear, i.e., when $CH(P_0)$ is a line segment.

To compare positions $\boldsymbol{p}$ and $\boldsymbol{q}$, we frequently use a lexicographic order >. It has however a drawback for our purpose: Suppose that $\boldsymbol{p}$ (resp. $\boldsymbol{q}$) in $Z_0$ is $\boldsymbol{p}^{(i)}$ (resp. $\boldsymbol{q}^{(i)}$) in $Z_i$. Then $\boldsymbol{p}^{(i)} < \boldsymbol{q}^{(i)}$ and $\boldsymbol{p}^{(j)} > \boldsymbol{q}^{(j)}$ can happen for some $i \not = j$. In $\psi _{(n,2)}$, we introduce an order $\succ$ that all robots can consistently compute.

Let $P = \{ \boldsymbol{p}_1, \boldsymbol{p}_2, \ldots , \boldsymbol{p}_n \}$ be a multiset of n points, and $\overline{P} = \{\boldsymbol{q}_1, \boldsymbol{q}_2, \ldots , \boldsymbol{q}_m \}$ be the set of distinct points in P. The multiplicity of a point $\boldsymbol{q} \in \overline{P}$ is denoted by $\mu _P(\boldsymbol{q})$. In the definition of $\succ _P$, it is convenient to treat $\mu _P(\boldsymbol{q})$ points $\boldsymbol{q}$ in P as a point $\boldsymbol{q}$ with a label $\mu _P(\boldsymbol{q})$. We thus identify P with a pair $(\overline{P}, \mu _P)$, where $\mu _P$ is a labeling function to associate label $\mu _P(\boldsymbol{q})$ with each point $\boldsymbol{q} \in \overline{P}$. Let $\boldsymbol{o}_P$ be the center of the smallest enclosing circle $C_P$ of P.

Let $G_P$ be the rotation group $G_{\overline{P}}$ of $\overline{P}$ about $\boldsymbol{o}_P$ preserving $\mu _P$. The order $|G_P|$ of $G_P$ is denoted by $k_P$. Note that $k_P$ does not depend on $\mu _P(\boldsymbol{o}_P)$. It is similar to the symmetricity $\sigma (P)$ of P defined in [18], but $k_P \not = \sigma (P)$ in general. Let $\varGamma _P(\boldsymbol{q}) \subseteq \overline{P}$ be the orbit of $G_P$ through $\boldsymbol{q} \in \overline{P}$. Then $|\varGamma _P(\boldsymbol{q})| = k_P$ for all $\boldsymbol{q} \in \overline{P} {\setminus } \{ \boldsymbol{o}_P \}$, and $\mu _P(\boldsymbol{q}') = \mu _P(\boldsymbol{q})$ for all $\boldsymbol{q}' \in \varGamma _P(\boldsymbol{q})$. If $\boldsymbol{o}_P \in \overline{P}$, $\varGamma _P(\boldsymbol{o}_P) = \{ \boldsymbol{o}_P \}$. Let $\varGamma _P = \{ \varGamma _P(\boldsymbol{q}): \boldsymbol{q} \in \overline{P} \}$ be the set of all orbits. Then $\varGamma _P$ is a partition of $\overline{P}$.

To define $\succ _P$, we need the concept of view. Define an x-y coordinate system $\Xi _{\boldsymbol{q}}$ for any point $\boldsymbol{q} \in \overline{P} {\setminus } \{ \boldsymbol{o}_P\}$. The origin of $\Xi _{\boldsymbol{q}}$ is $\boldsymbol{q}$, the unit distance is the radius of $C_P$, and the x-axis is taken so that it goes through $\boldsymbol{o}_P$ in its positive side. Finally, it is right-handed. Let $\gamma _{\boldsymbol{q}}$ be the coordinate transformation from $\Xi _{\boldsymbol{q}}$ to $Z_0$. Then the view $V_P(\boldsymbol{q})$ of $\boldsymbol{q}$ is defined to be $\gamma ^{-1}_{\boldsymbol{q}}(P)$. That is, $\gamma _{\boldsymbol{q}}(V_P(\boldsymbol{q})) = P$, i.e., P in $Z_0$ is $V_P(\boldsymbol{q})$ in $\Xi _{\boldsymbol{q}}$. By definition, $V_P(\boldsymbol{q}) = V_P(\boldsymbol{q}')$ if and only if $\boldsymbol{q}' \in \varGamma _P(\boldsymbol{q})$. Let $View_P = \{ V_P(\boldsymbol{q}): \boldsymbol{q} \in \overline{P} {\setminus } \{ \boldsymbol{o}_P \} \}$.

To compare two views in $View_P$, we arbitrarily choose and fix a total order $\sqsupset$ on the set of multisets of n points. We define a total order $\succ _P$ on $\varGamma _P$ as follows. For any two distinct orbits $\varGamma _P(\boldsymbol{q})$ and $\varGamma _P({\boldsymbol{q}'})$ in $\varGamma _P$, $\varGamma _P(\boldsymbol{q}) \succ _P \varGamma _P({\boldsymbol{q}'})$, if one of the following conditions hold: (1) $\mu _P(\boldsymbol{q}) > \mu _P(\boldsymbol{q}')$, (2) $\mu _P(\boldsymbol{q}) = \mu _P(\boldsymbol{q}')$ and $dist(\boldsymbol{q},\boldsymbol{o}_P) < dist(\boldsymbol{q}',\boldsymbol{o}_P)$, or (3) $\mu _P(\boldsymbol{q}) = \mu _P(\boldsymbol{q}'), dist(\boldsymbol{q},\boldsymbol{o}_P) = dist(\boldsymbol{q}',\boldsymbol{o}_P)$, and $V_P(\boldsymbol{q}) \sqsupset V_P(\boldsymbol{q}')$. When $\boldsymbol{o}_P \in \overline{P}$, we assume that $\varGamma _P(\boldsymbol{q}) \succ _P \varGamma _P(\boldsymbol{o}_P)$ for all $\boldsymbol{q} \not = \boldsymbol{o}_P$. Now $\succ _P$ is a total order on $\varGamma _P$. If $k_P = 1$, since $\varGamma _P(\boldsymbol{q}) = \{ \boldsymbol{q} \}$ for all $\boldsymbol{q} \in \overline{P}$, we regard $\succ _P$ as a total order on $\overline{P}$ (by identifying $\varGamma _P(\boldsymbol{q})$ with $\boldsymbol{q}$).

We partition the set of all multisets $P = \{ \boldsymbol{p}_1, \boldsymbol{p}_2, \ldots , \boldsymbol{p}_n \}$ for all $n \ge 4$ into six types G, L, T, I, S, and Z. Let $m_P = |\overline{P}|$.

• G(oal): $m_P \le 2$.

• L(ine): CH(P) is a line segment.

• T(riangle): $m_P = 3$ and CH(P) is a triangle.

• I(nside): $m_P = 4$, CH(P) is a triangle, and $\boldsymbol{o}_P \in P$.

• S(ide): $m_P = 4$, CH(P) is a triangle, and $\boldsymbol{M}_P \in P$, where $\boldsymbol{M}_P$ is the middle point of a longest side of CH(P).

• Z: P does not belong to the above five types.

We define a target function $\psi _{(n,2)}$.

[Target function $\psi _{(n,2)}$]

• 1. When P is type Z:

  • (a) If $k_P \ge 2$, $\psi _{(n,2)}(P) = \boldsymbol{o}_P$.

  • (b) If $k_P = 1$, $\psi _{(n,2)}(P) = \boldsymbol{a}_P$, where $\boldsymbol{a}_P \in \overline{P}$ is the largest point with respect to $\succ _P$, which is well-defined since $k_P = 1$.

• 2. If P is type L, invoke LN(n, 2).

• 3. When P is type T, let $\overline{P} = \{ \boldsymbol{a}, \boldsymbol{b}, \boldsymbol{c} \}$.

  • (a) If triangle $\boldsymbol{abc}$ is equilateral, $\psi _{(n,2)}(P) = \boldsymbol{o}_P$.

  • (b) If triangle $\boldsymbol{abc}$ is not equilateral, $\psi _{(n,2)}(P) = \boldsymbol{M}_P$, where $\boldsymbol{M}_P$ is the middle point of the longest side. If there are two longest sides, $\boldsymbol{M}_P$ is the middle point of the side next to the shortest side counter-clockwise.

• 4. If P is type I, $\psi _{(n,2)}(P) = \boldsymbol{o}_P$.

• 5. If P is type S, $\psi _{(n,2)}(P) = \boldsymbol{M}_P$ (which is defined in the definition of type S).

Algorithm LN$\mathbf {_{(n,2)}}$. We present target function LN$_{(n,2)}$. Let $P = \{ \boldsymbol{p}_1, \boldsymbol{p}_2, \ldots , \boldsymbol{p}_n \} \in {\mathcal P}$ be a configuration of type L, which may be a configuration that a robot identifies in Look phase. We identify a point $\boldsymbol{p}_i$ in $R^2$ with a point in R: Since $(0,0) \in P$, we rotate P about (0, 0) counter-clockwise so that the resultant P becomes the multiset of points in the x-axis. Then we denote (p, 0) by p. In what follows in this section, a configuration P is thus regarded as a multiset of n real numbers, including at least one 0. We assume $p_1 \le p_2 \le \dots \le p_n$. By $\overline{P} = \{ b_1, b_2 , \ldots , b_{m_P} \}$, we denote the set of distinct real numbers in P, where $m_P$ is the size $|\overline{P}|$ of $\overline{P}$, and $b_1< b_2< \dots < b_{m_P}$. The length of CH(P) is denoted by $L_P = b_{m_P} - b_1 = p_n - p_1$. Let $\lambda _P = \max _{p \in P} \min \{ p - p_1, p_{m_P} - p \} \le L_P/2$. Define $j^*$ by $b_{j^*} = 0$. (Thus the current position of a robot $r_i$ who identifies P in Look phase is $b_{j^*}$ in $Z_i$.) Since P is type L, $k_P \le 2$. We denote the middle point of x and y by $M_{xy}$, i.e., $M_{xy} = (x+y)/2$.

Like $\psi _{(n,2)}$, we consider 10 types, which we define as follows:

• G: $m_P \le 2$.

• B$_3$: $m_P = 3$ and $k_P = 2$.

• B$_4$: $m_P = 4$ and $k_P = 2$.

• B$_5$: $m_P = 5$ and $k_P = 2$.

• B$_6$: $m_P = 6$ and $k_P = 2$.

• B: $m_P \ge 7$ and $k_P = 2$.

• U$_3$: $m_P = 3$ and $k_P = 1$.

• W: $m_P = 4$, $k_P = 1$, and $\overline{P} = \{b_1, b_2, b_3, b_4\} (b_1< b_2< b_3 < b_4)$ satisfies either (a) $2(b_2 - b_1) = b_3 - b_2$ and $b_3 \le M_{b_1b_4}$, or (b) $2(b_4 - b_3) = b_3 - b_2$ and $b_2 \ge M_{b_1b_4}$.

• U$_4$: $m_P = 4$, $k_P = 1$, and P is not type W.

• U: $m_P \ge 5$ and $k_P = 1$.

We now give the target function LN$_{(n,2)}$.

[Target function LN $_{(n,2)}$ ]

• 1. If P is type G, LN$_{(n,2)}(P) = 0$.

• 2. When P is type B: If $j^* \le \lceil m_P/2 \rceil$, LN$_{(n,2)}(P) = b_1$. Otherwise if $j^* > \lceil m_P/2 \rceil$, LN$_{(n,2)}(P) = b_{m_P}$.

• 3. When P is type B$_3$: $m_P = 3$. If $j^* \le 2$, LN$_{(n,2)}(P) = M_{b_1b_2}$. Otherwise if $j^* = 3$, LN$_{(n,2)}(P) = M_{b_2b_3}$.

• 4. When P is type B$_4$: $m_P = 4$. If $j^* \le 2$, LN$_{(n,2)}(P) = M_{b_1b_2}$. Otherwise if $j^* \ge 3$, LN$_{(n,2)}(P) = M_{b_3b_4}$.

• 5. When P is type B$_5$: $m_P = 5$. If $j^* \le 3$, LN$_{(n,2)}(P) = b_2$. Otherwise if $j^* \ge 4$, LN$_{(n,2)}(P) = b_4$.

• 6. When P is type B$_6$: $m_P = 6$. If $j^* \le 3$, LN$_{(n,2)}(P) = b_2$. Otherwise if $j^* \ge 4$, LN$_{(n,2)}(P) = b_5$.

• 7. When P is type U: Since $k_P = 1$, either $b_1 \succ _P b_{m_P}$ or $b_{m_P} \succ _P b_1$ holds. If $b_1 \succ _P b_{m_P}$, then LN$_{(n,2)}(P) = b_1$. Otherwise if $b_{m_P} \succ _P b_1$, LN$_{(n,2)}(P) = b_{m_P}$.

• 8. When P is type U$_3$: Since $k_P = 1$ and $m_P = 3$, if $b_2 = M_{b_1b_3}$, then $\mu _P(b_1) \not = \mu _P(b_3)$. If $b_2 < M_{b_1b_3}$ or $(b_2 = M_{b_1b_3}) \wedge (\mu _P(b_1) > \mu _P(b_3))$, then LN$_{(n,2)}(P) = (2b_1 + b_2)/3$. Otherwise, if $b_2 > M_{b_1b_3}$ or $(b_2 = M_{b_1b_3}) \wedge (\mu _P(b_1) < \mu _P(b_3))$, then LN$_{(n,2)}(P) = (b_2 + 2b_3)/3$.

• 9. When P is type W: $k_P = 1$, $m_P = 4$, and P satisfies either condition (a) or (b) (of the definition of type W).

  • (a) If $2(b_2 - b_1) = b_3 - b_2$ and $b_3 \le M_{b_1b_4}$, then LN$_{(n,2)}(P) = b_2$.

  • (b) If $2(b_4 - b_3) = b_3 - b_2$ and $b_2 \ge M_{b_1b_4}$, then LN$_{(n,2)}(P) = b_3$.

• 10. When P is type U$_4$: $k_P = 1$, $m_P = 4$, and P is not type W. Suppose that $\mu _P(b_1) \ge \mu _P(b_4)$ holds. (The case P satisfies $\mu _P(b_1) < \mu _P(b_4)$ is symmetric, and we omit it.)

  • (a) If $\mu _P(b_1) \ge \mu _P(b_3)$, then LN$_{(n,2)}(P) = b_1$.

  • (b) If $(\mu _P(b_1) < \mu _P(b_3)) \wedge (\mu _P(b_3) \ge 3)$, LN$_{(n,2)}(P) = b_1$, if $b_3 = 0$, and LN$_{(n,2)}(P) = 0$, otherwise if $b_3 \not = 0$.

  • (c) Otherwise if $(\mu _P(b_1)< \mu _P(b_3)) \wedge (\mu _P(b_3) < 3)$, $\mu _P(b_1) = \mu _P(b_4) = 1$ and $\mu _P(b_3) = 2$. LN$_{(n,2)}(P) = b_1$, if $(b_2 = 0) \vee (b_3 = 0)$, and LN$_{(n,2)}(P) = 0$, otherwise if $(b_1 = 0) \vee (b_4 = 0)$.

We have the following theorem:

Theorem 10

Target function $\psi _{(n,2)}$, which satisfies $\alpha (\psi _{(n,2)})=1$, is an algorithm for FC(2)-PO.

8 Gathering Problem

We finally investigate the gathering problem, provided that there are no faulty robots, to emphasize that the gathering and the convergence problems have completely different properties from the viewpoint of compatibility. Since the gathering problem is not solvable if $n = 2$ [18], we assume $n \ge 3$ in this section. Moreover, we assume that the robots initially occupy distinct points. There are many gathering algorithms. The following algorithm GAT [18] is one of them.

[Target function GAT]

• 1. If there is a unique $\boldsymbol{p} \in P$ such that $\mu _P(\boldsymbol{p}) > 1$, GAT$(P) = \boldsymbol{p}$.

• 2. Otherwise, if $\mu _P(\boldsymbol{p}) = 1$ for all $\boldsymbol{p} \in P$:

  • (a) If $k_P = 1$, GAT$(P) = \boldsymbol{p}$, where $\boldsymbol{p}$ is the largest point in P with respect to $\succ _P$.

  • (b) If $k_P > 1$, GAT$(P) = \boldsymbol{o}_P$.

Observe that $\alpha (\textrm{GAT}) = 1$. We can modify Step 2(a) of GAT to obtain another algorithm GAT$'$. For example, GAT$'(P)$ can be the smallest point $\boldsymbol{p}'$ in P with respect to $\succ _P$, instead of $\boldsymbol{p}$. Then indeed GAT$'$ is also a gathering algorithm with $\alpha (\mathrm{GAT'}) = 1$, but obviously $\varPhi = \{\mathrm{GAT, GAT'} \}$ is not compatible with respect to the gathering problem. Let us summarize.

Theorem 11

 [18]. Let $\varPhi = \{ \textrm{GAT} \}$ and $\varPhi ' = \{ \mathrm{GAT'} \}$. Then $\varPhi$ and $\varPhi '$ are compatible with respect to the gathering problem, but $\varPhi \cup \varPhi '$ is not. Here $\alpha (\varPhi ) = \alpha (\varPhi ') = \alpha (\varPhi \cup \varPhi ') = 1$.

Theorem 12

Any target function $\phi$ is not a gathering algorithm if $\alpha (\phi ) < 1$, or equivalently, any set $\varPhi$ of target functions such that $\alpha (\varPhi ) < 1$ is not compatible with respect to the gathering problem.

9 Conclusions

We introduced the concept of compatibility and investigated the compatibilities of several convergence problems. A compatible set $\varPhi$ of target functions with respect to a problem $\varPi$ is an extension of an algorithm $\phi$ for $\varPi$, in the sense that every target function $\phi \in \varPhi$ is an algorithm for $\varPhi$.

The problems we investigated are the convergence problem, the fault tolerant (n, f)-convergence problem (FC(f)), the fault tolerant (n, f)-convergence problem to a convex f-gon (FC(f)-CP), and the fault tolerant (n, f)-convergence problem to f points (FC(f)-PO), for crash faults. The gathering problem was also investigated. The results are summarized in Table 1. Main observations we would like to emphasize are:

• 1. The convergence, FC(1), FC(1)-PO, and FC(f)-CP share the same property: Every set $\varPhi$ of target functions is compatible, if $0\le \alpha (\varPhi ) < 1$.

• 2. The gathering problem and FC(f)-PO for $f \ge 2$ share the same property: Any set $\varPhi$ of target functions is not compatible, if $0\le \alpha (\varPhi ) < 1$.

• 3. FC(f) ($f \ge 2$) is in between FC(f)-CP and FC(f)-PO.

Before closing the paper, we list some open problems:

• 1. Extend Table 1 to contain the results for $\alpha (\varPhi ) > 1$.

• 2. Suppose that $\phi$ and $\phi '$ are algorithms for the convergence problem. Find a necessary and/or a sufficient condition for $\varPhi = \{ \phi , \phi ' \}$ to be compatible with respect to the convergence problem.

• 3. Investigate the compatibility of FC(f)-PO for $f \ge 2$ under the $\mathcal FSYNC$ model.

• 4. Investigate the compatibility of convergence problems under the $\mathcal ASYNC$ model.

• 5. Investigate the compatibility of convergence problems in the presence of Byzantine failures.

• 6. Investigate the compatibility of fault tolerant gathering problems.

• 7. Find interesting problems with a large compatible set.