EPaxos (Egalitarian Paxos)

A leaderless Paxos variant where any replica can commit a command in one round-trip by agreeing with peers on an interference-based ordering, avoiding the latency and failover cost of a fixed leader.

Practical example

In a five-region key-value store, a client in Europe proposes a write; if a fast quorum of three replicas agrees on the same dependency set with no conflicting concurrent writes, the command commits in one WAN round-trip without waiting on a leader in another continent.

Traditional Multi-Paxos and Raft funnel every write through a single leader, which minimizes latency for clients co-located with that leader but imposes a wide-area round-trip penalty on every other client, and creates a failover stall during leader election. EPaxos removes this by allowing any replica to act as the command leader for a given proposal (“commander” role), dependent solely on whether it can gather a fast quorum that agrees on the command’s dependency set — the other commands it conflicts with, as determined by an application-supplied interferes() predicate (commonly derived from key overlap in a KV store).

The core mechanism works in two possible paths per instance:

Fast Path (one round-trip): The commander sends PreAccept messages containing its proposed command and current known dependencies to a fast quorum (typically ⌈3N/4⌉ for N=5). If all replies agree on the same dependency set, the command commits immediately with no second phase.
Slow Path (two round-trips): If replies diverge — because concurrent conflicting proposals interleaved — the commander merges the reported dependencies (taking the union) and drives a standard Paxos Accept phase to converge on the final ordering before committing.

Execution is decoupled from commitment: committed instances are executed in an order derived from a dependency graph (via strongly-connected-component / topological sort at execution time), so commands with no relationship can execute out of program order and even concurrently, provided all their dependencies have already committed.

The practical trade-off is CPU and bookkeeping cost versus latency. Because there is no fixed leader, every replica must track a full N-way instance space, run conflict detection on every proposal, and periodically execute a graph analysis pass to determine safe execution order — this is asymptotically more expensive than Raft’s simple log-apply loop. Livelock is also a real operational hazard: under high contention on the same keys, dependency graphs can grow large and execution stalls waiting for slow-path resolution, which is why production adaptations (e.g., Atlas, and CockroachDB’s abandoned EPaxos prototype) impose fallback leader election or bounded conflict domains to keep tail latency predictable.

Architecturally, EPaxos is most attractive in multi-region deployments with no single natural leader locality — e.g., active-active writes across continents where you want each region’s client to commit locally in one WAN round-trip rather than always paying the latency to a leader region. It is rarely deployed as-is in production because of implementation complexity and the difficulty of bounding worst-case latency under adversarial or highly-conflicting workloads; most systems instead borrow its core insight (leaderless fast-quorum commit with conflict-based ordering) into narrower-scope designs, such as per-shard leader election combined with EPaxos-style ordering only within known-independent key ranges.