Optimal Good-Case Latency for Sleepy Consensus
Authors:
- Yuval EfronYEYuval Efron
- Joachim NeuJNJoachim Neu
- Ling RenLRLing Ren
- Ertem Nusret TasETErtem Nusret Tas
Preprint
Abstract
In the context of Byzantine consensus problems such as Byzantine broadcast (BB) and Byzantine agreement (BA), the good-case setting aims to study the minimal possible latency of a BB or BA protocol under certain favorable conditions, namely the designated leader being correct (for BB), or all parties having the same input value (for BA). We provide a full characterization of the feasibility and impossibility of good-case latency, for both BA and BB, in the synchronous sleepy model. Surprisingly to us, we find irrational resilience thresholds emerging: 2-round good-case BB is possible if and only if at all times, at least $\frac{1}{\varphi} \approx 0.618$ fraction of the active parties are correct, where $\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$ is the golden ratio; 1-round good-case BA is possible if and only if at least $\frac{1}{\sqrt{2}} \approx 0.707$ fraction of the active parties are correct.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Expected Constant Round Byzantine Broadcast under Dishonest MajorityJournal of the ACM, 2025
- The Bitcoin Backbone Protocol: Analysis and ApplicationsJournal of the ACM, 2024
- All Byzantine Agreement Problems Are Expensive2024
- Towards Practical Sleepy BFT2023
- Constant Latency in Sleepy Consensus2022
- Ebb-and-Flow Protocols: A Resolution of the Availability-Finality Dilemma2021
- Byzantine Agreement with Unknown Participants and Failures2021
- Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web servicesACM SIGACT News, 2002
- The Byzantine Generals ProblemACM Transactions on Programming Languages and Systems, 1982