On the Validity of Consensus

DOI10.1145/3583668.3594567arXiv2301.04920OpenAlexW4380873997MaRDI QIDQ6202272FDOQ6202272

Author name not available (Why is that?), Author name not available (Why is that?), Seth Gilbert, Rachid Guerraoui, Author name not available (Why is that?)

Publication date: 26 March 2024

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

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).

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)

Cites Work

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

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)