All You Need is DAG

Keidar, Idit; Kokoris Kogias, Eleftherios; Naor, Oded; Spiegelman, Alexander

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.

Download (ext.)

https://arxiv.org/abs/2102.08325 [Preprint]

DOI

10.1145/3465084.3467905

Conference Paper | Published | English

Scopus indexed

Author

Keidar, Idit; Kokoris Kogias, Lefteris^ISTA; Naor, Oded; Spiegelman, Alexander

Department

Kokoris Group

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

2021

Date Published

2021-07-21

Proceedings Title

Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

Publisher

Association for Computing Machinery

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

ISBN

978-1-4503-8548-0

IST-REx-ID

10554

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, 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: