Removing the single leader
Multi Paxos and Raft funnel every command through one leader, which becomes a bottleneck and a single point of latency. Egalitarian Paxos, or EPaxos, is leaderless: any replica can propose any command, and the protocol orders commands only when they genuinely conflict.
Dependencies instead of slots
Instead of a single numbered log, EPaxos builds a graph. When a replica proposes a command it computes the set of already seen commands that interfere with it, such as writes to the same key, and records them as dependencies.
- Non conflicting commands commit in one round trip with a fast path quorum.
- Conflicting commands take an extra round to agree on their dependencies.
- Execution follows the dependency graph, so independent commands run in parallel.
Benefits and cost
Because there is no fixed leader, load spreads across replicas and a client can use the nearest one, cutting wide area latency. The price is complexity: replicas must track and agree on dependency sets and execute by walking, and sometimes untangling cycles in, the command graph.
Key idea
Egalitarian Paxos is leaderless and orders only conflicting commands via dependency graphs, spreading load and committing independent commands in a single round trip.