9 Search Results for "Saia, Jared"

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.OPODIS.2025.26
Recognizing Hereditary Properties in the Presence of Byzantine Nodes

Authors: David Cifuentes-Núñez, Pedro Montealegre, and Ivan Rapaport

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

Abstract
Augustine et al. [DISC 2022] initiated the study of distributed graph algorithms in the presence of Byzantine nodes in the congested clique model. In this model, there is a set B of Byzantine nodes, where |B| is less than a third of the total number of nodes. These nodes have complete knowledge of the network and the state of other nodes, and they conspire to alter the output of the system. The authors addressed the connectivity problem, showing that it is solvable under the promise that either the subgraph induced by the honest nodes is connected, or the graph has 2|B|+1 connected components. In the current work, we continue the study of the Byzantine congested clique model by considering the recognition of other graph properties, specifically hereditary properties. A graph property is hereditary if it is closed under taking induced subgraphs. Examples of hereditary properties include acyclicity, bipartiteness, planarity, and bounded (chromatic, independence) number, etc. For each class of graphs 𝒢 satisfying a hereditary property (a hereditary graph-class), we propose a randomized algorithm which, with high probability, (1) accepts if the input graph G belongs to 𝒢, and (2) rejects if G contains at least |B| + 1 disjoint subgraphs not belonging to 𝒢. The round complexity of our algorithm is 𝒪(((log (|𝒢_n|))/n) +|B|) ⋅polylog(n)) , where 𝒢_n is the set of n-node graphs in 𝒢. Finally, we obtain an impossibility result that proves that our result is tight. Indeed, we consider the hereditary class of acyclic graphs, and we prove that there is no algorithm that can distinguish between a graph being acyclic and a graph having |B| disjoint cycles.
Cite as

David Cifuentes-Núñez, Pedro Montealegre, and Ivan Rapaport. Recognizing Hereditary Properties in the Presence of Byzantine Nodes. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cifuentesnunez_et_al:LIPIcs.OPODIS.2025.26,
  author =	{Cifuentes-N\'{u}\~{n}ez, David and Montealegre, Pedro and Rapaport, Ivan},
  title =	{{Recognizing Hereditary Properties in the Presence of Byzantine Nodes}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{26:1--26:15},
  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.26},
  URN =		{urn:nbn:de:0030-drops-251990},
  doi =		{10.4230/LIPIcs.OPODIS.2025.26},
  annote =	{Keywords: Byzantine protocols, congested clique, hereditary properties}
}
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
DOI: 10.4230/LIPIcs.AFT.2025.13
Composable Byzantine Agreements with Reorder Attacks

Authors: Jing Chen, Jin Dong, Jichen Li, Xuanzhi Xia, and Wentao Zhou

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
Byzantine agreement (BA) is a foundational building block in distributed systems that has been extensively studied for decades. With the growing demand for protocol composition in practice, the security analysis of BA protocols under multi-instance executions has attracted increasing attention. However, most existing adversary models focus solely on party corruption and neglect important threats posed by adversarial manipulations of communication channels in the network. Through channel attacks, messages can be reordered across multiple executions and lead to violations of the protocol’s security guarantees, without the participating parties being corrupted. In this work, we present the first adversary model that combines party corruption and channel attacks. Based on this model, we establish new security thresholds for Byzantine agreement under parallel and concurrent compositions, supported by complementary impossibility and possibility results that match each other to form a tight bound. For the impossibility result, we show that even authenticated Byzantine agreement protocols cannot be secure under parallel composition when n ≤ 3t or n ≤ 2c + 2t + 1, where t and c denote the number of corrupted parties and communication channels, respectively. For the possibility result, we prove the existence of secure protocols for unauthenticated Byzantine agreement under parallel and concurrent composition, when n > 3t and n > 2c+2t+1. More specifically, we provide a general black-box compiler that transforms any single-instance secure BA protocol into one that is secure under parallel executions, and we provide a non-black-box construction for concurrent compositions.
Cite as

Jing Chen, Jin Dong, Jichen Li, Xuanzhi Xia, and Wentao Zhou. Composable Byzantine Agreements with Reorder Attacks. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.AFT.2025.13,
  author =	{Chen, Jing and Dong, Jin and Li, Jichen and Xia, Xuanzhi and Zhou, Wentao},
  title =	{{Composable Byzantine Agreements with Reorder Attacks}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{13:1--13:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.13},
  URN =		{urn:nbn:de:0030-drops-247321},
  doi =		{10.4230/LIPIcs.AFT.2025.13},
  annote =	{Keywords: Byzantine agreement, protocol composition, channel reorder attack, security threshold}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.12
How Much Public Randomness Do Modern Consensus Protocols Need?

Authors: Joseph Bonneau, Benedikt Bünz, Miranda Christ, and Yuval Efron

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
Modern blockchain-based consensus protocols aim for efficiency (i.e., low communication and round complexity) while maintaining security against adaptive adversaries. These goals are usually achieved using a public randomness beacon to select roles for each participant. We examine to what extent this randomness is necessary. Specifically, we provide tight bounds on the amount of entropy a Byzantine Agreement protocol must consume from a beacon in order to enjoy efficiency and adaptive security. We first establish that no consensus protocol can simultaneously be efficient, be adaptively secure, and use O(log n) bits of beacon entropy. We then show this bound is tight and, in fact, a trilemma by presenting three consensus protocols that achieve any two of these three properties.
Cite as

Joseph Bonneau, Benedikt Bünz, Miranda Christ, and Yuval Efron. How Much Public Randomness Do Modern Consensus Protocols Need?. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bonneau_et_al:LIPIcs.AFT.2025.12,
  author =	{Bonneau, Joseph and B\"{u}nz, Benedikt and Christ, Miranda and Efron, Yuval},
  title =	{{How Much Public Randomness Do Modern Consensus Protocols Need?}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.12},
  URN =		{urn:nbn:de:0030-drops-247310},
  doi =		{10.4230/LIPIcs.AFT.2025.12},
  annote =	{Keywords: Consensus, Randomness Beacon}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.14
Testing Sumsets Is Hard

Authors: Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, and Or Zamir

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A subset S of the Boolean hypercube 𝔽₂ⁿ is a sumset if S = {a + b : a, b ∈ A} for some A ⊆ 𝔽₂ⁿ. Sumsets are central objects of study in additive combinatorics, where they play a role in several of the field’s most important results. We prove a lower bound of Ω(2^{n/2}) for the number of queries needed to test whether a Boolean function f:𝔽₂ⁿ → {0,1} is the indicator function of a sumset, ruling out an efficient testing algorithm for sumsets. Our lower bound for testing sumsets follows from sharp bounds on the related problem of shift testing, which may be of independent interest. We also give a near-optimal {2^{n/2} ⋅ poly(n)}-query algorithm for a smoothed analysis formulation of the sumset refutation problem. Finally, we include a simple proof that the number of different sumsets in 𝔽₂ⁿ is 2^{(1±o(1))2^{n-1}}.
Cite as

Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, and Or Zamir. Testing Sumsets Is Hard. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ESA.2025.14,
  author =	{Chen, Xi and Nadimpalli, Shivam and Randolph, Tim and Servedio, Rocco A. and Zamir, Or},
  title =	{{Testing Sumsets Is Hard}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.14},
  URN =		{urn:nbn:de:0030-drops-244822},
  doi =		{10.4230/LIPIcs.ESA.2025.14},
  annote =	{Keywords: Sumsets, additive combinatorics, property testing, Boolean functions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.59
Error Correction for Message Streams

Authors: Meghal Gupta and Rachel Yun Zhang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In the setting of error correcting codes, Alice wants to send a message x ∈ {0,1}ⁿ to Bob via an encoding enc(x) that is resilient to error. In this work, we investigate the scenario where Bob is a low space decoder. More precisely, he receives Alice’s encoding enc(x) bit-by-bit and desires to compute some function f(x) in low space. A generic error-correcting code does not accomplish this because decoding is a very global process and requires at least linear space. Locally decodable codes partially solve this problem as they allow Bob to learn a given bit of x in low space, but not compute a generic function f. Our main result is an encoding and decoding procedure where Bob is still able to compute any such function f in low space when a constant fraction of the stream is corrupted. More precisely, we describe an encoding function enc(x) of length poly(n) so that for any decoder (streaming algorithm) A that on input x computes f(x) in space s, there is an explicit decoder B that computes f(x) in space s ⋅ polylog(n) as long as there were not more than 1/4 - ε fraction of (adversarial) errors in the input stream enc(x).
Cite as

Meghal Gupta and Rachel Yun Zhang. Error Correction for Message Streams. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.ITCS.2025.59,
  author =	{Gupta, Meghal and Zhang, Rachel Yun},
  title =	{{Error Correction for Message Streams}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{59:1--59:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.59},
  URN =		{urn:nbn:de:0030-drops-226875},
  doi =		{10.4230/LIPIcs.ITCS.2025.59},
  annote =	{Keywords: error-correcting codes, streaming algorithms, space-efficient algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.36
Fraud Detection for Random Walks

Authors: Varsha Dani, Thomas P. Hayes, Seth Pettie, and Jared Saia

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Traditional fraud detection is often based on finding statistical anomalies in data sets and transaction histories. A sophisticated fraudster, aware of the exact kinds of tests being deployed, might be difficult or impossible to catch. We are interested in paradigms for fraud detection that are provably robust against any adversary, no matter how sophisticated. In other words, the detection strategy should rely on signals in the data that are inherent in the goals the adversary is trying to achieve. Specifically, we consider a fraud detection game centered on a random walk on a graph. We assume this random walk is implemented by having a player at each vertex, who can be honest or not. In particular, when the random walk reaches a vertex owned by an honest player, it proceeds to a uniformly random neighbor at the next timestep. However, when the random walk reaches a dishonest player, it instead proceeds to an arbitrary neighbor chosen by an omniscient Adversary. The game is played between the Adversary and a Referee who sees the trajectory of the random walk. At any point during the random walk, if the Referee determines that a {specific} vertex is controlled by a dishonest player, the Referee accuses that player, and therefore wins the game. The Referee is allowed to make the occasional incorrect accusation, but must follow a policy that makes such mistakes with small probability of error. The goal of the adversary is to make the cover time large, ideally infinite, i.e., the walk should never reach at least one vertex. We consider the following basic question: how much can the omniscient Adversary delay the cover time without getting caught? Our main result is a tight upper bound on this delay factor. We also discuss possible applications of our results to settings such as Rotor Walks, Leader Election, and Sybil Defense.
Cite as

Varsha Dani, Thomas P. Hayes, Seth Pettie, and Jared Saia. Fraud Detection for Random Walks. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dani_et_al:LIPIcs.ITCS.2024.36,
  author =	{Dani, Varsha and Hayes, Thomas P. and Pettie, Seth and Saia, Jared},
  title =	{{Fraud Detection for Random Walks}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{36:1--36:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.36},
  URN =		{urn:nbn:de:0030-drops-195645},
  doi =		{10.4230/LIPIcs.ITCS.2024.36},
  annote =	{Keywords: Fraud detection, random processes, Markov chains}
}
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}
}
  • Refine by Type
  • 9 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 5 2025
  • 1 2024
  • 1 2020

  • Refine by Author
  • 3 Augustine, John
  • 2 King, Valerie
  • 2 Saia, Jared
  • 1 Bonneau, Joseph
  • 1 Bünz, Benedikt
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs

  • Refine by Classification
  • 6 Theory of computation → Distributed algorithms
  • 1 Mathematics of computing → Coding theory
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Mathematics of computing → Probability and statistics
  • Show More...

  • Refine by Keyword
  • 2 Byzantine agreement
  • 2 Byzantine protocols
  • 1 Blockchain Oracle
  • 1 Boolean functions
  • 1 Byzantine Fault Tolerance
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact