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$.

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. $$