EPaxos (7.1) felt genuinely novel — leaderless proposing, dependency-graph ordering. Worth knowing, though: Lamport himself had already explored closely related ideas years earlier, in two papers less famous than "Paxos Made Simple" but directly foreshadowing much of what this phase covers. Generalized Paxos (2004) relaxes the total-order requirement for commutative operations — the direct conceptual ancestor of EPaxos's dependency-based ordering. Fast Paxos (2006) shows how to skip Phase 1's leader-routing entirely for the common case, at the cost of a possible collision that needs explicit recovery — a direct ancestor of EPaxos's fast-path/slow-path split. This article covers both, and closes the loop on exactly how much of "modern" Paxos research traces back to ideas Lamport had already sketched.
Generalized Paxos: commutativity instead of total order
Recall article 4.3's atomic broadcast framing: total order requires every pair of operations to have an agreed relative order, even ones that don't logically interact. Generalized Paxos's insight, stated years before EPaxos built a full leaderless system around a closely related idea: if two operations commute — applying them in either order produces the same result — there's no need to agree on their relative order at all. Formally, Generalized Paxos replaces the single sequential command sequence with a partial order: a structure where only non-commuting (conflicting) operations need an agreed relative order, exactly the same underlying idea article 7.1 built EPaxos's dependency graph around.
Fast Paxos: skipping the leader for the common case
Fast Paxos targets a different inefficiency: in ordinary Multi-Paxos, even after Phase 1 is amortized (article 5.3), every client write still has to route through the leader specifically before being replicated — a latency cost for clients not physically close to the leader, precisely the cost article 7.1 opened by naming. Fast Paxos's fix: let any acceptor accept a value directly from a proposer that isn't the leader, in a designated fast round, cutting out the extra leader hop for the common case.
The catch, and it's a real one: if two different clients' proposals reach different subsets of acceptors in the same fast round (a collision — no single value gets the needed supermajority), the system can't simply pick one arbitrarily, because doing so might violate safety in exactly the way article 5.2's Phase 2 rule was designed to prevent. Fast Paxos handles this with an explicit recovery step — a designated coordinator (falling back to something like ordinary Multi-Paxos's leader role) resolves the collision using the same "adopt the highest-numbered information seen" logic from article 5.2's Phase 2 rule, just triggered specifically by a detected collision rather than running on every single value.
Fig 1 — Fast Paxos's collision recovery is the direct structural ancestor of EPaxos's slow path.
The lineage, made explicit
| Paper | Year | What it relaxes | What it keeps |
|---|---|---|---|
| Multi-Paxos (5.3) | 1998/2001 | — | Fixed leader, total order, majority quorums |
| Fast Paxos | 2006 | Requires routing through the leader for every write | Total order, fixed leader as fallback/recovery coordinator |
| Generalized Paxos | 2004 (concept), formalized later | Total order (only orders non-commuting operations) | Fixed leader structure |
| Flexible Paxos (7.2) | 2016 | Phase 1/Phase 2 quorums must both be majorities | Fixed leader, total order |
| EPaxos (7.1) | 2013 | Fixed leader AND total order, simultaneously | Majority-overlap safety core (article 3.3) |
FAQ
Why isn't Fast Paxos as famous as Multi-Paxos or as widely deployed as EPaxos-inspired systems?
Partly presentation (echoing article 5.1's recurring theme about Lamport's papers), and partly because the collision-recovery mechanism adds real implementation complexity for a latency win that matters most specifically for clients far from the leader — a narrower use case than Multi-Paxos's general-purpose replicated log. Its ideas, though, demonstrably influenced later, more widely-adopted leaderless designs.
Can Generalized Paxos and Fast Paxos be combined?
Conceptually yes, and doing so gets you something quite close to EPaxos's actual design space — commutativity-based partial ordering plus leader-skipping fast rounds. This isn't a coincidence; it's a reasonable way to understand what EPaxos's contribution actually was: combining and extending two ideas Lamport had already sketched separately, into one coherent, fully leaderless system.
Does commutativity detection in Generalized Paxos have the same real-time-information problem EPaxos's conflict detection has?
Yes, structurally identical — determining whether two operations commute (or conflict) in real time, with information that might not have fully propagated yet, is the same fundamental challenge article 7.1 described for EPaxos's dependency-set computation. Generalized Paxos doesn't sidestep this; it inherits it, which is part of why EPaxos's fuller treatment of the problem (fast quorums, explicit reconciliation) became the more complete, more discussed reference point.
Takeaways
- Generalized Paxos (Lamport, 2004) relaxes total order to a partial order over commuting operations — the direct conceptual ancestor of EPaxos's dependency-graph approach, while retaining Multi-Paxos's fixed-leader structure.
- Fast Paxos (Lamport, 2006) lets proposers skip the leader hop for a fast round, with an explicit collision recovery mechanism reusing article 5.2's Phase 2 adoption rule when two proposals collide — the direct ancestor of EPaxos's fast-path/slow-path split.
- Every modern Paxos variant covered so far relaxes exactly one (or more) of Multi-Paxos's three bundled convenience assumptions — fixed leader, total order, symmetric majority quorums — while leaving the underlying majority-overlap safety core (article 3.3) completely unchanged.
- "Which assumption does this paper relax, and what does it cost" is the single most useful lens for reading the remaining Phase 7 papers efficiently.
References & further reading
- Lamport — Fast Paxos (2006) — the primary Fast Paxos reference.
- Lamport — Generalized Consensus and Paxos (2004) — the primary Generalized Paxos reference.
- cvam.sight — Consensus 7.1: EPaxos, Leaderless Consensus — the system that combines and extends both ideas covered here.