Byzantine Fault Tolerant Symmetric-Persistent Circle Evacuation

Abstract

We consider (n, f)-evacuation on a circle, an evacuation problem of a hidden exit on the perimeter of a unit radius circle for $n>1$ robots, f of which are faulty. All the robots start at the center of the circle and move with maximum speed 1. Robots must first find the exit and then move there to evacuate in minimum time. The problem is considered complete when all the honest robots know the correct position of the exit and the last honest robot has evacuated through the exit. During the search, robots can communicate wirelessly.

We focus on symmetric-persistent algorithms, that is, algorithms in which all robots move directly to the circumference, start searching the circle moving in the same direction (cw or ccw), and do not stop moving around the circle before receiving information about the exit. We study the case of (n, 1) and (n, 2) evacuation. We first prove a lower bound of $1+\frac{4\pi }{n}+2\sin (\frac{\pi }{2}-\frac{\pi }{n})$ for one faulty robot, even a crash-faulty one. We also observe an almost matching upper bound obtained by means of an earlier search algorithm. We finally study the case with two Byzantine robots and we provide an algorithm that achieves evacuation in time at most $3+\frac{6\pi }{n}$ , for $n\ge 9$, or at most $3+\frac{6\pi }{n}+\delta (n)$, for $n<9$, where $\delta (n) \le 2\sin (\frac{3\pi }{2n})+ \sqrt{2-4\sin (\frac{3\pi }{2n})+4 \sin ^{2}{(\frac{3\pi }{2n})}}-2$.

1 Introduction

An important, extensively studied family of problems in mobile agent computing concerns situations where a group of robots need to find one or more targets that are located in unknown points of a territory. In a particular case of interest, the target(s) are exit(s) and the goal of the robots is either to locate the exit(s) (Search problem) or to leave the territory (Evacuation problem), as fast as possible. In this paper we focus on the latter problem.

1.1 Model and Preliminaries

We detail below the particular setting that we are going to study in this work.

Location and Movement

The starting position of the robots is the center of a unit radius disk. The exit is located at the perimeter of the disk. All robots move with the same speed 1. During their movement, they can recognize and move along the perimeter of the disk, and they can find the exit if they are at its location. Robots are allowed to take shortcuts moving through chords in the interior of the disk.

Communication

The robots can communicate wirelessly and with no delay at any time and distance. The messages may contain information about their location, whether or not they found the exit, how far they have moved from their starting position etc. Messages are tagged with the sender’s unique identifier that cannot be modified in any way. All robots can deduce their relative position from each other messages. They are also equipped with a pedometer in order to measure distances.

Fault Types

Some robots may display faulty behaviour. A crash-faulty robot may stop functioning at any time, meaning that they fail to communicate any messages, and remains idle. A Byzantine robot behaves maliciously, it can alter its trajectory and provide or hide information in order to confuse the rest of the honest robots on the location of the exit. A Byzantine robot can also behave as a crash-faulty one.

Adversary

For the worst case analysis of our algorithms, we consider an adversary who controls the location of the exit and the behaviour of the malicious robots (its trajectories as well as the messages they will broadcast) so as to maximize the resulting search and evacuation completion time. An evacuation is complete if the exit is found (has been visited by a non-faulty robot and the rest of them, if any, can be convinced (provably) of the (correct) location of the exit) and all the non-faulty robots reach the exit.

1.2 Related Work

Evacuation is closely related to Search, in fact the two problems coincide in the case of a single robot. A long line of research focused on the line search (aka Cow Path) problem (see [1,2,3] and references therein); more recent works include Kao et al. [4], in the randomized setting, and Demaine et al. [5] who takes into account the turn cost.

The problem was studied under the fault-tolerance perspective by Czyzowicz et al. [6, 7] who considered the problem under the presence of either crash or Byzantine failures.

In circular topologies, evacuation was the first problem to be studied, in [8], who dealt with both the wireless and face-to-face communication models. Additional work on circle evacuation followed shortly afterwards, e.g. in [9] for the face-to-face model, and in [10] for equilateral triangles (for a comprehensive survey we refer the reader to [11]).

Regarding fault-tolerant evacuation in circles, a work closely related to this paper is [12], where they study the problem with 3 robots, one of which is faulty, and provide upper and lower bounds for both cases of crash-faulty and Byzantine-faulty robot. They also introduce the notion of symmetric-persistent algorithms that we make use of in the present paper.

