There Is More Consensus in Egalitarian Parliaments
📜 Abstract
This paper describes the design and implementation of Egalitarian Paxos (EPaxos), a new distributed consensus algorithm based on Paxos. EPaxos achieves three goals: (1) optimal commit latency in the wide-area when tolerating one and two failures, under realistic conditions; (2) uniform load balancing across all replicas (thus achieving high throughput); and (3) graceful performance degradation when replicas are slow or crash. Egalitarian Paxos is to our knowledge the first protocol to achieve the previously stated goals efficiently—that is, requiring only a simple majority of replicas to be non-faulty, using a number of messages linear in the number of replicas to choose a command, and committing commands after just one communication round (one round trip) in the common case or after at most two rounds in any case. We prove Egalitarian Paxos’s properties theoretically and demonstrate its advantages empirically through an implementation running on Amazon EC2.
✨ Summary
Contributions
The paper introduces Egalitarian Paxos (EPaxos), a leaderless state-machine-replication protocol designed for geo-distributed systems and high-throughput clusters. Unlike Multi-Paxos, EPaxos allows any replica to act as the command leader, distributes request-processing load across replicas, and avoids a leader-election interruption when a minority of replicas fails. Commands are ordered dynamically using dependency information rather than through a globally preassigned sequence of slots.
EPaxos uses a fast path when replicas independently derive identical dependency and sequence-number metadata. In that case, a command can be committed after one communication round with a fast quorum. If concurrent commands interfere and replicas derive different metadata, the protocol uses a second Paxos-style acceptance round. The execution algorithm constructs dependency graphs and orders strongly connected components so that interfering commands execute consistently and client-serialized operations preserve linearizability. The optimized protocol uses a fast-path quorum of (F + \lceil(F+1)/2\rceil) replicas and tolerates up to (F) crash failures with (2F+1) replicas.
The evaluation compares EPaxos with Multi-Paxos, Mencius, and Generalized Paxos using Amazon EC2 experiments. EPaxos provides low wide-area commit latency, higher throughput than leader-bottlenecked Multi-Paxos, better tolerance of slow replicas, and continued commit availability after a minority replica failure. Its principal limitations are the need to identify command interference, increased metadata and execution complexity, and possible execution delays caused by dependency chains, especially under highly conflicting workloads. The paper also discusses persistent logging, recovery, reconfiguration, read leases, dependency-list reduction, and batching. (cs.cmu.edu)
Influence
The work directly motivated later research that re-evaluated EPaxos’s performance under broader conflict workloads. EPaxos Revisited reproduced the original result that EPaxos can achieve optimal median WAN commit latency, but reported substantially worse tail latency under some workloads and identified unbounded dependency growth as a source of very high latency or livelock. It proposed bounded dependency growth and synchronized-clock techniques that reduced conflicts by at least 50% and reduced mean latency by up to 7.5% in its experiments. (usenix.org)
The original authors also released an EPaxos implementation, and subsequent research reused or forked that code for experimental evaluation. (github.com) The search found clear evidence of continued academic use and follow-up evaluation, but no sufficiently authoritative evidence establishing that EPaxos itself became a widely deployed industry consensus protocol.