On the Validity of Consensus

DOI10.1145/3583668.3594567MaRDI QIDQ6202272zbMATH OpenOpenAlexFDO

Authors Rachid Guerraoui, Seth Gilbert

Publication date 26 March 2024

Published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2301.04920

zbMATH Keywords

lower boundsolvabilitymessage complexityByzantine consensus

Mathematics Subject Classification ID

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

Abstract: The Byzantine consensus problem involves $n$ processes, out of which t < n could be faulty and behave arbitrarily. Three properties characterize consensus: (1) termination, requiring correct (non-faulty) processes to eventually reach a decision, (2) agreement, preventing them from deciding different values, and (3) validity, precluding ``unreasonable decisions. But, what is a reasonable decision? Strong validity, a classical property, stipulates that, if all correct processes propose the same value, only that value can be decided. Weak validity, another established property, stipulates that, if all processes are correct and they propose the same value, that value must be decided. The space of possible validity properties is vast. However, their impact on consensus remains unclear. This paper addresses the question of which validity properties allow Byzantine consensus to be solvable with partial synchrony, and at what cost. First, we determine necessary and sufficient conditions for a validity property to make the consensus problem solvable; we say that such validity properties are solvable. Notably, we prove that, if n <= 3t, all solvable validity properties are trivial (there exists an always-admissible decision). Furthermore, we show that, with any non-trivial (and solvable) validity property, consensus requires Omega(t^2) messages. This extends the seminal Dolev-Reischuk bound, originally proven for strong validity, to all non-trivial validity properties. Lastly, we give a general Byzantine consensus algorithm, we call Universal, for any solvable (and non-trivial) validity property. Importantly, Universal incurs O(n^2) message complexity. Thus, together with our lower bound, Universal implies a fundamental result in partial synchrony: with t in Omega(n), the message complexity of all (non-trivial) consensus variants is Theta(n^2).

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 2013822 (Why is no real title available?)
• scientific article; zbMATH DE number 2013840 (Why is no real title available?)
• scientific article; zbMATH DE number 1848309 (Why is no real title available?)
• A combinatorial characterization of the distributed 1-solvable tasks
• A hierarchy of conditions for consensus solvability
• A necessary condition for Byzantine \(k\)-set agreement
• An algorithmic approach to the asynchronous computability theorem
• Asymptotically Optimal Validated Asynchronous Byzantine Agreement
• Asynchronous secure computations with optimal resilience (extended abstract)
• Bounds on information exchange for Byzantine agreement
• Byzantine Fault Detectors for Solving Consensus
• Byzantine agreement with median validity
• Byzantine vector consensus in complete graphs
• Communication Complexity of Byzantine Agreement, Revisited
• Condition-based consensus in synchronous systems
• Conditions on input vectors for consensus solvability in asynchronous distributed systems
• Distributed computability in Byzantine asynchronous systems
• Dumbo-MVBA: Optimal Multi-Valued Validated Asynchronous Byzantine Agreement, Revisited
• Efficient Byzantine Fault-Tolerance
• Efficient player-optimal protocols for strong and differential consensus
• From binary consensus to multivalued consensus in asynchronous message-passing systems
• HotStuff
• Impossibility of distributed consensus with one faulty process
• Initial failures in distributed computations
• Introduction to Reliable and Secure Distributed Programming
• Multidimensional approximate agreement in Byzantine asynchronous systems
• Optimal algorithms for synchronous Byzantine \(k\)-set agreement
• Practical threshold signatures
• Principles of Distributed Systems
• Randomized protocols for asynchronous consensus
• Reaching Agreement in the Presence of Faults
• Resilient-optimal interactive consistency in constant time
• Synchronous Byzantine agreement with nearly a cubic number of communication bits, synchronous Byzantine agreement with nearly a cubic number of communication bits
• The Byzantine Generals Problem
• The Byzantine generals problem
• The asynchronous computability theorem for t-resilient tasks
• The topological structure of asynchronous computability
• Using conditions to expedite consensus in synchronous distributed systems
• \textsc{Rambo}: a robust, reconfigurable atomic memory service for dynamic networks

This page was built for publication: On the Validity of Consensus

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