Revisiting Lower Bounds for Two-Step Consensus
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915733336752128 |
|---|---|
| author | Ryabinin, Fedor Gotsman, Alexey Sutra, Pierre |
| author_facet | Ryabinin, Fedor Gotsman, Alexey Sutra, Pierre |
| contents | A seminal result by Lamport shows that at least $\max\{2e+f+1,2f+1\}$ processes are required to implement partially synchronous consensus that tolerates $f$ process failures and can furthermore decide in two message delays under $e$ failures. This lower bound is matched by the classical Fast Paxos protocol. However, more recent practical protocols, such as Egalitarian Paxos, provide two-step decisions with fewer processes, seemingly contradicting the lower bound. We show that this discrepancy arises because the classical bound requires two-step decisions under a wide range of scenarios, not all of which are relevant in practice. We propose a more pragmatic condition for which we establish tight bounds on the number of processes required. Interestingly, these bounds depend on whether consensus is implemented as an atomic object or a decision task. For consensus as an object, $\max\{2e+f-1,2f+1\}$ processes are necessary and sufficient for two-step decisions, while for a task the tight bound is $\max\{2e+f, 2f+1\}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_03627 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Revisiting Lower Bounds for Two-Step Consensus Ryabinin, Fedor Gotsman, Alexey Sutra, Pierre Distributed, Parallel, and Cluster Computing A seminal result by Lamport shows that at least $\max\{2e+f+1,2f+1\}$ processes are required to implement partially synchronous consensus that tolerates $f$ process failures and can furthermore decide in two message delays under $e$ failures. This lower bound is matched by the classical Fast Paxos protocol. However, more recent practical protocols, such as Egalitarian Paxos, provide two-step decisions with fewer processes, seemingly contradicting the lower bound. We show that this discrepancy arises because the classical bound requires two-step decisions under a wide range of scenarios, not all of which are relevant in practice. We propose a more pragmatic condition for which we establish tight bounds on the number of processes required. Interestingly, these bounds depend on whether consensus is implemented as an atomic object or a decision task. For consensus as an object, $\max\{2e+f-1,2f+1\}$ processes are necessary and sufficient for two-step decisions, while for a task the tight bound is $\max\{2e+f, 2f+1\}$. |
| title | Revisiting Lower Bounds for Two-Step Consensus |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2505.03627 |