Understanding EPaxos: The Leaderless Consensus Algorithm Explained

Introduction

EPaxos (Egalitarian Paxos) is a next‑generation distributed consistency algorithm that has attracted great interest in industry. Unlike traditional Paxos or Multi‑Paxos, EPaxos is leaderless and aims to achieve high availability and throughput while handling conflicts directly.

Paxos Background

Paxos is the seminal consensus algorithm that tolerates F failures with 2F+1 replicas. It reaches a decision through two phases: Prepare and Accept. The Prepare phase lets replicas compete for proposal rights, and the Accept phase lets the winning replica propose a value. This two‑phase process often requires multiple network round‑trips, leading to inefficiency and possible livelocks.

Multi‑Paxos introduces a leader to eliminate the Prepare phase, reducing the decision to a single round‑trip. While this improves efficiency, the leader becomes a performance and availability bottleneck.

EPaxos was proposed to combine the strengths of Basic Paxos (high availability) and Multi‑Paxos (high efficiency) without introducing a leader.

EPaxos Solution

EPaxos is a leaderless algorithm: any replica can initiate a proposal, and a decision typically requires one or two network round‑trips. Because there is no leader election overhead, the system remains highly available even if some replicas fail, and load is balanced across all replicas.

Unlike Paxos, EPaxos does not assign a global sequence number to instances in advance. Instead, each replica maintains its own two‑dimensional instance space (a row in a matrix). Proposals are made concurrently in these spaces, and EPaxos also ensures a consistent ordering between different instances.

Each instance carries a set of dependencies (deps) that represent the relative order with other instances (e.g., B depends on A, meaning A must precede B). The dependency sets are agreed upon together with the instance values, allowing all replicas to reconstruct a consistent dependency graph.

After instances reach consensus, replicas perform a deterministic reordering. This process is similar to a topological sort, but because dependencies may form cycles, EPaxos first identifies strongly connected components using Tarjan's algorithm, contracts each component into a node, and then topologically sorts the resulting DAG. Within a component, instances are ordered by a sequence number (seq), although in practice seq may duplicate, which is a known issue.

Implementation challenges include the risk of stack overflow in recursive Tarjan implementations, handling cycles that can cause livelocks, and ensuring the deterministic ordering works correctly under high concurrency.

Summary

EPaxos introduces dynamic ordering and a leaderless design, achieving both efficiency and availability while inheriting advantages of Basic Paxos and Multi‑Paxos. It remains a promising algorithm for future distributed systems.

Thought Questions

Since EPaxos instances are not pre‑numbered, how are they identified?

How does EPaxos determine an instance's dependency set, and how is this set agreed upon across replicas?

Why can dependencies between instances form cycles, and under what conditions does a cyclic dependency arise?