Byzantine Resilience of Robot Gathering under Round-Robin Scheduling
We study deterministic gathering of $n$ anonymous, oblivious mobile robots in the plane under round-robin scheduling with rigid movement, in the presence of $f$ Byzantine robots. Robots observe all robot positions with their multiplicities, while their local coordinate systems may change adversarially between activations. The goal is for all correct robots to gather at a single point in finite time and remain there forever. We analyze ToMax, a simple algorithm that moves to a point of maximum multiplicity and stays still if and only if its current position is the unique maximum. We prove that ToMax achieves gathering whenever $f\le\lfloor\sqrt{n}/2\rfloor$, establishing an $Ω(\sqrt{n})$ lower bound on the achievable Byzantine resilience.
Authors
- Fabian Frei (ORCID: https://orcid.org/0000-0002-1368-3205)
- Yuichi Sudo (ORCID: https://orcid.org/0000-0002-4442-1750)
- Koichi Wada
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-17
- DOI
- https://doi.org/10.48550/arxiv.2611.22631
- Primary Topic
- Optimization and Search Problems
- Type
- preprint