1 Search Results for "Shadagopan, Nischith"

Document

DOI: 10.4230/LIPIcs.OPODIS.2022.13

Randomized Byzantine Gathering in Rings

Authors: John Augustine, Arnhav Datar, and Nischith Shadagopan

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

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.

Cite as

John Augustine, Arnhav Datar, and Nischith Shadagopan. Randomized Byzantine Gathering in Rings. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.13},
  URN =		{urn:nbn:de:0030-drops-176333},
  doi =		{10.4230/LIPIcs.OPODIS.2022.13},
  annote =	{Keywords: Mobile agents and robots}
}

Refine by Author
1 Augustine, John
1 Datar, Arnhav
1 Shadagopan, Nischith

Refine by Classification
1 Computing methodologies → Self-organization
1 Theory of computation → Self-organization

Refine by Keyword
1 Mobile agents and robots

Refine by Type
1 document

Refine by Publication Year
1 2023

1 Search Results for "Shadagopan, Nischith"

Randomized Byzantine Gathering in Rings

Abstract

Cite as

Thanks for your feedback!

Could not send message