For the search problem in circles, under crash or Byzantine failures, a recent study [13] has shown a tight bound of $1+\frac{4\pi }{n}$ to find the exit where n is the number of robots, one of which is Byzantine.

1.3 Results of the Paper

In Sect. 2 we consider the Evacuation problem for n robots one of which is Byzantine and we prove a lower bound for the symmetric persistent algorithms of $1+\frac{4\pi }{n}+2\sin (\frac{\pi }{2}-\frac{\pi }{n})$. The lower bound is almost matching to our upper bound. In Sect. 3 we present our symmetric persistent algorithm for the case of Evacuation of n robots with 2 Byzantine faults and we provide an upper bound of $3+\frac{6\pi }{n}$ , for $n\ge 9$ and $3+\frac{6\pi }{n}+\delta (n)$ for $n<9$, where $\delta (n) \le 2\sin (\frac{3\pi }{2n})+ \sqrt{2-4\sin (\frac{3\pi }{2n})+4 \sin ^{2}{(\frac{3\pi }{2n})}}-2$.

2 Evacuation with One Byzantine Fault

We define (n, f) - Evacuation, to mean evacuation for $n > 1$ robots, of which f are faulty. In this work, we consider only Byzantine faults.

2.1 Lower Bound for Symmetric-Persistent Algorithms

As defined in [12], symmetric-persistent algorithms are family of natural algorithms that force all robots to immediately go to the disk perimeter and only allow a robot to stop its exploration of the assigned sector if it receives information about the exit. Symmetric-persistent algorithms force all the robots to move in the same direction (either clockwise or counter-clockwise).

Theorem 1

Any symmetric-persistent algorithm requires time at least

$$ 1+\frac{4\pi }{n}+2\sin \Bigl (\frac{\pi }{2}- \frac{\pi }{n}\Bigr ) \ge 3+\frac{4\pi }{n}-\frac{\pi ^2}{2n^2} $$

for evacuation of n robots, one of which is crash-faulty, from a circle of radius 1.

Proof

Note that if $n=2$ the result is trivial, so we assume $n\ge 3$. Let us denote by f(n) the quantity displayed in the statement.

Fix a 0 on the unit circle and denote by $x_i$ the length of the arc between robot $\alpha _i$ and 0 in the ccw direction. Let $\psi _i$ denote the length of the arc between robots $\alpha _i$ and $\alpha _{i+2}$. Since $\sum \psi _i={4\pi }$, there exists i such that $\psi _i\ge {4\pi }/n=2\theta$. Without loss of generality, let $x_2=\psi _0\ge 2\theta$ and denote it by $\psi$. For any $\epsilon >0$, if the adversary places the exit at distance $\psi -\epsilon$ from 0 and robot $\alpha _1$ is faulty, then the exit will be discovered by robot $\alpha _0$ in time $1+\psi -\epsilon$.

We now consider two cases on $\psi$.

First, suppose $2\theta \le \psi <\pi$. By the maximality of $\psi$, there is at least one robot at distance x from 0 such that $x\in [\pi -\psi /2,\pi +\psi /2]$. The total time this robot will require to reach the exit is at least

$$ 1+\psi -\epsilon +2\sin \Bigl (\frac{\pi -\psi /2}{2}\Bigr ) \ge 1+2\theta +2\sin \Bigl (\frac{\pi -\theta }{2}\Bigr )-\epsilon =f(n)-\epsilon ,$$

where the inequality follows because $\psi \ge 2\theta$ and the left-hand side is increasing in $\psi$.

Next, we consider the case $\pi \le \psi$. In this case we will bound the time robot $\alpha _2$ will need, which is at least

$$ 1+\psi -\epsilon +2\sin (\psi /2) $$

time units. Note that this is increasing in $\psi$. It follows that it is at least $1+\pi -\epsilon +2$, which for $n\ge 4$ is greater than f(n). If $n=3$, then this is at least $1+2\theta -\epsilon +2\sin \theta =f(n)-\epsilon$. The equality holds since $\sin \theta =\sin (2\pi /3)=\sin (\frac{\pi }{2}-\frac{\pi }{6})\ge \sin (\frac{\pi }{2}-\frac{\pi }{3})$.

Since the above hold for any $\epsilon$, the first bound in the statement follows. The second bound follows from the inequality $\cos (x)\ge 1-x^2/2$.

Theorem 2

There exists a symmetric-persistent algorithm that requires time at most

$$ 3+\frac{4\pi }{n} $$

for evacuation of n robots, one of which is Byzantine, from a circle of radius 1.

Proof

We employ the optimal Search algorithm proposed in [13], which has a time bound of $1+\frac{4\pi }{n}$ to find the exit, and add the length of the diameter for the furthest robot to evacuate.

Remark 1

Note that above upper bound is within $O(1/n^2)$ from the lower bound of Theorem 1.

3 Evacuation with Two Byzantine Faults

3.1 Algorithm for (n, 2) - Evacuation

We will now present an algorithm for Evacuation of n robots, 2 of which are faulty, both Byzantine, and then analyze its time requirements.

Consider n robots $a_0, a_1, \ldots ,a_{n-1}$ and set $\theta :=2\pi /n$. Each robot $a_k$ moves along a radius to the point $k\theta$ of the perimeter of the unit circle. We call the arc $[k\theta , (k+1)\theta )$ sector $S_k$; that is, after 1 time unit, robot $a_k$ will be located at the beginning of sector $S_k$. Robots make announcements if they find the exit and confirm/disprove the announcements of other robots accordingly. Every robot searches one sector in each round, moving counter clockwise (ccw). At any moment, if an announcement is confirmed by two other robots, that announcement is correct. Also, an announcement disproved by three other robots is invalidated (announcing a different exit also counts as a disproof). When three robots make different announcements, we can deduce that two of them are Byzantine and as a result the silent ones are honest. All honest robots move through a chord to the exit to evacuate the circle and the algorithm terminates in time E(n, 2). Details of the main algorithm are as follows.

We define as t the time beyond the $1+3\theta$ needed to learn the position of the exit. If $t\le 1$, evacuation time is unaffected and equals to $3+3\theta$. If $t>1$, the evacuation time is increased by a function $\delta (n)$. For the geometric proof and the calculation of $\delta (n)$ please refer to the appendix.

Theorem 3 ((5, 2) - Evacuation)

The worst-case time for (n, 2) - Evacuation for $n\ge 9$ by Algorithm 1 satisfies

$$\begin{aligned} E(n,2)\le 3+\frac{6\pi }{n} \end{aligned}$$

and $E(n,2)\le 1+\frac{6\pi }{n}+ 2\sin (\frac{3\pi }{2n})+ \sqrt{2-4\sin (\frac{3\pi }{2n})+4 \sin ^{2}{(\frac{3\pi }{2n})}}$ for $n<9$.

Proof

If after 3 rounds only one announcement is made, that announcement is correct because in these 3 rounds every point in the circle has been searched by at least one honest robot. All robots will move through a chord towards the exit, and evacuation will be completed in time $3+3\theta$. For any other outcome, we consider the following cases depending on the number of announcements made during the execution of the algorithm.

Case 1: No announcement at the end of round 1.

Subcase 1-a: No announcement at the end of round 2.

• 1-a-i: Two announcements at the end of round 3.

  Assume that they are made by robots $a_0$ and $a_{n-1}$. Robots $a_1$ and $a_2$ searched the sector with the announcement of $a_0$ in the previous rounds and made no announcements. Also $a_0$ disagrees with $a_{n-1}$ as he made an announcement elsewhere. Three robots disagree with $a_0$ so that is the Byzantine one. As a result the correct exit is the one $a_{n-1}$ announced. The exit will be known in time $1+3\theta$. Similar argument can be used for announcements not in consecutive sectors.

• 1-a-ii: Three announcements at the end of round 3.

  Announcements must be in consecutive sectors (in any other case, we would have earlier announcements). Lets say announcements made by robots $a_0$, $a_{n-1}$ and $a_{n-2}$. Then we know that the rest of the robots are honest. Robot $a_1$ visited the sectors with the announcements of $a_0$ and $a_{n-1}$ in the previous rounds. As a result $a_{n-2}$ is honest and the exit is on his announcement. The exit will be known in time $1+3\theta$.

Subcase 1-b: One announcement at the end of round 2.

Fig. 1.

time $1+\theta$

Fig. 2.

time $1+2\theta$

Fig. 3.

time $1+3\theta$

Fig. 4.

Inspection and Evacuation

Then at round 3 there will be one or two new announcements.

• 1-b-i. One new announcement at the end of round 3.

  If the new announcement is in a different sector than the previous one, refer to case (1-a-i). Else (two announcements in the same sector), suppose that the first announcement was made by $a_0$ and the second by $a_{n-1}$. Then we can deduce that $a_1$ is the one Byzantine robot (as he disagrees with both announcements, and at the end of round 3, no new announcement is made) and as a result $a_{n-2}$ is an honest one. $a_{n-2}$ as an inspector robot will travel through a chord to the nearest announcement. We will know the exit in time $1+3\theta +2\sin (\pi /n)$. See Figs. 1–4.

