Search Results

Documents authored by Augustine, John

Document
DOI: 10.4230/LIPIcs.DISC.2024.3
Byzantine Resilient Distributed Computing on External Data

Authors: John Augustine, Jeffin Biju, Shachar Meir, David Peleg, Srikkanth Ramachandran, and Aishwarya Thiruvengadam

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
We study a class of problems we call retrieval problems in which a distributed network has read-only access to a trusted external data source through queries, and each peer is required to output some computable function of the data. To formalize this, we propose the Data Retrieval Model comprising two parts: (1) a congested clique network with k peers, up to β k of which can be Byzantine in every execution (for suitable values of β ∈ [0,1)); (2) a trusted source of data with no computational abilities, called the External Data Source (or just source for short). This source stores an array 𝒳 of n bits (n ≫ k), providing every peer in the congested clique read-only access to 𝒳 through queries. It is assumed that a query to the source is significantly more expensive than a message between two peers in the network. Hence, we prioritize minimizing the number of queries a peer performs over the number of messages it sends. Retrieval problems are easily solved by having each peer query all of 𝒳, so we focus on designing non-trivial query-efficient protocols for retrieval problems in the DR network that achieve low query performance per peer. Specifically, to initiate this study, we present deterministic and randomized upper and lower bounds for two fundamental problems. The first is the Download problem that requires every peer to output an array of n bits identical to 𝒳. The second problem of focus, Disjunction, requires nodes to learn if some bit in 𝒳 is set to 1.
Cite as

John Augustine, Jeffin Biju, Shachar Meir, David Peleg, Srikkanth Ramachandran, and Aishwarya Thiruvengadam. Byzantine Resilient Distributed Computing on External Data. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.DISC.2024.3,
  author =	{Augustine, John and Biju, Jeffin and Meir, Shachar and Peleg, David and Ramachandran, Srikkanth and Thiruvengadam, Aishwarya},
  title =	{{Byzantine Resilient Distributed Computing on External Data}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{3:1--3:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.3},
  URN =		{urn:nbn:de:0030-drops-212304},
  doi =		{10.4230/LIPIcs.DISC.2024.3},
  annote =	{Keywords: Byzantine Fault Tolerance, Blockchain Oracle, Congested Clique, Data Retrieval Model}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.22
Local Recurrent Problems in the SUPPORTED Model

Authors: Akanksha Agrawal, John Augustine, David Peleg, and Srikkanth Ramachandran

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
We study the SUPPORTED model of distributed computing introduced by Schmid and Suomela [Schmid and Suomela, 2013], which generalizes the LOCAL and CONGEST models. In this framework, multiple instances of the same problem, differing from each other by the subnetwork to which they apply. recur over time, and need to be solved efficiently online. To do that, one may rely on an initial preprocessing phase for computing some useful information. This preprocessing phase makes it possible, in some cases, to obtain improved distributed algorithms, overcoming locality-based time lower bounds. Our main contribution is to expand the class of problems to which the SUPPORTED model applies, by handling also multiple recurring instances of the same problem that differ from each other by some problem specific input, and not only the subnetwork to which they apply. We illustrate this by considering two extended problem classes. The first class, denoted PCS, concerns problems where client nodes of the network need to be served, and each recurring instance applies to some Partial Client Set. The second class, denoted PFO, concerns situations where each recurrent instance of the problem includes a partially fixed output, which needs to be completed to a full consistent solution. Specifically, we propose some natural recurrent variants of the dominating set problem and the coloring problem that are of interest particularly in the distributed setting. For these problems, we show that information about the topology can be used to overcome locality-based lower bounds. We also categorize the round complexity of Locally Checkable Labellings in the SUPPORTED model for the simple case of paths. Finally we present some interesting open problems and some partial results towards resolving them.
Cite as

Akanksha Agrawal, John Augustine, David Peleg, and Srikkanth Ramachandran. Local Recurrent Problems in the SUPPORTED Model. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.OPODIS.2023.22,
  author =	{Agrawal, Akanksha and Augustine, John and Peleg, David and Ramachandran, Srikkanth},
  title =	{{Local Recurrent Problems in the SUPPORTED Model}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.22},
  URN =		{urn:nbn:de:0030-drops-195124},
  doi =		{10.4230/LIPIcs.OPODIS.2023.22},
  annote =	{Keywords: Distributed Algorithms, LOCAL Model, SUPPORTED Model}
}
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.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}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.7
Byzantine Connectivity Testing in the Congested Clique

