2009 | OriginalPaper | Chapter
Byzantine Convergence in Robot Networks: The Price of Asynchrony
Authors : Zohir Bouzid, Maria Gradinariu Potop-Butucaru, Sébastien Tixeuil
Published in: Principles of Distributed Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the convergence problem in fully asynchronous, uni-dimensional robot networks that are prone to Byzantine (
i.e.
malicious) failures. In these settings, oblivious anonymous robots with arbitrary initial positions are required to eventually converge to an
a priori
unknown position despite a subset of them exhibiting Byzantine behavior. Our contribution is twofold. We propose a deterministic algorithm that solves the problem in the most generic settings: fully asynchronous robots that operate in the non-atomic CORDA model. Our algorithm provides convergence in 5
f
+ 1-sized networks where
f
is the upper bound on the number of Byzantine robots. Additionally, we prove that 5
f
+ 1 is a lower bound whenever robot scheduling is fully asynchronous. This constrasts with previous results in partially synchronous robot networks, where 3
f
+ 1 robots are necessary and sufficient.