Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Byzantine Convergence in Robot Networks: The Price of Asynchrony
verfasst von : Zohir Bouzid, Maria Gradinariu Potop-Butucaru, Sébastien Tixeuil
Erschienen in: Principles of Distributed Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.