EPaxos

Every modern distributed database needs consensus: a way to make a cluster of servers agree on the same sequence of operations even when some servers crash or messages are lost. The classic answer is Paxos — but classic Paxos has a catch.

In Paxos, one server plays the role of leader. Every command, no matter where it originates, must pass through that leader, who assigns it a global slot number. The leader becomes a funnel: all writes queue up behind it, and if the leader is far away your latency pays the price of an extra network round-trip.

EPaxos — Egalitarian Paxos — was published by Iulian Moraru, David G. Andersen, and Michael Kaminsky at SOSP 2013. Its central insight is deceptively simple: two commands only need to be ordered relative to each other if they conflict. Commands that read and write different keys can execute in any order and produce the same result — they commute. If two commands commute, there is nothing to agree on between them, and each can be committed independently at any replica, with no single bottleneck.

Where classic Paxos imposes a total order on all commands, EPaxos builds a dependency graph: each command records which other in-flight commands it conflicts with, and replicas execute them in a topological sort of that graph. Commands that never share a conflict edge are free to race ahead.

The demo below models three EPaxos replicas. Each command targets a key (A or B). Commands on different keys commute — they can commit independently via the fast path in one round-trip. Commands on the same key conflict and must go through a slower coordination round.

<!-- {{c_demo_title}} -->
<div class="controls">
  <div class="ctrl-row">
    <label>{{lbl_cmd}}</label>
    <select id="sel-key">
      <option value="A">{{opt_key_a}}</option>
      <option value="B">{{opt_key_b}}</option>
    </select>
    <input id="inp-val" type="text" placeholder="{{ph_value}}" maxlength="6" />
    <button id="btn-send" type="button">{{btn_send}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<div class="arena" id="arena">
  <div class="replica" id="r0"><div class="rep-head">{{lbl_replica}} R1</div><ul class="log" id="log0"></ul></div>
  <div class="replica" id="r1"><div class="rep-head">{{lbl_replica}} R2</div><ul class="log" id="log1"></ul></div>
  <div class="replica" id="r2"><div class="rep-head">{{lbl_replica}} R3</div><ul class="log" id="log2"></ul></div>
</div>
<div class="dep-box">
  <div class="dep-title">{{lbl_dep_graph}}</div>
  <canvas id="dep-canvas" width="480" height="120"></canvas>
</div>
<div class="status" id="status"></div>

/* {{c_css_base}} */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; font-size: 14px; color: #222; }
.controls { margin-bottom: .7rem; }
.ctrl-row { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; }
label { font-weight: 600; white-space: nowrap; }
select, input[type=text] {
  padding: .35rem .5rem; border: 1px solid #b0bec5; border-radius: 6px;
  font: inherit; background: #fff;
}
input[type=text] { width: 80px; }
button {
  padding: .4rem .9rem; font: 600 13px system-ui; border-radius: 6px; cursor: pointer;
  border: 1px solid #1d3557; background: #1d3557; color: #fff;
}
button.ghost { background: #fff; color: #1d3557; }
/* {{c_css_arena}} */
.arena { display: flex; gap: 8px; margin-bottom: .7rem; }
.replica {
  flex: 1; border: 1px solid #cdd9e3; border-radius: 8px; padding: 6px 8px;
  min-height: 110px; background: #f8fafc;
}
.rep-head { font-weight: 700; font-size: .8rem; color: #1d3557; margin-bottom: 4px; text-align: center; }
.log { list-style: none; padding: 0; }
.log li {
  font-size: .78rem; padding: 3px 5px; margin: 2px 0; border-radius: 5px;
  border-left: 3px solid transparent;
}
.log li.fast { background: #e6f4ea; border-color: #0a7d33; color: #0a7d33; }
.log li.slow { background: #fff3e0; border-color: #c86000; color: #c86000; }
.log li.pending { background: #eef2f7; border-color: #7a8ea8; color: #4a5568; }
/* {{c_css_dep}} */
.dep-box { margin-bottom: .5rem; }
.dep-title { font-weight: 700; font-size: .8rem; color: #1d3557; margin-bottom: 3px; }
canvas { border: 1px solid #cdd9e3; border-radius: 6px; background: #f8fafc; display: block; width: 100%; max-width: 480px; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; color: #555; }

// Code not found

Notice the asymmetry. Commuting commands each get their own fast-path commit with no coordination between replicas. Conflicting commands trigger a dependency-tracking round: the executing replica must collect acknowledgements that include dependency information, and all replicas must reach the same execution order. The dependency graph grows only along conflict edges.

EPaxos achieves something remarkable, but it does so by trading one cost for another.

The fast path (commuting commands). If a command $c$ arrives at replica $R$ and no other in-flight command conflicts with it, $R$ sends a single PreAccept message to a fast-path quorum of $\lfloor F/2 \rfloor + 1$ replicas (where $F$ is the failure tolerance). If all quorum members agree on the same dependency set, $c$ is committed in one round-trip — the theoretical minimum for any fault-tolerant protocol under the FLP impossibility result.

The slow path (conflicting commands). When two replicas disagree on the dependency set — because concurrent conflicting commands arrived at different replicas simultaneously — a second round is needed. The leader runs Accept to impose a consistent dependency set, adding a full round-trip. Total: two round-trips, same as classic Paxos in the worst case.

The dependency graph and execution. After commit, replicas must execute commands in a topological order of the dependency graph. Finding that order requires detecting strongly connected components (SCCs) in the graph, using an algorithm like Tarjan's or Kosaraju's in $O(V + E)$ time. Commands in the same SCC must be executed in a deterministic agreed-upon order (e.g. by command ID).

The commutativity tax. All of this only works if replicas agree on what "conflicts" means. Each application must supply a conflict relation: two commands conflict if and only if their execution order can change the result. For key-value stores this is easy (writes to the same key conflict). For general state machines it can be subtle — a wrong conflict relation silently violates correctness. EPaxos hands this responsibility to the application, making it more powerful but also more dangerous than single-leader Paxos.

EPaxos's insight — only conflicting commands need coordination — has rippled through the distributed systems world:

• Geo-distributed databases: when replicas sit in different continents, a leader in one data center imposes a full cross-ocean round-trip on every write from elsewhere. EPaxos lets each region commit local non-conflicting writes at local latency.
• Leaderless replication: systems like Apache Cassandra use leaderless replication for availability, but without a formal consensus protocol. EPaxos provides the correctness guarantee that informal quorum reads/writes lack.
• CockroachDB and TiDB: both databases base their replication layers on Raft (a single-leader protocol similar to Paxos). Research prototypes have explored EPaxos-style dependency tracking to reduce cross-region latency for commuting transactions.
• Calvindb and Calvin: a different angle — pre-ordering transactions before execution so everything commutes — shows the same insight from the other direction.
• Formal verification: the TLA+ specification of EPaxos (Whittaker et al., 2021) revealed subtle correctness bugs in the original paper's slow path, illustrating how tricky leaderless protocols are to get right. This connects to the broader challenge of program equivalence and formal verification in distributed systems.

EPaxos is not a drop-in replacement for Raft or classic Paxos. Its implementation complexity is substantially higher, and its benefits only materialize when the workload has a significant fraction of commuting commands. But when those conditions hold, it offers latency that no single-leader protocol can match.

EPaxos makes a beautiful bet: most commands in a well-designed workload commute most of the time. When that bet pays off, every replica can lead for its own commands, cross-region latency disappears, and the dependency graph stays sparse and cheap to execute.

The lesson generalises far beyond consensus protocols. Wherever you find a coordination bottleneck, ask whether the operations you are serialising truly need a total order — or whether a dependency graph would do. If two things genuinely do not interfere with each other, forcing them to wait in a queue is not correctness, it is just unnecessary cost.

That question — what must be ordered, and what is free to race? — sits at the heart of P vs NP, parallel algorithms, and every distributed system ever built. EPaxos just makes it unusually vivid.