Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2009-08-04
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
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 apriori 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 5f+1-sized networks where f is the upper bound on the number of Byzantine robots. Additionally, we prove that 5f+1 is a lower bound whenever robot scheduling is fully asynchronous. This constrasts with previous results in partially synchronous robots networks, where 3f+1 robots are necessary and sufficient.
Bouzid Zohir
Potop-Butucaru Maria
Tixeuil Sébastien
No associations
LandOfFree
Byzantine Convergence in Robots Networks: The Price of Asynchrony does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Byzantine Convergence in Robots Networks: The Price of Asynchrony, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Byzantine Convergence in Robots Networks: The Price of Asynchrony will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-556725