License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2022.13
URN: urn:nbn:de:0030-drops-176333
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17633/
Go to the corresponding LIPIcs Volume Portal

Augustine, John ; Datar, Arnhav ; Shadagopan, Nischith

Randomized Byzantine Gathering in Rings

pdf-format:
LIPIcs-OPODIS-2022-13.pdf (0.8 MB)

Abstract

We study the problem of gathering k anonymous mobile agents on a ring with n nodes. Importantly, f out of the k anonymous agents are Byzantine. The agents operate synchronously and in an autonomous fashion. In each round, each agent can communicate with other agents co-located with it by broadcasting a message. After receiving all the messages, each agent decides to either move to a neighbouring node or stay put. We begin with the k agents placed arbitrarily on the ring, and the task is to gather all the good agents in a single node. The task is made harder by the presence of Byzantine agents, which are controlled by a single Byzantine adversary. Byzantine agents can deviate arbitrarily from the protocol. The Byzantine adversary is computationally unbounded. Additionally, the Byzantine adversary is adaptive in the sense that it can capitalize on information gained over time (including the current round) to choreograph the actions of Byzantine agents. Specifically, the entire state of the system, which includes messages sent by all the agents and any random bits generated by the agents, is known to the Byzantine adversary before all the agents move. Thus the Byzantine adversary can compute the positioning of good agents across the ring and choreograph the movement of Byzantine agents accordingly. Moreover, we consider two settings: standard and visual tracking setting. With visual tracking, agents have the ability to track other agents that are moving along with them. In the standard setting, agents do not have such an ability.
In the standard setting we can achieve gathering in ?(nlog nlog k) rounds with high probability and can handle ?(k/(log k)) number of Byzantine agents. With visual tracking, we can achieve gathering faster in ?(n log n) rounds whp and can handle any constant fraction of the total number of agents being Byzantine.

BibTeX - Entry

@InProceedings{augustine_et_al:LIPIcs.OPODIS.2022.13,
  author =	{Augustine, John and Datar, Arnhav and Shadagopan, Nischith},
  title =	{{Randomized Byzantine Gathering in Rings}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17633},
  URN =		{urn:nbn:de:0030-drops-176333},
  doi =		{10.4230/LIPIcs.OPODIS.2022.13},
  annote =	{Keywords: Mobile agents and robots}
}

Keywords: Mobile agents and robots
Collection: 26th International Conference on Principles of Distributed Systems (OPODIS 2022)
Issue Date: 2023
Date of publication: 15.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI