Home > Research > Publications & Outputs > Fully-Distributed Byzantine Agreement in Sparse...

Research

Electronic data

Links

Text available via DOI:

Keywords

View graph of relations

Fully-Distributed Byzantine Agreement in Sparse Networks

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Published

Standard

Fully-Distributed Byzantine Agreement in Sparse Networks. / Augustine, John; Dufoulon, Fabien; Pandurangan, Gopal.
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ed. / Yossi Azar; Debmalya Panigrahi. SIAM, 2025. p. 4172-4197.

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Harvard

Augustine, J, Dufoulon, F & Pandurangan, G 2025, Fully-Distributed Byzantine Agreement in Sparse Networks. in Y Azar & D Panigrahi (eds), Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, pp. 4172-4197. https://doi.org/10.1137/1.9781611978322.142

APA

Augustine, J., Dufoulon, F., & Pandurangan, G. (2025). Fully-Distributed Byzantine Agreement in Sparse Networks. In Y. Azar, & D. Panigrahi (Eds.), Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 4172-4197). SIAM. https://doi.org/10.1137/1.9781611978322.142

Vancouver

Augustine J, Dufoulon F, Pandurangan G. Fully-Distributed Byzantine Agreement in Sparse Networks. In Azar Y, Panigrahi D, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2025. p. 4172-4197 doi: 10.1137/1.9781611978322.142

Author

Augustine, John ; Dufoulon, Fabien ; Pandurangan, Gopal. / Fully-Distributed Byzantine Agreement in Sparse Networks. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). editor / Yossi Azar ; Debmalya Panigrahi. SIAM, 2025. pp. 4172-4197

Bibtex

@inproceedings{804cd2786aed472aa094cd065c7400ca,
title = "Fully-Distributed Byzantine Agreement in Sparse Networks",
abstract = "Byzantine agreement is a fundamental problem in fault-tolerant distributed networks that has been studied intensively for the last four decades. Most of these works designed protocols for \emph{complete} networks. A key goal in Byzantine protocols is to tolerate as many Byzantine nodes as possible --- up to $O(n)$ Byzantine nodes ($n$ is the total network size).The work of Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] was the first to address the Byzantine agreement problem in \emph{sparse, bounded degree} networks and presented a protocol that achieved \emph{almost-everywhere} agreement among honest nodes.In such networks, all known Byzantine agreement protocols (e.g., Dwork, Peleg, Pippenger, and Upfal, STOC 1986; Upfal, PODC 1992; King, Saia, Sanwalani, and Vee, FOCS 2006) that tolerated a large number of Byzantine nodes had a major drawback that they were \emph{not fully-distributed} --- in those protocols, nodes are required to have initial knowledge of the entire network topolog",
keywords = "Distributed algorithms, Byzantine Agreement, Fault Tolerance",
author = "John Augustine and Fabien Dufoulon and Gopal Pandurangan",
year = "2025",
month = jan,
day = "7",
doi = "10.1137/1.9781611978322.142",
language = "English",
pages = "4172--4197",
editor = "Yossi Azar and Debmalya Panigrahi",
booktitle = "Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)",
publisher = "SIAM",

}

RIS

TY - GEN

T1 - Fully-Distributed Byzantine Agreement in Sparse Networks

AU - Augustine, John

AU - Dufoulon, Fabien

AU - Pandurangan, Gopal

PY - 2025/1/7

Y1 - 2025/1/7

N2 - Byzantine agreement is a fundamental problem in fault-tolerant distributed networks that has been studied intensively for the last four decades. Most of these works designed protocols for \emph{complete} networks. A key goal in Byzantine protocols is to tolerate as many Byzantine nodes as possible --- up to $O(n)$ Byzantine nodes ($n$ is the total network size).The work of Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] was the first to address the Byzantine agreement problem in \emph{sparse, bounded degree} networks and presented a protocol that achieved \emph{almost-everywhere} agreement among honest nodes.In such networks, all known Byzantine agreement protocols (e.g., Dwork, Peleg, Pippenger, and Upfal, STOC 1986; Upfal, PODC 1992; King, Saia, Sanwalani, and Vee, FOCS 2006) that tolerated a large number of Byzantine nodes had a major drawback that they were \emph{not fully-distributed} --- in those protocols, nodes are required to have initial knowledge of the entire network topolog

AB - Byzantine agreement is a fundamental problem in fault-tolerant distributed networks that has been studied intensively for the last four decades. Most of these works designed protocols for \emph{complete} networks. A key goal in Byzantine protocols is to tolerate as many Byzantine nodes as possible --- up to $O(n)$ Byzantine nodes ($n$ is the total network size).The work of Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] was the first to address the Byzantine agreement problem in \emph{sparse, bounded degree} networks and presented a protocol that achieved \emph{almost-everywhere} agreement among honest nodes.In such networks, all known Byzantine agreement protocols (e.g., Dwork, Peleg, Pippenger, and Upfal, STOC 1986; Upfal, PODC 1992; King, Saia, Sanwalani, and Vee, FOCS 2006) that tolerated a large number of Byzantine nodes had a major drawback that they were \emph{not fully-distributed} --- in those protocols, nodes are required to have initial knowledge of the entire network topolog

KW - Distributed algorithms

KW - Byzantine Agreement

KW - Fault Tolerance

U2 - 10.1137/1.9781611978322.142

DO - 10.1137/1.9781611978322.142

M3 - Conference contribution/Paper

SP - 4172

EP - 4197

BT - Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

A2 - Azar, Yossi

A2 - Panigrahi, Debmalya

PB - SIAM

ER -