All You Need is DAG

Keidar I, Kokoris Kogias E, Naor O, Spiegelman A. 2021. All You Need is DAG. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 165–175.


Conference Paper | Published | English

Scopus indexed
Author
Keidar, Idit; Kokoris Kogias, LefterisISTA; Naor, Oded; Spiegelman, Alexander
Department
Abstract
We present DAG-Rider, the first asynchronous Byzantine Atomic Broadcast protocol that achieves optimal resilience, optimal amortized communication complexity, and optimal time complexity. DAG-Rider is post-quantum safe and ensures that all values proposed by correct processes eventually get delivered. We construct DAG-Rider in two layers: In the first layer, processes reliably broadcast their proposals and build a structured Directed Acyclic Graph (DAG) of the communication among them. In the second layer, processes locally observe their DAGs and totally order all proposals with no extra communication.
Publishing Year
Date Published
2021-07-21
Proceedings Title
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
Acknowledgement
Oded Naor is grateful to the Technion Hiroshi Fujiwara Cyber-Security Research Center for providing a research grant. Part of Oded’s work was done while at Novi Research. This work was funded by the Novi team at Facebook. We also wish to thank the Novi Research team for valuable feedback, and in particular George Danezis, Alberto Sonnino, and Dahlia Malkhi.
Page
165-175
Conference
PODC: Principles of Distributed Computing
Conference Location
Virtual, Italy
Conference Date
2021-07-26 – 2021-07-30
IST-REx-ID

Cite this

Keidar I, Kokoris Kogias E, Naor O, Spiegelman A. All You Need is DAG. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2021:165-175. doi:10.1145/3465084.3467905
Keidar, I., Kokoris Kogias, E., Naor, O., & Spiegelman, A. (2021). All You Need is DAG. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (pp. 165–175). Virtual, Italy: Association for Computing Machinery. https://doi.org/10.1145/3465084.3467905
Keidar, Idit, Eleftherios Kokoris Kogias, Oded Naor, and Alexander Spiegelman. “All You Need Is DAG.” In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, 165–75. Association for Computing Machinery, 2021. https://doi.org/10.1145/3465084.3467905.
I. Keidar, E. Kokoris Kogias, O. Naor, and A. Spiegelman, “All You Need is DAG,” in Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Virtual, Italy, 2021, pp. 165–175.
Keidar I, Kokoris Kogias E, Naor O, Spiegelman A. 2021. All You Need is DAG. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 165–175.
Keidar, Idit, et al. “All You Need Is DAG.” Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2021, pp. 165–75, doi:10.1145/3465084.3467905.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2102.08325

Search this title in

Google Scholar
ISBN Search