License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2022.14
URN: urn:nbn:de:0030-drops-172059
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17205/
Civit, Pierre ;
Dzulfikar, Muhammad Ayaz ;
Gilbert, Seth ;
Gramoli, Vincent ;
Guerraoui, Rachid ;
Komatovic, Jovan ;
Vidigueira, Manuel
Byzantine Consensus Is Θ(n²): The Dolev-Reischuk Bound Is Tight Even in Partial Synchrony!
Abstract
The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT).
This paper closes the existing gap by introducing SQuad, a partially synchronous Byzantine consensus protocol with quadratic worst-case communication complexity. In addition, SQuad is optimally-resilient and achieves linear worst-case latency complexity. The key technical contribution underlying SQuad lies in the way we solve view synchronization, the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we present RareSync, a view synchronization protocol with quadratic communication complexity and linear latency complexity, which we utilize in order to obtain SQuad.
BibTeX - Entry
@InProceedings{civit_et_al:LIPIcs.DISC.2022.14,
author = {Civit, Pierre and Dzulfikar, Muhammad Ayaz and Gilbert, Seth and Gramoli, Vincent and Guerraoui, Rachid and Komatovic, Jovan and Vidigueira, Manuel},
title = {{Byzantine Consensus Is \Theta(n²): The Dolev-Reischuk Bound Is Tight Even in Partial Synchrony!}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {14:1--14: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/opus/volltexte/2022/17205},
URN = {urn:nbn:de:0030-drops-172059},
doi = {10.4230/LIPIcs.DISC.2022.14},
annote = {Keywords: Optimal Byzantine consensus, Communication complexity, Latency complexity}
}
|
Keywords: |
|
Optimal Byzantine consensus, Communication complexity, Latency complexity |
|
Collection: |
|
36th International Symposium on Distributed Computing (DISC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
17.10.2022 |