Authors: John Augustine, Anisur Rahaman Molla, Gopal Pandurangan, and Yadu Vasudev

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
We initiate the study of distributed graph algorithms under the presence of Byzantine nodes. We consider the fundamental problem of testing the connectivity of a graph in the congested clique model in a Byzantine setting. We are given a n-vertex (arbitrary) graph G embedded in a n-node congested clique where an arbitrary subset of B nodes of the clique of size up to (1/3-ε)n (for any arbitrary small constant ε > 0) can be Byzantine. We consider the full information model where Byzantine nodes can behave arbitrarily, collude with each other, and have unlimited computational power and full knowledge of the states and actions of the honest nodes, including random choices made up to the current round. Our main result is an efficient randomized distributed algorithm that is able to correctly distinguish between two contrasting cases: (1) the graph G⧵ B (i.e., the graph induced by the removal of the vertices assigned to the Byzantine nodes in the clique) is connected or (2) the graph G is far from connected, i.e., it has at least 2|B|+1 connected components. Our algorithm runs in O(polylog n) rounds in the congested clique model and guarantees that all honest nodes will decide on the correct case with high probability. Since Byzantine nodes can lie about the vertices assigned to them, we show that this is essentially the best possible that can be done by any algorithm. Our result can be viewed also in the spirit of property testing, where our algorithm is able to distinguish between two contrasting cases while giving no guarantees if the graph falls in the grey area (i.e., neither of the cases occur). Our work is a step towards robust and secure distributed graph computation that can output meaningful results even in the presence of a large number of faulty or malicious nodes.
Cite as

John Augustine, Anisur Rahaman Molla, Gopal Pandurangan, and Yadu Vasudev. Byzantine Connectivity Testing in the Congested Clique. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.DISC.2022.7,
  author =	{Augustine, John and Molla, Anisur Rahaman and Pandurangan, Gopal and Vasudev, Yadu},
  title =	{{Byzantine Connectivity Testing in the Congested Clique}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.7},
  URN =		{urn:nbn:de:0030-drops-171987},
  doi =		{10.4230/LIPIcs.DISC.2022.7},
  annote =	{Keywords: Byzantine protocols, distributed graph algorithms, congested clique, graph connectivity, fault-tolerant computation, randomized algorithms}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2022.21
Brief Announcement: Cooperative Guarding in Polygons with Holes

Authors: John Augustine and Srikkanth Ramachandran

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
We study the Cooperative Guarding problem for polygons with holes in a mobile multi-agents setting. Given a set of agents, initially deployed at a point in a polygon with n vertices and h holes, we require the agents to collaboratively explore and position themselves in such a way that every point in the polygon is visible to at least one agent and that the set of agents are visibly connected. We study the problem under two models of computation, one in which the agents can compute exact distances and angles between two points in its visibility, and one in which agents can only compare distances and angles. In the stronger model, we provide a deterministic O(n) round algorithm to compute such a cooperative guard set while not requiring more than (n + h)/2 agents and O(log n) bits of persistent memory per agent. In the weaker model, we provide an O(n⁴) round algorithm, that does not require more than (n+2h)/2 agents.
Cite as

John Augustine and Srikkanth Ramachandran. Brief Announcement: Cooperative Guarding in Polygons with Holes. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 21:1-21:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.SAND.2022.21,
  author =	{Augustine, John and Ramachandran, Srikkanth},
  title =	{{Brief Announcement: Cooperative Guarding in Polygons with Holes}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{21:1--21:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.21},
  URN =		{urn:nbn:de:0030-drops-159636},
  doi =		{10.4230/LIPIcs.SAND.2022.21},
  annote =	{Keywords: Mobile Agents, Art Gallery Problem, Cooperative Guarding}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.31
Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols

Authors: John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
The last decade has seen substantial progress on designing Byzantine agreement algorithms which do not require all-to-all communication. However, these protocols do require each node to play a particular role determined by its ID. Motivated by the rise of permissionless systems such as Bitcoin, where nodes can join and leave at will, we extend this research to a more practical model where initially, each node does not know the identity of its neighbors. In particular, a node can send to new destinations only by sending to random (or arbitrary) nodes, or responding to messages received from those destinations. We assume a synchronous and fully-connected network, with a full-information, but static Byzantine adversary. A major drawback of existing Byzantine protocols in this setting is that they have at least Ω(n²) message complexity, where n is the total number of nodes. In particular, the communication cost incurred by the honest nodes is Ω(n²), even when Byzantine node send no messages. In this paper, we design protocols for fundamental problems which are message-competitive, i.e., the total number of bits sent by honest nodes is not significantly more than the total sent by Byzantine nodes. We describe a message-competitive algorithm to solve Byzantine agreement, leader election, and committee election. Our algorithm sends an expected O((T+n)log n) bits and has latency O(polylog(n)) (even in the CONGEST model), where T = O(n²) is the number of bits sent by Byzantine nodes. The algorithm is resilient to (1/4-ε)n Byzantine nodes for any fixed ε > 0, and succeeds with high probability. Our message bounds are essentially optimal up to polylagarithmic factors, for algorithms that run in polylogarithmic rounds in the CONGEST model. We also show lower bounds for message-competitive Byzantine agreement regardless of rounds. We prove that, in general, one cannot hope to design Byzantine protocols that have communication cost that is significantly smaller than the cost of the Byzantine adversary.
Cite as

John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia. Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.DISC.2020.31,
  author =	{Augustine, John and King, Valerie and Molla, Anisur Rahaman and Pandurangan, Gopal and Saia, Jared},
  title =	{{Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{31:1--31:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.31},
  URN =		{urn:nbn:de:0030-drops-131093},
  doi =		{10.4230/LIPIcs.DISC.2020.31},
  annote =	{Keywords: Byzantine protocols, Byzantine agreement, Leader election, Committee election, Message-competitive protocol, Randomized protocol}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact