Search Results

Documents authored by Augustine, John

Document
DOI: 10.4230/LIPIcs.OPODIS.2025.18
Distributed Download from an External Data Source in Asynchronous Faulty Settings

Authors: John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, and David Peleg

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
The distributed Data Retrieval (DR) model consists of k peers connected by a complete peer-to-peer communication network, and a trusted external data source that stores an array X of n bits (n ≫ k). Up to β k of the peers might fail in any execution (for β ∈ [0, 1)). Peers can obtain the information either by inexpensive messages passed among themselves or through expensive queries to the source array X. In the DR model, we focus on designing protocols that minimize the number of queries performed by any nonfaulty peer (a measure referred to as the query complexity) while maximizing the resiliency parameter β. The Download problem requires each nonfaulty peer to correctly learn the entire array X. Earlier work on this problem focused on synchronous communication networks and established several deterministic and randomized upper and lower bounds. Our work is the first to extend the study of distributed data retrieval to asynchronous communication networks. We address the Download problem under both the Byzantine and crash failure models. We present query-optimal deterministic solutions in an asynchronous model that can tolerate any fixed fraction β < 1 of crash faults. In the Byzantine failure model, it is known that deterministic protocols incur a query complexity of Ω(n) per peer, even under synchrony. We extend this lower bound to randomized protocols in the asynchronous model for β ≥ 1/2, and further show that for β < 1/2, a randomized protocol exists with near-optimal query complexity.
Cite as

John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, and David Peleg. Distributed Download from an External Data Source in Asynchronous Faulty Settings. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.OPODIS.2025.18,
  author =	{Augustine, John and Chatterjee, Soumyottam and King, Valerie and Kumar, Manish and Meir, Shachar and Peleg, David},
  title =	{{Distributed Download from an External Data Source in Asynchronous Faulty Settings}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.18},
  URN =		{urn:nbn:de:0030-drops-251915},
  doi =		{10.4230/LIPIcs.OPODIS.2025.18},
  annote =	{Keywords: Byzantine Fault Tolerance, Blockchain Oracle, Data Retrieval Model, Distributed Download, asynchrony}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.9
Distributed Download from an External Data Source in Byzantine Majority Settings

Authors: John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, and David Peleg

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We consider the Download problem in the Data Retrieval Model, introduced in DISC'24, where a distributed set of peers, some of which may be Byzantine, seek to learn n bits of data stored at a trustworthy external data source. Each bit of data can be learned by a peer either through a direct and costly query of the source or through other peers that have already learned it; the goal is to design a collaborative protocol that reduces the query complexity defined as the maximum number of bits queried by any honest peer. We begin with a randomized protocol for the Download problem that achieves optimal query complexity, up to a logarithmic factor. For a stronger "dynamic" adversary that can change the set of Byzantine peers from one round to the next, we achieve optimality (within log factors) for both query complexity (in expectation) and time complexity, but with larger messages. In broadcast communication, where all peers (including Byzantine peers) are required to send the same message to all peers, we achieve (up to log factors) an optimal trade-off between query complexity, time complexity, and message size with the dynamic adversary. All of our protocols can tolerate any constant fraction β < 1 of Byzantine peers.
Cite as

John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, and David Peleg. Distributed Download from an External Data Source in Byzantine Majority Settings. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.DISC.2025.9,
  author =	{Augustine, John and Chatterjee, Soumyottam and King, Valerie and Kumar, Manish and Meir, Shachar and Peleg, David},
  title =	{{Distributed Download from an External Data Source in Byzantine Majority Settings}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{9:1--9:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.9},
  URN =		{urn:nbn:de:0030-drops-248262},
  doi =		{10.4230/LIPIcs.DISC.2025.9},
  annote =	{Keywords: Byzantine Fault Tolerance, Blockchain Oracle, Data Retrieval Model, Distributed Download}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.47
Brief Announcement: Highly Dynamic and Fully Distributed Data Structures

Authors: John Augustine, Antonio Cruciani, and Iqra Altaf Gillani

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We study robust and efficient distributed algorithms for building and maintaining distributed data structures in dynamic Peer-to-Peer (P2P) networks. P2P networks are characterized by a high level of dynamicity with abrupt heavy node churn (nodes that join and leave the network continuously over time). We present a novel algorithmic framework to build and maintain, with high probability, a skip list for poly(n) rounds despite a churn rate of 𝒪(n/log n), which is the number of nodes joining and/or leaving per round; n is the stable network size. We assume that the churn is controlled by an oblivious adversary that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Importantly, the maintenance overhead in any interval of time (measured in terms of the total number of messages exchanged and the number of edges formed/deleted) is (up to log factors) proportional to the churn rate. Furthermore, the algorithm is scalable in that the messages are small (i.e., at most polylog(n) bits) and every node sends and receives at most polylog(n) messages per round. To the best of our knowledge, our work provides the first-known fully-distributed data structure and associated algorithms that provably work under highly dynamic settings (i.e., high churn rate that is near-linear in n). Furthermore, the nodes operate in a localized manner. Our framework crucially relies on new distributed and parallel algorithms to merge two n-element skip lists and delete a large subset of items, both in 𝒪(log n) rounds with high probability. These procedures may be of independent interest due to their elegance and potential applicability in other contexts in distributed data structures. Finally, we believe that our framework can be generalized to other distributed and dynamic data structures including graphs, potentially leading to stable distributed computation despite heavy churn.
Cite as

John Augustine, Antonio Cruciani, and Iqra Altaf Gillani. Brief Announcement: Highly Dynamic and Fully Distributed Data Structures. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 47:1-47:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.DISC.2025.47,
  author =	{Augustine, John and Cruciani, Antonio and Gillani, Iqra Altaf},
  title =	{{Brief Announcement: Highly Dynamic and Fully Distributed Data Structures}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{47:1--47:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.47},
  URN =		{urn:nbn:de:0030-drops-248636},
  doi =		{10.4230/LIPIcs.DISC.2025.47},
  annote =	{Keywords: Peer-to-peer network, dynamic network, data structure, churn, distributed algorithm, randomized algorithm}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.48
Brief Announcement: Distributed Download from an External Data Source in Asynchronous Faulty Settings

Authors: John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, and David Peleg

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
The distributed Data Retrieval (DR) model consists of k peers connected by a complete peer-to-peer communication network, and a trusted external data source that stores an array X of n bits (n ≫ k). Up to β k of the peers might fail in any execution (for β ∈ [0, 1)). Peers can obtain the information either by inexpensive messages passed among themselves or through expensive queries to the source array X. In the DR model, we focus on designing protocols that minimize the number of queries performed by any nonfaulty peer (a measure referred to as query complexity) while maximizing the resilience parameter β. The Download problem requires each nonfaulty peer to correctly learn the entire array X. Earlier work on this problem focused on synchronous communication networks and established several deterministic and randomized upper and lower bounds. Our work is the first to extend the study of distributed data retrieval to asynchronous communication networks. We address the Download problem under both the Byzantine and crash failure models. We present query-optimal deterministic solutions in an asynchronous model that can tolerate any fixed fraction β < 1 of crash faults. In the Byzantine failure model, it is known that deterministic protocols incur a query complexity of Ω(n) per peer, even under synchrony. We extend this lower bound to randomized protocols in the asynchronous model for β ≥ 1/2, and further show that for β < 1/2, a randomized protocol exists with near-optimal query complexity. To the best of our knowledge, this is the first work to address the Download problem in asynchronous communication networks.
Cite as

John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, and David Peleg. Brief Announcement: Distributed Download from an External Data Source in Asynchronous Faulty Settings. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 48:1-48:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.DISC.2025.48,
  author =	{Augustine, John and Chatterjee, Soumyottam and King, Valerie and Kumar, Manish and Meir, Shachar and Peleg, David},
  title =	{{Brief Announcement: Distributed Download from an External Data Source in Asynchronous Faulty Settings}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{48:1--48:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.48},
  URN =		{urn:nbn:de:0030-drops-248646},
  doi =		{10.4230/LIPIcs.DISC.2025.48},
  annote =	{Keywords: Byzantine Fault Tolerance, Blockchain Oracle, Data Retrieval Model, Distributed Download}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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