Self-stabilizing gathering of mobile robots under crash or Byzantine faults

Abstract

Gathering is a fundamental coordination problem in cooperative mobile robotics. In short, given a set of robots with arbitrary initial locations and no initial agreement on a global coordinate system, gathering requires that all robots, following their algorithm, reach the exact same but not predetermined location. Gathering is particularly challenging in networks where robots are oblivious (i.e., stateless) and direct communication is replaced by observations on their respective locations. Interestingly any algorithm that solves gathering with oblivious robots is inherently self-stabilizing if no specific assumption is made on the initial distribution of the robots. In this paper, we significantly extend the studies of deterministic gathering feasibility under different assumptions related to synchrony and faults (crash and Byzantine). Unlike prior work, we consider a larger set of scheduling strategies, such as bounded schedulers. In addition, we extend our study to the feasibility of probabilistic self-stabilizing gathering in both fault-free and fault-prone environments.

Appendix

1.1 Necessity of the side move for Algorithm 5.1

We must now show the necessity of introducing a side move in Algorithm 5.1. Assuming that robots execute the naive algorithm (Algorithm 5.1 without the clause executing the side move), we exhibit a situation in which the robots are unable to gather (depicted in Fig. 6):

Fig. 6

Illustration of the necessity of introducing the side move. The naive algorithm (without side move) can result in an endless cycle

Consider the initial configuration depicted in Fig. 6a. Assume that the reachable distance of all robots is the same and call it $\delta$. Let $D$ be some arbitrary distance strictly larger than $\delta$. The robots (or a subset thereof) are initially located such that they form four castles on a segment. Let ${ Q } _ FarL ,{ Q } _ FarR$ be the two castles at both ends of the segment and assume that they consist only of crashed robots. Let $W_L,W_R$ be two towers such that they become a castle by adding one robot. For simplicity, assume again that they also consist only of crashed robots. Let $r_L,r_R$ be two correct robots initially in $W_L,W_R$ respectively. The location of the four castles is symmetric such that the midpoint between ${ Q } _ FarL$ and ${ Q } _ FarR$ is also the midpoint between $W_L$ and $W_R$. The distance between $W_L$ and $W_R$ is $2D$ and the distance between ${ Q } _ FarL$ and ${ Q } _ FarR$ is at least $10D$.

Consider the scheduler as an adversary following a round-robin policy. First, $r_R$ is active (Fig. 6b). According to the naive algorithm, $r_R$ must move toward the nearest castle, which is the castle formed by $W_L$ and $r_L$. The dashed lines on the figure represent the boundaries of the Voronoi cells of each of the three castles: $\left\{ { Q } _ FarL , { Q } _ FarR , W_L\cup \left\{ r_L\right\} \right\}$. Since $r_R$ is located inside the Voronoi cell of castle $W_L\cup \left\{ r_L\right\}$, it moves toward it.

Second, $r_L$ is active (Fig. 6c). Since $r_R$ has moved in the previous step, $W_R$ is no longer the location of a castle. Now, $r_L$ is located inside the Voronoi cell of ${ Q } _ FarL$ and moves toward it.

Third, $r_R$ is active again (Fig. 6d). There are only two castles left on the configuration, namely ${ Q } _ FarL$ and ${ Q } _ FarR$. Since $D >\delta$, $r_R$ is located to the right of the midpoint between $W_L$ and $W_R$, which is also the midpoint between $Q_ FarL$ and ${ Q } _ FarR$. This means that $r_R$ is in the Voronoi cell of ${ Q } _ FarR$ and hence moves toward it. But, because $r_R$ is at distance $\delta$ to $W_R$, it ends its movement exactly at $W_R$, thus forming a castle again.

Fourth, $r_L$ is active and there are three castles (Fig. 6e). By construction, $W_R$ is located at a distance at least $6D$ from ${ Q } _ FarL$, and hence $r_L$ remains inside the Voronoi cell of the castle formed by $W_R$ and $r_R$. $r_L$ is also at a distance $\delta$ from $W_L$, and hence ends its movement exactly at $W_L$, forming a castle. This leads back to the initial configuration (Fig. 6a), and thus the cycle continues forever.

1.2 Disambiguation of side move for Algorithm 5.2

Fig. 7

Disambiguated side move. $\frac{a}{a+b} = \frac{a'}{a'+b'}$

Algorithm A.1 describes one way to disambiguate the side move, and is illustrated in Fig. 7. The lengths a and b depend on the position of robot ${ P }$ on the ray from castle ${ Q }$ relative to the boundary of the Voronoi cell of ${ Q }$.

The construction uses a trisection of the sector S calculated in the original side move. This ensures that a robot moving from a different ray does not end up at the same location. Trisecting ensures that there is no overlap in the zones computed by two robots from two different rays taking a side move into the same sector. With bisection, the two robots could compute a target on the same bisector and hence possibly collide. Whereas, with trisection, they cannot.

In addition, taking the minimum between points ${ V } _a$ and ${ V } _b$ ensures that the segment $\overline{{ Q } { V' }}$ lies entirely within the zone desired for a side move. Since the zone is convex (intersection of three convex areas), segment $\overline{{ P } { V' }}$ lies entirely inside the zone.

$$\begin{aligned} \alpha= & {} \frac{a}{a+b} \in \left( 0;1\right] \end{aligned}$$

(1)

$$\begin{aligned} a'(\alpha )= & {} \min \left( \left( a+b\right) \alpha ^2 \cos \theta ^+, \frac{ \left( a+b\right) \alpha }{ \cos \theta ^+ - m \sin \theta ^+ } \right) \end{aligned}$$

(2)

Since $a'(\alpha )$ is taken as the minimum of two functions that are both monotonic increasing in $\alpha$ over the range considered, $a'(\alpha )$ is itself monotonic increasing. It follows that, for two values $\alpha _1$ and $\alpha _2$ with $\alpha _1\not =\alpha _2$, the segments from $P(\alpha )$ to $P'(\alpha )$ do not cross.