• 1-b-ii: Two new announcements at the end of round 3.

  If the three announcements made until the end of round 3 are in different sector, refer to case (1-a-ii). If one of the new announcements is in the same sector with the previous one, consider the following cases:

  • Assume that $a_0$ made the announcement in the second round and $a_{n-1}$, $a_1$ made an announcement in the third round.

    We can deduce that $a_1$ is the Byzantine robot as he disagrees with the other two announcements and also with robots $a_2$ and $a_3$ that searched that sector in previous rounds. As a result $a_{n-2}$ is honest. Inspector robot $a_{n-2}$ will travel through a chord to the nearest announcement. We will know the exit in time $1+3\theta +2\sin (\pi /n)$.

  • Assume that $a_0$ made the announcement in the second round and $a_{n-1}$, $a_{n-2}$ made an announcement in the third round. In that case we can deduce that all other robots are honest. Robot $a_1$ visited the sector with the announcements of $a_{n-1}$ and $a_{n-2}$. The exit is the announcement of $a_{n-2}$ and will be known in time $1+3\theta$.

Subcase 1-c: Two announcements at the end of round 2.

If there is no new announcement at round 3, refer to case (1-a-i). If there is one new announcement at the end of round 3 in a different sector, refer to case (1-a-ii). Else, if there there is one new announcement at the end of round 3 in the same sector with a previous announcement refer to case (1-b-ii).

Subcase 1-d: Three announcements at the end of round 2.

Refer to case (1-a-ii).

Case 2: One announcement at the end of round 1.

Subcase 2-a: No new announcement at the end of round 2.

Fig. 5.

time $1+\theta$

Fig. 6.

time $1+2\theta$

Fig. 7.

time $1+3\theta$

Fig. 8.

Inspection and Evacuation

• 2-a-i: One new announcement at the end of round 3.

  If announcements in different sector, refer to case (1-a-i). If two announcements are in the same sector, say by $a_0$, $a_{n-2}$, then after 3 rounds we will have no consensus about the exit. In the worst case, $a_{n-1}$ will agree with $a_0$ and the inspector robot $a_{n-3}$ will agree with $a_{n-2}$. In such a case, a second inspector robot $a_{n-4}$ is needed to move to the nearest announcement. The exit will be known in time $1+3\theta +2\sin (3\pi /2n)$. This is the worst search time. See Figs. 5–8.

• 2-a-ii: Two new announcements at the end of round 3.

  If all announcements in different sectors, refer to case (1-a-ii). Else consider the following cases:

  • Assume the announcements were made by $a_0$ in the first round and by $a_{n-2}$ and $a_{n-4}$ in the third round. We know that all the other robots are honest. Robot $a_{n-1}$ searched the sector with the announcements of $a_0$ and $a_{n-2}$ in the second round. If one of them is correct, that must be the one $a_0$ announced (if $a_{n-2}$ would be correct, $a_{n-1}$ would announced it in the second round). If $a_{n-1}$ disagrees with both of them, the exit is announced correctly by $a_{n-4}$ and will be known in time $1+3\theta$.

  • Assume the announcements were made by $a_0$ in the first round and by $a_{n-1}$ and $a_{n-2}$ in the third round. We know that all the other robots are honest. Inspector robot $a_{n-3}$ will visit the nearest announcement and the exit will be known in time $1+3\theta +2\sin (\pi /n)$.

Subcase 2-b: One new announcement at the end of round 2.

• 2-b-i: No new announcement at the end of round 3.

  If we can’t already differentiate the announcements, inspector robot will find us the exit at time $1+3\theta +2\sin (\pi /n)$. Refer to case (2-a-i).

• 2-b-ii: One new announcement at the end of round 3. If all three announcements are in different sectors, refer to case (1-a-ii). If two of the three announcements are in the same sector refer to case (2-a-ii). If all three announcements are in the same sector made by, say, $a_0$, $a_{n-1}$ and $a_{n-2}$ then after the third round, honest inspector robot $a_{n-3}$ must visit 2 of these announcements, The exit will be known in time $1+3\theta +4\sin (\pi /3n)$. See Figs. 9–12.

Fig. 9.

time $1+\theta$

