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. Conferences, Workshops, Symposiums, and Seminars
  4. Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!
 
conference paper

Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!

Civit, Pierre
•
Dzulfikar, Muhammad Ayaz
•
Gilbert, Seth  
Show more
2022
LIPIcs–Leibniz International Proceedings in Informatic
36th International Symposium on Distributed Computing (DISC 2022)

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.

  • Files
  • Details
  • Metrics
Type
conference paper
Author(s)
Civit, Pierre
Dzulfikar, Muhammad Ayaz
Gilbert, Seth  
Gramoli, Vincent  
Guerraoui, Rachid  
Komatovic, Jovan  
Ribeiro Vidigueira, Manuel José  
Date Issued

2022

Publisher

Dagstuhl Publishing

Publisher place

Hannover

Published in
LIPIcs–Leibniz International Proceedings in Informatic
Issue

11

Start page

1:11

End page

1:19

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event nameEvent placeEvent date
36th International Symposium on Distributed Computing (DISC 2022)

Augusta, Georgia, USA

October 25-27, 2022

RelationURL/DOI

IsPreviousVersionOf

https://infoscience.epfl.ch/record/308405
Available on Infoscience
August 30, 2022
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/190449
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