Leaderless Ordering: Dependency Graphs Instead of a Single Log

Every protocol so far has had one node deciding the order: a leader appends, followers replicate, the log is a sequence. The sequence is a convenience. What consensus actually requires is that the outcome be the same at every replica, and a total order over all operations is one way to guarantee that, but it is stronger than necessary when most operations do not interact. Two writes to different keys can execute in either order and produce the same state. A protocol that exploits this can let any replica coordinate any command, removing the leader from the critical path and with it the election, the failover pause, and the single hot node.

The log is a stronger requirement than consensus needs

A replicated state machine needs a deterministic function from a set of operations to a final state. A total order supplies that: apply the operations in order, and every replica reaches the same state. The total order also supplies more than is needed, because it fixes the order of operations that commute. If set(x, 1) and set(y, 2) are applied in either order, the result is the same; the protocol spent coordination on a distinction that does not affect the outcome.

Leaderless protocols make this explicit. Each command carries a sequence number chosen by its coordinating replica and a set of dependencies: the commands that must be executed before it. Two commands with no dependency between them may be executed in any order, or concurrently, and the replicas will still converge. Two commands that conflict must be ordered, and the dependency sets are what encode that order.

The result is a partial order rather than a total one, and the replicas must agree on it. Agreement on a partial order is still agreement, and it still requires quorums: a command’s dependencies are only authoritative if a quorum has seen them.

How a command gets its dependencies

A replica that wants to execute a command assigns it the next sequence number in its own per-replica counter, then computes the dependency set. The set is built from the commands that other replicas have recently coordinated and that conflict with this one.

The mechanism is a shared structure of recent commands, indexed by sequence number. A replica preparing a command reads the entries at the sequence numbers it is about to use and records, for each conflicting command it finds there, that the conflicting command must precede it. It then writes its own command into the structure at its sequence number, along with its dependency list.

The conflicting check is application-defined. For a key-value store, two commands conflict if they touch the same key, or if one is a read and the other a write to the same key. Commands that touch disjoint keys have empty dependency sets relative to each other and can proceed independently. This is why the approach suits workloads with many independent keys and suffers on workloads where every operation touches one hot key: the dependency sets grow, the partial order approaches a total order, and the protocol’s advantage disappears.

Sequence numbers matter for the conflict resolution. When two concurrent commands do conflict, they each record the other as a dependency, and the pair must be ordered. The rule is by sequence number: the command with the lower sequence number goes first, and ties are broken by the coordinating replica’s identifier. Both commands have recorded the dependency, so both replicas that hold them can compute the same order without further communication. The dependency sets are symmetric precisely because both sides read the shared structure before writing to it, and the shared structure is replicated, so a later reader sees both.

The quorum structure

Each command is replicated to a quorum, and the quorum is the same majority as in a leader-based protocol: floor(n/2) + 1 of n replicas, with n ≥ 2f + 1 to tolerate f failures. The difference is who coordinates. Any replica can be the coordinator for a command, and different replicas can coordinate different commands simultaneously, each collecting its own majority.

The safety argument turns on the same intersection property as majority quorums, applied to the dependency structure rather than to a log slot. A command’s dependencies are recorded at the replicas that accepted it, and a later command that reads the structure sees the dependencies of any command whose quorum intersects its own read quorum. Because two majorities intersect, a later command cannot miss a conflicting earlier command’s dependency record, and therefore cannot place itself before it.

The subtlety is that the dependency record and the command itself are written in the same step. A command that is written but whose dependencies are not yet known is a command that cannot be ordered, so the protocol writes both together and treats an entry without a complete dependency set as not yet committed. This is the analogue of the prepare phase in Paxos: the information a later coordinator needs must exist before the command is considered durable.

Sequence numbers are allocated per replica, so two replicas can pick the same number for different commands. The pair (sequence number, replica id) is what makes them distinct, and the ordering rule uses the pair, not the number alone. A protocol that uses only the number has a collision whenever two replicas coordinate concurrently at the same index, which is the common case in a leaderless design.

Execution without a total order