Fig. 10.

time $1+2\theta$

Fig. 11.

time $1+3\theta$

Fig. 12.

Inspection and Evacuation

Subcase 2-c: Two new announcements at the end of round 2.

Refer to case (2-a-ii).

Case 3: Two announcements at the end of round 1.

Subcase 3-a: No new announcement at the end of round 2.

• 3-a-i. No new announcement at the end of round 3.

  Refer to case (1-a-i).

• 3-a-ii. One announcement at the end of round 3.

  If all three announcements are in different sectors, refer to case (1-a-ii). If two announcements are in the same sector, consider the following cases:

  • Assume that $a_0$ and $a_{n-4}$ made the announcements in the first round and $a_{n-2}$ in the third round. All other robots are honest. Robot $a_{n-1}$ for example have visited all the locations of the announcements and we will know the correct exit in time $1+3\theta$.

  • Assume that $a_0$ and $a_{n-1}$ made the announcements in the first round and $a_{n-2}$ in the third round. That means that $a_3$ is honest, and if the announcement of $a_{n-1}$ is not correct, becoming an inspector robot, will move to the nearest announcement through a chord and the exit will be known in time $1+3\theta +2\sin (\pi /n)$.

Subcase 3-b: One new announcement at the end of round 2.

Refer to case (3-a-ii).

Case 4: Three announcements at the end of round 1.

Refer to case (1-a-ii).

This completes the proof of the claimed time bound.    $\square$

Some calculations follow that give (for $4\le n \le 9$) the bounds obtained by the above algorithm for the (n, 2) case in comparison with the lower bound obtained for the (n, 1) case (which holds of course for 2 Byzantine robots as well):

n	(n, 1): LB	(n, 2): $3+3\theta$	$(n,2): \delta (n)$	(n, 2) :  UB
4	5.5558	7.7124	0.5687	8.2811
5	5.1313	6.7699	0.2361	7.0060
6	4.8264	6.1415	0.0881	6.2297
7	4.5971	5.6927	0.0318	5.7246
8	4.4186	5.3561	0.0095	5.3657
9	4.2756	5.0944	0	5.0944

4 Conclusion

We studied the evacuation problem of n robots with one or two Byzantine faults in the wireless model and provided a lower bound for the (n, 1)-evacuation case and an upper bound for the (n, 2)-evacuation case. An interesting possible direction after that would be to tighten our bounds, consider other communication models (like the face-to-face model) or generalize for f Byzantine robots. In particular, we conjecture that $3+3\theta$ is a lower bound for the (n, 2) evacuation problem for infinitely many n.

A Appendix - \(\delta (n)\) Calculation

As shown in Fig. 13, suppose at the end of round 3 the exit is not yet known, and possible exits are in D and E. Robot $a_k$ placed at A, moves to evacuate to its farthest announcement D, at distance 2 (diameter, r=1). After $t\le r$ the inspector robot moving from F will determine the correct exit and robot $a_k$ may need to change direction to E, but the new path that will travel is not larger than the diameter of the circle.

Fig. 13.

$t\le 1$

Fig. 14.

$t>1$

We must show that $BE \le BD$. Triangle CED is equilateral $(CE=CD=r=1)$ and angle $C\hat{E}D=C\hat{D}E$. As a result angle $B\hat{E}D \ge C\hat{E}D$. In triangle BED, $B\hat{E}D \ge B\hat{D}E$ meaning that $BD \ge BE$.

If $t>1$, evacuation time is increased by $\delta (n)$.

As we can see in Fig. 14, we must calculate the distance of path ABE. We know that $AB=t$ so we continue to determine BE.

In triangle CBE, $CE=1$, $CB=1-BD=1-(2-t)=t-1$. In the worst case regarding evacuation, angle $E\hat{C}D=\theta /2$. Now we can calculate BE:

$$\begin{aligned}&BE^2=CB^2+CE^2-2 \cdot CB \cdot CE \cdot \cos (\pi /n)\\&\, BE^2=t^2-2(t-1)(\cos (\pi /n) +1). \end{aligned}$$

The total distance the robot will travel to evacuate is $AB+BE=t+BE$ and that surpasses the diameter by $\delta (n)$ defined below:

$$\delta (n) = \left\{ \begin{array}{ll} 0 &{} \text{ if } t \le 1 \\ t+\sqrt{t^2-2(t-1)(\cos {(\pi /n)}+1)}-2, &{} \text{ if } t>1 \end{array} \right. $$