Phase 5's entire classical lineage (Paxos, VR, Raft, Zab) shares one structural assumption this phase starts questioning: a single stable leader handles every write. That leader is both a throughput ceiling (every write funnels through one node's CPU and bandwidth, the exact bottleneck article 6.5 named for BFT protocols) and a latency tax for clients far from it (a client near Singapore writing through a leader in Virginia pays the full round-trip, every time, regardless of how close other replicas might be). Moraru, Andersen, and Kaminsky's 2013 EPaxos (Egalitarian Paxos) asks: what if any replica could commit a command directly, in the common case with a single round-trip to a nearby quorum, with no leader at all? The answer requires replacing "one global order" with something subtler — a dependency graph — and this article covers exactly how, and exactly what it costs.
Why remove the leader at all
Revisit the two costs a fixed leader imposes, now precisely, building on article 5.3's Multi-Paxos analysis: throughput — every single write must pass through one node, capping total system throughput at that one node's capacity no matter how many replicas exist (directly parallel to article 6.5's leader-bandwidth bottleneck, just for the crash-fault setting rather than Byzantine); and latency — a client's write latency is dominated by its round-trip to the leader specifically, which for geographically distributed deployments (Phase 9's subject) can be much worse than the round-trip to the client's nearest replica. EPaxos's leaderless design directly targets both: any replica can act as the "command leader" for any individual command, letting a client always talk to its nearest replica, and (in the common, no-conflict case) commit that command with a single round-trip to a nearby quorum, no different from Multi-Paxos's fast path (article 5.3) — just without requiring that fast path to always route through the same one node.
The catch: what happens without one global order
Here's the problem this convenience creates, and it's the whole reason EPaxos needs genuinely new machinery, not just a relabeling of Multi-Paxos's roles. Every algorithm since Phase 3 has relied on a single, globally agreed order of operations (article 3.2's log index, article 4.3's total-order-broadcast property) — and that single order is precisely what a fixed leader was providing for free, just by being the one party deciding what goes where in its own sequential log. Remove the fixed leader, and different replicas concurrently committing different commands (each acting as its own command leader) no longer have an obvious shared way to agree on a total order across commands that never went through the same coordinating party.
Dependency graphs instead of a log
When a replica proposes a command as its command leader, it attaches a dependency set — the set of other, potentially-conflicting commands it knows about that must be ordered before it. It sends this proposal to a fast quorum (a specific, slightly larger quorum than Phase 5's simple majority — more below); each replica in that quorum checks its own local knowledge of recent commands and, if it knows of any additional conflicting commands the proposer's dependency set missed, adds them to the reply. If every replica in the fast quorum agrees on the exact same dependency set (no additions needed), the command commits immediately, in a single round-trip — the fast path, structurally identical in cost to Multi-Paxos's single-round-trip append (article 5.3), just without a fixed leader deciding the order globally.
If replies disagree (different replicas knew about different conflicting commands, because information about recent activity hasn't fully propagated yet — article 1.1's "Lie #1" in concrete form), the command leader takes the union of all reported dependencies and runs a second round (the slow path — structurally similar to a full Paxos Phase 1/2, article 5.2) to get that expanded dependency set agreed upon. Either way, once a command's dependencies are settled, replicas execute commands by traversing the resulting dependency graph — using a deterministic tie-breaking rule (an ordering criterion applied consistently by every replica, echoing article 5.2's proposal-number tie-breaking pattern) to linearize any commands that turn out to be mutually dependent, so every replica executes conflicting commands in the identical relative order even though no single global sequence number was ever agreed for the whole log.
Fig 1 — Only genuinely conflicting commands need agreed ordering; disjoint commands commit and execute fully independently.
Fast quorums: a genuine trade-off, not a free upgrade
The single-round-trip fast path requires a larger quorum than a simple crash-fault majority — specifically, for N replicas tolerating f failures, EPaxos's fast quorum needs ⌊N/2⌋ + ⌊(f+1)/2⌋ replicas (larger than the plain majority ⌊N/2⌋+1 that Phase 5's algorithms used) to guarantee that any two fast-path attempts still see enough overlap to detect conflicts reliably. This is EPaxos's central, honest trade-off: leaderless operation and per-replica locality gains come at the cost of a larger quorum requirement for the fast path, and — the part that's easy to underestimate reading only the happy-path description — genuinely more complex conflict-tracking bookkeeping (every replica must track recent command history to compute accurate dependency sets) compared to Multi-Paxos's comparatively simple sequential log.
| Property | Multi-Paxos (5.3) / Raft (5.5-5.6) | EPaxos |
|---|---|---|
| Who can propose | Only the current leader | Any replica, per command |
| Ordering mechanism | Single global log (total order) | Dependency graph (partial order, only conflicts ordered) |
| Fast-path quorum size | Simple majority | Larger — ⌊N/2⌋ + ⌊(f+1)/2⌋ |
| Client latency | Round-trip to leader, wherever it is | Round-trip to nearest quorum — better for geo-distributed clients |
| Bookkeeping complexity | Simple sequential log | Per-command conflict detection, dependency tracking |
FAQ
Does EPaxos still need the same crash-fault node counts as Phase 5's algorithms?
Yes — EPaxos operates under the same crash-fault (not Byzantine) model as Phase 5, with the standard 2f+1 total node count for tolerating f crash failures. The larger fast quorum size discussed above is a different concept from the total cluster size — it's how many replicas must respond on the fast path, not how many total nodes are needed to survive failures.
How does a replica know which commands conflict without a central coordinator tracking everything?
Each replica maintains its own local record of recently proposed/committed commands and applies an application-defined conflict predicate (for a key-value store, typically "do these commands touch overlapping keys") to determine dependencies — this is inherently approximate in real time (a replica might not yet know about a very recent command elsewhere), which is exactly why the fast-quorum reply step exists: to catch and reconcile any gaps before commit.
Is EPaxos used in production systems today?
EPaxos itself is more prominent as a research reference point than a widely-deployed off-the-shelf system, but its core ideas (leaderless proposing, dependency-based ordering) directly influenced later work, including some of the later articles in this phase (Atlas, Caesar) that refine and address specific EPaxos limitations discovered in practice and follow-up research.
Does leaderless mean there's no election mechanism at all?
Not entirely — EPaxos still needs a recovery mechanism for when a command leader fails mid-proposal (a replica must be able to safely take over and complete or abort that specific command), which reuses much of the same majority-overlap-based safety reasoning from article 3.3, just scoped to individual commands rather than a single persistent leader role covering the whole log.
Takeaways
- Opens Phase 7: the modern Paxos family relaxes assumptions Phase 5's classical algorithms all shared — starting here with the fixed leader assumption.
- A fixed leader is both a throughput ceiling and a latency tax for distant clients — EPaxos targets both by letting any replica propose commands directly.
- Without a fixed leader, there's no free global order — EPaxos's key structural move is ordering only genuinely conflicting commands via a per-command dependency graph, not a total-order log.
- The fast path commits in one round-trip when a fast quorum agrees on dependencies; the slow path (a second round) resolves disagreements — structurally similar to Multi-Paxos's fast/full-Paxos distinction, just per-command rather than per-leader-term.
- The trade-off is real and explicit: a larger fast-quorum size than plain majority, and genuinely more complex per-replica conflict-tracking bookkeeping — leaderless consensus is not a strictly-better free upgrade over Phase 5's algorithms.
References & further reading
- Moraru, Andersen & Kaminsky — There Is More Consensus in Egalitarian Parliaments (SOSP 2013) — the primary EPaxos reference.
- cvam.sight — Consensus 5.3: Multi-Paxos — the fixed-leader fast path this article contrasts EPaxos against.
- cvam.sight — Consensus 6.5: Narwhal and Bullshark — the parallel leader-bandwidth-bottleneck motivation in the Byzantine setting.