Brief Announcement: Revisiting Lower Bounds for Two-Step Consensus

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 f 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}.