The Linearizable Register Beneath Every Coordination Primitive

A coordination service exposes a small surface: read a value, write a value, compare a value and swap it, list the children of a path, watch a path for changes. Everything else a distributed application needs from it, from mutual exclusion to leader election to group membership, is expressed by combining those operations. The reason such a thin interface suffices is that all of it is one object with one consistency property, and the property is strong enough that clients can reason about their own protocols as if the service were a single machine.

The contract the service actually offers

The central object is a register: a named cell holding a value. The service’s promise is that every operation on that cell appears to take effect at a single instant between its invocation and its response, and that all clients agree on the order of those instants. This is linearizability, and its practical content is that a read which returns after a write has completed must return the written value or something later. A read that overlaps a write may return either.

The property is stronger than it sounds, and the strength is exactly what makes client-side protocols tractable. Consider a client that reads a value v1, computes a new value from it, and writes it back. If the read and the write were allowed to be reordered relative to other clients’ operations, the client’s computation would be based on a state that never existed at any instant, and two clients could each compute a “next” value from the same predecessor without either noticing. With linearizability, the read’s instant is a real point in the global order, so any competing write that lands after it is visible to the write that follows, and the comparison-and-swap operation below can detect the interference.

Sequential consistency, the weaker model, guarantees only that all clients see the same order, not that the order respects real time. A register that is sequentially consistent can serve a read from a stale replica while a write to the same cell has already been acknowledged to another client, as long as the ordering of operations in the single global sequence is consistent with each client’s own program order. For a lock, that is fatal: a client could acquire a lock that another client has already acquired and released, because the acquire was ordered before the release in the global sequence even though it happened later in real time. Coordination needs the real-time constraint, which is why these services pay for consensus rather than replication with local reads.

Why the primitive is not a lock

The obvious way to build mutual exclusion on a register is to read the cell, and if it is empty, write one’s own identifier into it. Two clients can do this concurrently, both read empty, both write. With a plain write, the second write overwrites the first and both clients believe they hold the lock. The register is linearizable, so the two writes have a definite order, but neither client can learn that order from the result of its own write.

The fix is a conditional write. A compare-and-swap takes an expected value and a new value and applies the write only if the cell currently holds the expected value, returning whether it did. Its linearization point is the comparison, so of two concurrent compare-and-swaps with the same expected value, at most one succeeds. This turns the register into the primitive that all the higher-level structures need, and it is the reason the operation exists in every such service rather than being a convenience.

With compare-and-swap, mutual exclusion becomes a loop: read the cell, if it is empty attempt to swap empty for one’s own identifier, if the swap fails re-read and retry. The loop is optimistic, so it can spin under contention, and it must handle the case where the holder’s identifier is a value that has since been deleted. In practice the cell holds a structured record with a holder and a version or a lease deadline, which makes the comparison meaningful and lets versioned compare-and-swap loops replace a bare empty-check.

Ordering as a service

A register that returns values is not enough for the harder coordination problems, because several of them need to know the relative order of events rather than their values. Leader election needs to pick the oldest candidate. A fair lock queue needs to serve waiters in arrival order. A membership list needs a stable sequence so that two observers can agree on who joined before whom.

The standard trick is to make the write return a value the client did not supply: a monotonically increasing sequence number assigned by the service at the linearization point. A client that creates a child node under a path receives a name that embeds such a number, and sorting the children by that number recovers the order in which the creations were linearized. This is how ZooKeeper’s sequential nodes work, and it is why the ordering property is a property of the service rather than something the client can reconstruct after the fact. The client cannot sort by its own timestamps, because clocks disagree; it cannot sort by request send time, because the network reorders. Only the service’s assignment reflects the actual order.

The same sequence number serves as a fencing token when the resource being protected is outside the service. A client that acquires a lock receives the sequence number of its acquisition, and every write it makes to the protected resource carries that number. A resource that remembers the highest number it has seen rejects writes bearing lower ones, which converts the ordering guarantee of the register into an ordering guarantee on the actual data. The full argument for why this is necessary rather than optional appears in fencing tokens and advisory locks.

Reading the state without a lock

Not every operation needs to mutate. Listing the members of a group, or reading a configuration value, is a read, and reads are where the cost of linearizability becomes visible. A linearizable read in a consensus-backed service must either go through the leader, which serializes it with writes, or use a read-index protocol in which the leader confirms its leadership with a quorum before serving, or a lease that lets the leader serve reads locally while it holds a valid grant. All three keep the read linearizable; they differ in how much coordination each read costs.

The alternative, reading from a follower, gives up linearizability for latency and is what makes follower reads unsuitable for coordination decisions. A stale read of a membership list may omit a member that has just joined, and a client that acts on that list may hand out a resource the new member already holds. The distinction matters most in exactly the cases where coordination is invoked, which is to say during failures and reconfigurations, when replication lag is largest.

A second subtlety: linearizable single-object reads do not compose into a linearizable multi-object snapshot. Reading path A and then path B can observe A before a concurrent transaction that wrote both, and B after it, producing a state in which neither the old nor the new configuration is intact. A service that needs atomic multi-object reads must offer them explicitly, typically as a multi-operation that the service linearizes as a unit, or must expose a version number that the client checks and retries on. Treating a pair of independent reads as a snapshot is a common source of configuration bugs, and it is the reason many coordination APIs include a bulk read that returns a consistent version alongside the values.

Where the abstraction stops paying

The register model assumes the service is available. When a quorum of the service is unreachable, the register stops serving, and every protocol built on it stops with it. That is a deliberate trade: a coordination service that answered reads during a partition would answer them inconsistently, and a lock service that hands out the same lock twice is worse than one that hands out nothing. The consequence is that the coordination service becomes a dependency whose unavailability halts the clients, which drives the design guidance to keep the state small and the operations rare. A system that consults the register on every request has imported the service’s availability into its own request path; one that consults it only when leadership changes or membership shifts has confined the dependency to the moments when it is genuinely needed.

The register also assumes that the client can be trusted to act on what it read. Linearizability orders the operations, but it does not prevent a client from reading a valid value, stalling for an arbitrary time, and then acting on a state that has since changed. That gap is not a flaw in the register; it is the reason the register is usually wrapped in a lease, so that the value carries an expiry and the client’s right to act on it lapses on a schedule rather than on the client’s diligence.