Τίτλος:
Byzantine fault tolerant symmetric-persistent circle evacuation
Γλώσσες Τεκμηρίου:
Αγγλικά
Περίληψη:
We consider (n,f)-evacuation from a disk, a problem in which n>1 robots, f of which are faulty, seek to evacuate through a hidden exit which is located on the perimeter of a unit disk. We focus on symmetric-persistent algorithms, a common natural approach to search and evacuation problems. We consider two communication models: wireless and face-to-face. For the wireless model we first prove a lower bound of [Formula presented] for the case of one faulty robot. We also observe an almost matching upper bound obtained by utilizing an earlier search algorithm. We then study the case with two Byzantine robots and we provide an algorithm that achieves evacuation in time at most [Formula presented], where δ(n) is a decreasing function with maximum value δ(4)=0.5687, vanishing for n≥9. For the face-to-face model we provide an upper bound of [Formula presented] for evacuation of n robots under crash faults, an upper bound of [Formula presented] for evacuation in the case of one Byzantine robot and an upper bound of [Formula presented] in the case of two Byzantine robots. © 2023 Elsevier B.V.
Συγγραφείς:
Leonardos, N.
Pagourtzis, A.
Papaioannou, I.
Περιοδικό:
Theoretical Computer Science
Λέξεις-κλειδιά:
Byzantine fault; Crash faults; Evacuation; Face to face; Face-to-face communications; Fault-tolerant; Symmetrics; Upper Bound; Wireless communication face-to-face communication; Wireless communications, Robots
DOI:
10.1016/j.tcs.2023.113839
