Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!
 
research article

Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!

Civit, Pierre
•
Dzulfikar, Muhammad Ayaz
•
Gilbert, Seth
Show more
December 11, 2023
Distributed Computing

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic (in the number of processes) communication complexity in the worst case: given a system with n processes and at most f < n/3 failures, any solution to Byzantine consensus exchanges Omega(n(2)) words, where a word contains a constant number of values and signatures. 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 where the network alternates between (1) asynchronous periods, with unbounded message delays, and (2) synchronous periods, with delta-bounded message delays. 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 O(n(2)) worst-case communication complexity. In addition, SQUAD is optimally-resilient (tolerating up to f < n/3 failures) and achieves O(f & sdot; delta) 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 O(n(2)) communication complexity and O(f & sdot; delta) latency complexity, which we utilize in order to obtain SQUAD.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

s00446-023-00458-w.pdf

Type

Publisher

Version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

License Condition

CC BY

Size

996.25 KB

Format

Adobe PDF

Checksum (MD5)

0b5dc14aabbff374aef2dc1dfded40c5

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés