Evacuation from a disc in the presence of a faulty robot
We consider the evacuation problem on a circle for three robots, at most one of which is faulty. The three robots starting from the center of a unit circle search for an exit placed at an unknown location on the perimeter (of the circle). During the search, robots can communicate wirelessly at any distance. The goal is to minimize the time that the latest non-faulty robot reaches the exit. Our main contributions are two intuitive evacuation protocols for the non-faulty robots to reach the exit in two well-studied fault-models, Crash and Byzantine. Moreover, we complement our positive results by lower bounds in both models. A summary of our results reads as follows: - Case of Crash Faults: Lower Bound ≈5.188; Upper Bound ≈6.309;, - Case of Byzantine Faults: Lower Bound ≈5.948; Upper Bound ≈6.921, For comparison, it is known (see ) that in the case of three non-faulty robots with wireless communication we have a lower bound of 4.159, and an upper bound of 4.219 for evacuation, while for two non-faulty robots (Formula Presented) is a tight upper and lower bound for evacuation.
|Keywords||Algorithm, Byzantine faulty, Crash faulty, Evacuation, Robot, Search|
|Series||Lecture Notes in Computer Science|
Czyzowicz, J. (Jurek), Georgiou, K. (Konstantinos), Godon, M. (Maxime), Kranakis, E, Krizanc, D. (Danny), Rytter, W. (Wojciech), & Włodarczyk, M. (Michał). (2017). Evacuation from a disc in the presence of a faulty robot. In Lecture Notes in Computer Science. doi:10.1007/978-3-319-72050-0_10