DATABASES Signal 406
Almost consensus: ABD and the edges of quorum replication
↗
Illustration only Photo by Marc PEZIN on Unsplash
The article walks through ABD, a majority-quorum algorithm that implements a linearizable register, and shows why it does not achieve consensus or provide compare-and-swap semantics.
Engineers who rely on simple quorum reads/writes for linearizability must recognize that such schemes cannot solve agreement problems that require consensus. Knowing ABD's limits helps decide when a lightweight register suffices and when a full consensus protocol like Paxos or Raft is necessary.
Written by elseif from the cluster below · every claim links back to a sourceThe three things worth knowing
ABD uses intersecting majorities for reads and writes to guarantee a linearizable register without running a consensus algorithm.
The algorithm cannot implement compare-and-swap because concurrent writes may leave different values on replicas despite quorum intersection.
A runnable Python demonstration illustrates ABD's behavior, its fault tolerance (up to ���n/2���−1 unavailable replicas), and where consensus-level coordination is still required.
THE READ
What the cluster adds up to.
ABD (Attiya-Bar-Noy-Dolev) is presented as a classic majority-quorum construction from the 1990s that yields a linearizable distributed register. It is often introduced before Paxos or Raft because it is simpler than full consensus yet still exposes subtle distributed-systems challenges. The article situates ABD after Thomas’s 1979 majority-voting scheme and Gifford’s 1979 read-quorum extension, noting how both rely on quorum intersection to prevent conflicting updates.
The accompanying Python tour defines a Register holding a value and a timestamp, a Replica that updates only when the incoming timestamp is strictly greater (using the replica ID as a tie-breaker), and a TGCluster that creates a set of replicas and computes the majority size. A broadcast helper sends a message to all replicas and collects replies from the required quorum, allowing the implementation of GET and SET operations that together emulate a quorum-based read/write service.
Through this code the article demonstrates that ABD provides linearizability for individual registers: a read that contacts a majority is guaranteed to see the latest completed write. However, the same mechanism fails to solve consensus or to implement compare-and-swap. Concurrent writes can leave different values on different majorities, and without an additional agreement step the system cannot converge on a single value, showing ABD’s limitation to register-level semantics only.
Adopting ABD gives a fault-tolerant linearizable register that tolerates up to ���n/2���−1 replica failures with only two round-trips per operation (one to send the request, one to collect acknowledgments). The cost is the need to manage logical timestamps and handle tie-breaks, plus the latency of waiting for a majority. When an application requires operations that depend on global agreement, such as leader election, atomic compare-and-swap, or multi-object transactions, ABD is insufficient and a consensus protocol must be layered on top, increasing complexity and message overhead.
Written by elseif from the cluster below · checked for specifics the sources never containedTHE CLUSTER