Understanding EPaxos: A Leaderless Consensus Algorithm Explained

Introduction

EPaxos (Egalitarian Paxos) is a next‑generation distributed consensus algorithm that eliminates the need for a leader. Although it has attracted industry attention, no engineering implementation or easy‑to‑understand article existed. This article explains EPaxos step by step for readers familiar with Paxos or Raft.

Basic Idea

EPaxos is leaderless: any replica can propose. It can be viewed as each replica acting as a leader in a multi‑group Paxos/Raft setup. By tracking dependencies between instances, EPaxos determines a global order across groups, achieving true leaderless operation.

Each instance runs a consensus phase to agree on its value, dependencies, and sequence number, followed by a deterministic sorting algorithm that merges per‑group instance sequences into a single global sequence.

Instance Model

Unlike Paxos, EPaxos instances are not pre‑assigned sequential IDs. Each replica has a row in a two‑dimensional space, identified as R.i where R is the replica and i is a locally increasing integer. Instances carry additional fields:

state : pre‑accepted, accepted, or committed.

deps : set of instances that must precede this one.

seq : sequence number equal to max(seq of deps) + 1.

All replicas must agree on state, deps, and seq before sorting.

Consensus Protocol

EPaxos adds a PreAccept phase to Paxos. The three phases are:

Prepare : optional; usually skipped because each replica can propose locally.

PreAccept : determines deps and seq; if a fast quorum agrees, the instance can be committed directly (fast path).

Accept : runs when fast quorum fails; synchronizes value, deps, and seq among a majority.

Commit : disseminates the final decision (value, deps, seq) to all replicas.

Sorting Algorithm

After instances are committed, EPaxos sorts them using a deterministic algorithm similar to topological sorting. It first finds strongly connected components (SCCs) with Tarjan’s algorithm, contracts each SCC into a vertex, producing a DAG, and then topologically sorts the DAG. Within an SCC, instances are ordered by their seq numbers.

Challenges include potential cycles that cause livelocks and the need for recursion‑friendly SCC detection.

Case Study

A five‑replica example demonstrates proposals A, B, and C, showing how PreAccept, Accept, and Commit interact, how deps and seq are derived, and how the final ordering A → B → C is obtained.

Discussion

Key topics include instance conflicts, fast quorum sizing, and the requirement that the proposer always belongs to the quorum because it persists its local state before broadcasting.

Pseudocode

The core EPaxos protocol can be expressed in pseudocode (illustrated in the accompanying diagram), where each replica stores commands in a two‑dimensional array and follows the PreAccept‑Accept‑Commit flow.

Conclusion

EPaxos removes leader bottlenecks, enables concurrent, out‑of‑order commits, and can improve throughput, but engineering challenges such as failure handling, dependency cycles, and persistent storage remain.

Thought Questions

Why can instance seq numbers repeat, and under what conditions?

How is the fast quorum size derived?

If a proposer crashes before completing consensus, how should other replicas handle the instance?