Introduction

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.

Try It: Commute vs Conflict

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.

<!-- EPaxos commute-vs-conflict demo -->
<div class="controls">
  <div class="ctrl-row">
    <label>Command:</label>
    <select id="sel-key">
      <option value="A">Key A</option>
      <option value="B">Key B</option>
    </select>
    <input id="inp-val" type="text" placeholder="value" maxlength="6" />
    <button id="btn-send" type="button">Send command</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
</div>
<div class="arena" id="arena">
  <div class="replica" id="r0"><div class="rep-head">Replica R1</div><ul class="log" id="log0"></ul></div>
  <div class="replica" id="r1"><div class="rep-head">Replica R2</div><ul class="log" id="log1"></ul></div>
  <div class="replica" id="r2"><div class="rep-head">Replica R3</div><ul class="log" id="log2"></ul></div>
</div>
<div class="dep-box">
  <div class="dep-title">Dependency graph</div>
  <canvas id="dep-canvas" width="480" height="120"></canvas>
</div>
<div class="status" id="status"></div>

/* base styles: controls, buttons, inputs */
* { 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; }
/* replica columns layout */
.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; }
/* dependency graph canvas */
.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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// EPaxos (Egalitarian Paxos) demo — leaderless consensus via dependency graph.
// Fast path: command has no conflicts with in-flight commands → 1 round-trip.
// Slow path: conflict detected → leader must run Accept phase → 2 round-trips.

const REPLICAS = 3;
let cmdSeq = 0;       // global command sequence number
let commands = [];    // committed commands in order

// Two commands conflict if they target the same key (non-commutative).
function conflicts(a, b) {
  return a.key === b.key;
}

// Compute the dependency set of a new command against all prior committed commands.
function computeDeps(newCmd) {
  return commands.filter(c => conflicts(c, newCmd)).map(c => c.id);
}

// Handle the Send button: assign an ID, compute deps, classify fast/slow.
function sendCommand() {
  const key = document.getElementById('sel-key').value;
  const val = document.getElementById('inp-val').value.trim() || '?';
  const id = ++cmdSeq;
  const leader = (id - 1) % REPLICAS; // round-robin leader: each command is proposed by a different replica
  const deps = computeDeps({ key });
  const isFast = deps.length === 0;    // no deps = no conflicts = fast path

  const cmd = { id, key, val, deps, isFast, leader };
  commands.push(cmd);

  appendToReplicas(cmd);
  drawDependencyGraph();
  showStatus(cmd, isFast);
}

function appendToReplicas(cmd) {
  for (let i = 0; i < REPLICAS; i++) {
    const li = document.createElement('li');
    const tag = cmd.isFast ? 'fast path' : 'slow path';
    const depStr = cmd.deps.length ? ' ← c' + cmd.deps.join(',c') : '';
    li.textContent = 'c' + cmd.id + ':' + cmd.key + '=' + cmd.val + depStr + ' [' + tag + ']';
    li.className = cmd.isFast ? 'fast' : 'slow';
    document.getElementById('log' + i).appendChild(li);
  }
}

// Draw the dependency graph on the canvas.
function drawDependencyGraph() {
  const canvas = document.getElementById('dep-canvas');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  const n = commands.length;
  if (n === 0) return;

  const R = 16, PAD = 28;
  // lay out nodes left-to-right by arrival order
  const step = Math.min(54, (W - 2 * PAD) / Math.max(n - 1, 1));
  const positions = commands.map((_, i) => ({ x: PAD + i * step, y: H / 2 }));

  // draw dependency edges
  ctx.strokeStyle = '#c86000';
  ctx.lineWidth = 1.5;
  commands.forEach(cmd => {
    cmd.deps.forEach(depId => {
      const from = positions[depId - 1];
      const to   = positions[cmd.id - 1];
      if (!from || !to) return;
      ctx.beginPath();
      ctx.moveTo(from.x, from.y);
      ctx.lineTo(to.x, to.y);
      ctx.stroke();
      // arrowhead pointing to the dependent command
      const angle = Math.atan2(to.y - from.y, to.x - from.x);
      const ax = to.x - R * Math.cos(angle);
      const ay = to.y - R * Math.sin(angle);
      ctx.beginPath();
      ctx.moveTo(ax, ay);
      ctx.lineTo(ax - 7 * Math.cos(angle - 0.4), ay - 7 * Math.sin(angle - 0.4));
      ctx.lineTo(ax - 7 * Math.cos(angle + 0.4), ay - 7 * Math.sin(angle + 0.4));
      ctx.closePath();
      ctx.fillStyle = '#c86000';
      ctx.fill();
    });
  });

  // draw command nodes
  commands.forEach((cmd, i) => {
    const { x, y } = positions[i];
    ctx.beginPath();
    ctx.arc(x, y, R, 0, 2 * Math.PI);
    ctx.fillStyle = cmd.isFast ? '#0a7d33' : '#c86000';
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 1.5;
    ctx.stroke();
    ctx.fillStyle = '#fff';
    ctx.font = 'bold 9px system-ui';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText('c' + cmd.id + ':' + cmd.key, x, y);
  });
}

function showStatus(cmd, isFast) {
  const el = document.getElementById('status');
  if (isFast) {
    el.textContent = fmt('cc%id% committed via fast path — no conflicts, 1 round-trip.', { id: cmd.id });
    el.style.color = '#0a7d33';
  } else {
    const depList = 'c' + cmd.deps.join(', c');
    el.textContent = fmt('cc%id% ← {%depList%} takes slow path — conflict detected, 2 round-trips needed.', { id: cmd.id, depList: depList });
    el.style.color = '#c86000';
  }
}

function reset() {
  cmdSeq = 0;
  commands = [];
  for (let i = 0; i < REPLICAS; i++) {
    document.getElementById('log' + i).innerHTML = '';
  }
  const canvas = document.getElementById('dep-canvas');
  canvas.getContext('2d').clearRect(0, 0, canvas.width, canvas.height);
  document.getElementById('status').textContent = '';
  document.getElementById('inp-val').value = '';
}

document.getElementById('btn-send').addEventListener('click', sendCommand);
document.getElementById('btn-reset').addEventListener('click', reset);
Result
Console

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.

The Real Complexity

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

The fast path (commuting commands). If a command cc arrives at replica RR and no other in-flight command conflicts with it, RR sends a single PreAccept message to a fast-path quorum of ⌊F/2⌋+1\lfloor F/2 \rfloor + 1 replicas (where FF is the failure tolerance). If all quorum members agree on the same dependency set, cc 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)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/epaxos/Content licensed under CC BY-NC 4.0.