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

DOI10.1007/S00446-023-00458-WMaRDI QIDQ6579852FDOQ6579852

Authors: Muhammad Ayaz Dzulfikar, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui 

Publication date: 26 July 2024

Published in: Distributed Computing (Search for Journal in Brave)

zbMATH Keywords

communication complexitylatency complexityoptimal Byzantine consensus

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Unreliable failure detectors for reliable distributed systems
• Authenticated Algorithms for Byzantine Agreement
• Impossibility of distributed consensus with one faulty process
• The Byzantine Generals Problem
• Born and raised distributively: fully distributed non-interactive adaptively-secure threshold signatures with short shares
• Round-by-round fault detectors (extended abstract), unifying synchrony and asynchrony
• Byzantine Fault Detectors for Solving Consensus
• Bounds on information exchange for Byzantine agreement
• Title not available (Why is that?)
• Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography
• Dynamic fault-tolerant clock synchronization
• Timeliness, failure-detectors, and consensus performance
• Asynchronous byzantine agreement protocols
• The weakest failure detector for solving consensus
• Thunderella: blockchains with optimistic instant confirmation
• Signature-free asynchronous binary Byzantine consensus with \(t<n/3\), \(O(n^2)\) messages, and \(O(1)\) expected time
• Bootstrapping the blockchain, with applications to consensus and fast PKI setup
• PoW-based distributed cryptography with no trusted setup
• Communication Complexity of Byzantine Agreement, Revisited
• Asymptotically Optimal Validated Asynchronous Byzantine Agreement
• HotStuff
• Breaking the \(O(n^2)\) bit barrier, scalable Byzantine agreement with an adaptive adversary
• Title not available (Why is that?)
• On the communication efficiency of statistically secure asynchronous MPC with optimal resilience
• Brief Announcement: Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP
• Reaching consensus for asynchronous distributed key generation
• Dumbo-MVBA: Optimal Multi-Valued Validated Asynchronous Byzantine Agreement, Revisited
• Revisiting Optimal Resilience of Fast Byzantine Consensus
• Efficient and Adaptively Secure Asynchronous Binary Agreement via Binding Crusader Agreement
• Making Byzantine consensus live
• Expected linear round synchronization: the missing link for linear Byzantine SMR

This page was built for publication: Byzantine consensus is \(\Theta(n^2)\): the Dolev-Reischuk bound is tight even in partial synchrony!

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6579852)