A replica executes a command when it has the command, its dependencies, and the dependencies of those dependencies, recursively, down to commands that are already executed. The recursion is the graph traversal, and the local state is a set of executed commands plus a frontier of commands whose dependencies are satisfied.

The traversal is deterministic given the dependency sets, so two replicas with the same sets produce the same execution order. The order is not the sequence-number order globally; it is a topological order of the dependency graph, and different replicas may execute independent commands in different orders. That is acceptable because independent commands commute, and the state after all of them is the same.

The conflict rule makes the graph acyclic in the cases that matter. If command A records B as a dependency and B records A, the pair is ordered by sequence number, so the cycle resolves to one direction. Longer cycles are possible in principle and must be broken by the same rule, which is why the dependency check has to be consistent across replicas: a replica that records a dependency the other side did not record can create a cycle that the sequence-number rule cannot break.

Execution can also proceed out of sequence-number order, which is the source of the latency benefit. A replica does not wait for command 5 to arrive before executing command 6 if 6 does not depend on 5. In a leader-based log, the commit index forces exactly this wait. Removing it removes the head-of-line blocking that a single slow follower can impose on the whole cluster.

Recovery is the hard part

A leader-based protocol’s recovery is an election: a new leader is chosen, and it repairs logs by walking backwards. The state that must be reconstructed is a prefix, and the repair is bounded by the log.

Leaderless recovery is harder because there is no single coordinator whose failure is a clean event. A command may have been coordinated by a replica that then failed, and the command may be partially replicated: some replicas have it with dependencies, some have it without, some do not have it at all. A recovery process must determine whether the command is committed and, if it is, what its dependency set is.

The recovery is itself a consensus problem, run by the replicas that hold the command’s partial state. They exchange their views of the command, and the dependency set that wins is the one supported by a quorum of the command’s acceptors. The rule has to handle the case where the failed coordinator wrote a dependency set that is not the one the majority holds, and the case where two different dependency sets both have quorum support because the coordinator sent different versions to different replicas. The resolution is a second round of agreement over the dependency set, which is where the protocol’s complexity concentrates.

The cost is visible in the tail. In steady state, a leaderless protocol can commit independent commands faster than a leader-based one, because there is no single serialization point. In the presence of failures, the recovery of a single command can require a full agreement round among its acceptors, and the recovery of many commands can require many such rounds. A cluster that fails often spends its time recovering, and the recovery path is much less exercised than the steady-state path, which is where implementation bugs hide.

Where the approach pays and where it does not

The workload that benefits has three properties: many independent keys, operations that are cheap to classify as conflicting or not, and a tolerance for the occasional extra round when conflicts are discovered. A key-value store over a large keyspace with point reads and writes fits. A system where every operation touches a global counter does not, because every command conflicts with every other and the dependency graph becomes a total order maintained by an expensive distributed protocol.

The failure model also matters. Leaderless protocols tolerate the loss of any replica without a failover pause, which is attractive for latency-sensitive services. They do not eliminate the need for quorums, so a partition still stops progress on the minority side, and the FLP constraints apply unchanged: termination is not guaranteed under arbitrary asynchrony, only eventual termination once the network stabilizes.

The operational cost is the real obstacle. A leader-based protocol has one code path for replication and one for election, and the election is a well-understood state machine. A leaderless protocol has a replication path, a conflict-detection path, a graph traversal, and a recovery path that is itself a consensus protocol. The surface area for bugs is larger, and the bugs are in the parts that run least often. That is why leaderless designs appear in systems that have measured the leader as their bottleneck and are willing to pay the complexity, rather than as a default.

What the design space actually contains

The progression from majority quorums through Paxos to a leaderless protocol is a progression in what gets ordered. Majority quorums order nothing by themselves; they provide the intersection property. Paxos uses the intersection to agree on a single value at a time and leaves the sequence to the application or to a multi-value extension. A log-based protocol like Raft orders everything, which simplifies the application and concentrates the coordination. A leaderless protocol orders only what conflicts, which distributes the coordination and moves the complexity into the dependency and recovery machinery.

None of these is strictly better. They are different answers to the question of how much ordering to buy and where to put the coordination cost. The constant across all of them is the quorum intersection that makes the ordering authoritative, and the timing assumption that makes it terminate.