Almost consensus: ABD and the edges of quorum replication - The Consensus
The Consensus Weekly<br>Get new deep dives, plus jobs and funding in software infrastructure, free in your inbox every week.Join the WeeklyWant a peek? Check out the archives.consensus<br>Almost consensus: ABD and the edges of quorum replication<br>From Thomas's 1979 majority voting, to ABD's linearizable register, to Cassandra's read repair: we provide a runnable Python tour of quorum replication, and show how ABD does not solve consensus.By Evgenii IvanovAugust 2, 2026 Focus
You are getting early access to this article as a subscriber. Your support makes articles like this possible. Thank you.The ABD algorithm, named after its creators Attiya, Bar-Noy, and Dolev, is a classic majority quorum algorithm from the 90s for implementing a linearizable distributed register. It is often presented as a "pre-consensus" topic before Paxos and Raft: simpler than consensus, but already rich enough to expose many important subtleties.Murat Demirbas has written a number of excellent posts on ABD. However, it still took me additional effort to draw sequence diagrams and build intuition for why ABD is not consensus. Besides that, there is another useful way to illustrate the boundary: to show why ABD is not Compare-and-Swap (CAS).We'll start with a brief introduction to quorum replication, building up simple implementations of a predecessor algorithm before getting to an implementation of ABD, and demonstrating features and limitations along the way.Quorum replication#<br>Quorum-based replication is an old idea. Thomas [1979] described a majority-voting approach for updating replicated databases: an update carries the timestamps of the values it was computed from, and a majority of replicas must vote that those values haven't changed before it is applied anywhere. Any two majorities intersect, so two conflicting updates can never both be accepted. Reads in Thomas touch only a single node and thus can be arbitrarily out of date.Gifford [1979] simplified the algorithm by pushing concurrency control out to the transaction system, and extended it so that reads happen through a quorum too.Quorum replication allows a system to tolerate unavailable replicas. Hardware and networks are unreliable, so some servers may be down or temporarily unreachable. If there are n replicas and both reads and writes use majorities, then at least ⌊n/2⌋+1 replicas must be available to perform an operation. For example, with n = 3, the majority is 2, so the system can tolerate one unavailable replica. With n = 5, the majority is 3, so it can tolerate two unavailable replicas.This explains why replication factors are commonly odd. Three and four replicas both tolerate only one unavailable replica: their majority sizes are 2 and 3, respectively. Similarly, five and six replicas both tolerate two failures. Moving from an odd replication factor to the next even one increases the quorum size without increasing the number of unavailable replicas the system can tolerate.To understand the papers better, we'll sketch out an algorithm influenced by both in Python. First, we'll have a Register which stores a value together with its timestamp. The timestamp consists of a time component, derived from a logical clock, and a stable, distinct ID. A Replica contains a register and a clock we'll use to generate new timestamps.class Register:<br>def __init__(self):<br>self.ts = (0, "-")<br>self.value = None
class Replica:<br>def __init__(self, replica_id: str):<br>self.replica_id = replica_id<br>self.clock = 0<br>self.register = Register()
def next_ts(self) -> tuple:<br>self.clock += 1<br>return (self.clock, self.replica_id)
quorum.pyA Replica accepts two kinds of requests. GET simply returns the current value and its timestamp. SET asks the replica to update its value and timestamp. The replica performs the update only if the new timestamp is strictly greater than the one it already stores, using replica_id as a tie-breaker when the logical-clock components are equal.def handle(self, msg: tuple) -> tuple:<br>if msg[0] == "GET":<br>return ("VALUE", self.register.ts, self.register.value)<br>if msg[0] == "SET":<br>_, ts, value = msg<br>if ts > self.register.ts:<br>self.register.ts, self.register.value = ts, value<br>return ("ACK",)<br>raise ValueError(f"unknown message {msg}")
quorum.pyThe operations could also be called READ and WRITE. We use GET and SET here to distinguish replica-level requests from complete quorum operations.We'll add a TGCluster class to create the replicas; following the convention that replicas are named R1, R2, and so on.class NoQuorum(Exception):<br>pass
class TGCluster:<br>def __init__(self, n: int):<br>self.replicas = [Replica(f"R{i + 1}") for i in range(n)]<br>self.majority = n // 2 + 1
def __repr__(self) -> str:<br>return ", ".join(f"{r.replica_id} holds {r.register.value} at {r.register.ts}"<br>for r in self.replicas)
quorum.pyWe'll also implement a broadcast helper that sends a message to the replicas and collects replies from the...