Almost consensus: ABD and the edges of quorum replication

# Almost consensus: ABD and the edges of quorum replication Source: [https://theconsensus.dev/p/2026/08/02/almost-consensus.html](https://theconsensus.dev/p/2026/08/02/almost-consensus.html) [](https://theconsensus.dev/) On software infrastructure\. ## Almost consensus: ABD and the edges of quorum replication 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](https://theconsensus.dev/p/2026/08/02/almost-consensus.html#) You are getting early access to this article as a subscriber\. Your support makes articles like this possible\. Thank you\. [The ABD algorithm](https://dl.acm.org/doi/10.1145/200836.200869?from_theconsensus=1), 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](https://muratbuffalo.blogspot.com/2012/05/replicatedfault-tolerant-atomic-storage.html?from_theconsensus=1)[of](https://muratbuffalo.blogspot.com/2015/02/paper-summary-perspectives-on-cap.html?from_theconsensus=1)[excellent](https://muratbuffalo.blogspot.com/2019/06/is-this-consensus.html?from_theconsensus=1)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[\#](https://theconsensus.dev/p/2026/08/02/almost-consensus.html#quorum-replication) Quorum\-based replication is an old idea\.[Thomas \[1979\]](https://pages.cs.wisc.edu/~remzi/Classes/739/Fall2018/Papers/thomas79-quorums.pdf?from_theconsensus=1)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\]](https://dl.acm.org/doi/10.1145/800215.806583?from_theconsensus=1)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](https://lamport.azurewebsites.net/pubs/time-clocks.pdf?from_theconsensus=1), and a stable, distinct ID\. A`Replica`contains a register and a clock we'll use to generate new timestamps\. ``` class Register: def __init__(self): self.ts = (0, "-") self.value = None class Replica: def __init__(self, replica_id: str): self.replica_id = replica_id self.clock = 0 self.register = Register() def next_ts(self) -> tuple: self.clock += 1 return (self.clock, self.replica_id) ``` quorum\.py A`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: if msg[0] == "GET": return ("VALUE", self.register.ts, self.register.value) if msg[0] == "SET": _, ts, value = msg if ts > self.register.ts: self.register.ts, self.register.value = ts, value return ("ACK",) raise ValueError(f"unknown message {msg}") ``` quorum\.py The 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): pass class TGCluster: def __init__(self, n: int): self.replicas = [Replica(f"R{i + 1}") for i in range(n)] self.majority = n // 2 + 1 def __repr__(self) -> str: return ", ".join(f"{r.replica_id} holds {r.register.value} at {r.register.ts}" for r in self.replicas) ``` quorum\.py We'll also implement a`broadcast`helper that sends a message to the replicas and collects replies from the required majority quorum\. \(We use the`artificially\_X`convention to specify arguments that diverge from standard execution so that we can trigger scenarios in testing\.\) ``` def broadcast(self, msg: tuple, artificially_reachable: list[Replica] | None = None, artificially_incomplete: bool = False) -> list: replies = [r.handle(msg) for r in artificially_reachable or self.replicas] if len(replies) < self.majority and not artificially_incomplete: raise NoQuorum(f"{len(replies)} of {len(self.replicas)} replicas " f"replied, {self.majority} needed") return replies ``` quorum\.py Here, we make an important simplification\. In a real system, some replicas might be down and never reply\. A production implementation would therefore send requests asynchronously, use timeouts or deadlines, and stop waiting once enough replies had arrived\. At the same time, this demonstrates an important property of quorum algorithms: a request is normally sent to all eligible replicas, but the operation waits only for a quorum of replies\. Responses from the remaining replicas may arrive later or not at all\. Now we can implement the quorum write operation\. We increment the timestamp for each operation and wait for a majority of replicas to store the new value\. ``` def quorum_write(self, writer: Replica, value, artificially_reachable=None, artificially_incomplete: bool = False) -> list: return self.broadcast(("SET", writer.next_ts(), value), artificially_reachable, artificially_incomplete) ``` quorum\.py The quorum read chooses the value with the greatest timestamp among the replies from a majority of replicas\. ``` def quorum_read(self, artificially_reachable=None) -> tuple: replies = self.broadcast(("GET",), artificially_reachable) return max(((ts, v) for _, ts, v in replies), key=lambda p: p[0]) ``` quorum\.py Let's try it out in the terminal\. We'll build a cluster, write an initial value`"A"`to the cluster, write a second value`"B"`that is artificially sent only to two replicas in the cluster, then we'll read back the register from the cluster in every quorum possible and observe that they all agree the value is`"B"`\. ``` $ python3 -c ' import itertools from quorum import TGCluster c = TGCluster(3) r1, r2, r3 = c.replicas c.quorum_write(r1, "A") # Pretend r3 is unavailable. c.quorum_write(r1, "B", artificially_reachable=[r1, r2]) # Show r3 without "B". print("cluster internal state:", c) # Yet every possible quorum returns "B". for quorum in itertools.combinations(c.replicas, 2): ts, value = c.quorum_read(artificially_reachable=quorum) print(f"quorum state {{{quorum[0].replica_id}, {quorum[1].replica_id}}}: {value} at {ts}") assert value == "B" ' cluster internal state: R1 holds B at (2, 'R1'), R2 holds B at (2, 'R1'), R3 holds A at (1, 'R1') quorum state {R1, R2}: B at (2, 'R1') quorum state {R1, R3}: B at (2, 'R1') quorum state {R2, R3}: B at (2, 'R1') ``` At first glance, the idea looks almost too simple: write to a quorum, read from a quorum, and pick the newest value\. But when we introduce concurrency, message delays, and multiple readers, you start to see the limitations\. Consider the execution below, a classic example that appears in many textbooks, including the famous[Designing Data\-Intensive Applications](https://www.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/?from_theconsensus=1)\. R3R2R1Reader BReader AWriterR3R2R1Reader BReader AWriter3 replicas, majority = 2\. Every replica holds \(ts=0, x=A\)\.Writer sends SET\(ts=1, x=B\) to all three\. The copies for R1 and R2 are delayed in the network\.1 ACK of the 2 it needs — the write is still in progress\.Reader A: GET from everyone, return once 2 replies are in\.Highest timestamp wins\. Reader A returns x = B\.Reader B starts only after Reader A has returned\.Reader B returns x = A\. \(The register went backwards\.\)The delayed SETs reach R2 and R1 only now, and the write completes\.SET\(ts=1, x=B\)1ACK2GET3GET4\(ts=1, x=B\)5\(ts=0, x=A\)6GET7GET8\(ts=0, x=A\)9\(ts=0, x=A\)10 ``` sequenceDiagram autonumber participant W as Writer participant A as Reader A participant B as Reader B participant R1 as R1 participant R2 as R2 participant R3 as R3 Note over W,R3: 3 replicas, majority = 2. Every replica holds (ts=0, x=A). Note over W,R3: Writer sends SET(ts=1, x=B) to all three. The copies for R1 and R2 are delayed in the network. W->>R3: SET(ts=1, x=B) R3-->>W: ACK Note over W: 1 ACK of the 2 it needs — the write is still in progress. Note over A,R3: Reader A: GET from everyone, return once 2 replies are in. A->>R2: GET A->>R3: GET R3-->>A: (ts=1, x=B) R2-->>A: (ts=0, x=A) Note over A: Highest timestamp wins. Reader A returns x = B. Note over B,R3: Reader B starts only after Reader A has returned. B->>R1: GET B->>R2: GET R1-->>B: (ts=0, x=A) R2-->>B: (ts=0, x=A) Note over B: Reader B returns x = A. (The register went backwards.) Note over W,R3: The delayed SETs reach R2 and R1 only now, and the write completes. ``` There are three important takeaways from this example\. First, there is no separate notion of commit\. A replica exposes a value as soon as it receives the write\. The writer may not have completed the operation yet, but a concurrent reader can already observe the new value from one replica\. A loose DBMS analogy is[Read Uncommitted](https://jepsen.io/consistency/models/read-uncommitted?from_theconsensus=1): a reader may observe a value from an operation that has not completed yet\. The analogy is not exact, but the intuition is useful: this simple quorum algorithm has no separate mechanism to distinguish a value from an incomplete operation from a value that is already stable\. We can see this in code\. ``` $ python3 -c ' from quorum import TGCluster, NoQuorum c = TGCluster(3) r1, r2, r3 = c.replicas c.quorum_write(r1, "A") # The write reaches only R1, so it never collects a majority. R1 stored the # value anyway: a replica exposes a write as soon as it arrives. try: c.quorum_write(r1, "B", artificially_reachable=[r1]) except NoQuorum as e: print(f"the write never completed: {e}") a = c.quorum_read(artificially_reachable=[r1, r2]) b = c.quorum_read(artificially_reachable=[r2, r3]) print(f"quorum state {{R1, R2}}: {a[1]} at {a[0]}") print(f"quorum state {{R2, R3}}: {b[1]} at {b[0]}") assert a[1] == "B" assert b[1] == "A" ' the write never completed: 1 of 3 replicas replied, 2 needed quorum state {R1, R2}: B at (2, 'R1') quorum state {R2, R3}: A at (1, 'R1') ``` Second, this quorum algorithm is not atomic\. This is closely related to the previous point\. While a write is still in progress, one reader can observe the new value, and a later reader can still observe the old value\. For a single replicated value, also called a register, "atomicity" here means linearizability: once one completed read observes the new value, a later read that starts after it must not go back and return the old one as it does in our example\. We can also see this in code\. ``` $ python3 -c ' from quorum import TGCluster c = TGCluster(3) r1, r2, r3 = c.replicas c.quorum_write(r3, "A") # Pretend only r3 is reachable. c.quorum_write(r3, "B", artificially_reachable=[r3], artificially_incomplete=True) a = c.quorum_read(artificially_reachable=[r2, r3]) # r3 has B b = c.quorum_read(artificially_reachable=[r1, r2]) # neither has B print(f"quorum state {{R2, R3}}: {a[1]}") print(f"quorum state {{R1, R2}}: {b[1]}") assert (a[1], b[1]) == ("B", "A") ' quorum state {R2, R3}: B quorum state {R1, R2}: A ``` Third, both reads and writes are single\-phase operations, which is a very nice property\. A writer sends the value to replicas and waits for a quorum of acknowledgements\. A read contacts a quorum and returns the value with the highest timestamp\. On the other hand, there is no second phase that makes the value observed by a reader stable for future readers\. Let's see how ABD solves this linearizability problem\. ## ABD[\#](https://theconsensus.dev/p/2026/08/02/almost-consensus.html#abd) ABD adds a crucial second phase to reads: after a reader finds the value with the highest timestamp, it writes that value back to a quorum before returning it\. This write\-back phase prevents the system from "going back in time"\. If one read returns a newer value, later reads that start after the first one completes are forced to observe that value or an even newer one\. For the ABD implementation, we'll build a new class that reuses parts of the`TGCluster`class\. The`abd\_read`function is very close to`quorum\_read`; it merely adds the write\-back phase\. ``` class ABDCluster(TGCluster): def abd_read(self, artificially_reachable=None) -> tuple: ts, value = self.quorum_read(artificially_reachable) # phase 1 self.broadcast(("SET", ts, value), artificially_reachable) # phase 2 return ts, value ``` quorum\.py The execution diagram becomes: R3R2R1Reader BReader AWriterR3R2R1Reader BReader AWriter3 replicas, majority = 2\. Every replica holds \(ts=0, x=A\)\.Writer sends SET\(ts=1, x=B\) to all three\. The copies for R1 and R2 are delayed in the network\.1 ACK of the 2 it needs\. \(The write is still in progress\.\)Reader A, phase 1: GET from everyone, continue once 2 replies are in\.Highest timestamp wins: \(ts=1, x=B\)\.Reader A, phase 2: write the winner back to a quorum before returning it\.Reader A returns x = B\. Even though the writer has not completed its write, the write\-back made that value permanent\.Reader B starts only after Reader A has returned, and still before the delayed SETs arrive\.R2 is in both quorums\. \{R2,R3\} took the write\-back, \{R1,R2\} is being read now\. Quorum intersection carries the value across\.Reader B returns x = B\. No going backwards\.The delayed SETs arrive only now and the write completes\. R2 already holds ts=1, so nothing changes there\. R1 finally installs \(ts=1, x=B\)\.SET\(ts=1, x=B\)1ACK2GET3GET4\(ts=1, x=B\)5\(ts=0, x=A\)6SET\(ts=1, x=B\)7SET\(ts=1, x=B\)8ACK9ACK10GET11GET12\(ts=0, x=A\)13\(ts=1, x=B\)14 ``` sequenceDiagram autonumber participant W as Writer participant A as Reader A participant B as Reader B participant R1 as R1 participant R2 as R2 participant R3 as R3 Note over W,R3: 3 replicas, majority = 2. Every replica holds (ts=0, x=A). Note over W,R3: Writer sends SET(ts=1, x=B) to all three. The copies for R1 and R2 are delayed in the network. W->>R3: SET(ts=1, x=B) R3-->>W: ACK Note over W: 1 ACK of the 2 it needs. (The write is still in progress.) Note over A,R3: Reader A, phase 1: GET from everyone, continue once 2 replies are in. A->>R2: GET A->>R3: GET R3-->>A: (ts=1, x=B) R2-->>A: (ts=0, x=A) Note over A: Highest timestamp wins: (ts=1, x=B). Note over A,R3: Reader A, phase 2: write the winner back to a quorum before returning it. A->>R2: SET(ts=1, x=B) A->>R3: SET(ts=1, x=B) R2-->>A: ACK R3-->>A: ACK Note over A: Reader A returns x = B. Even though the writer has not completed its write, the write-back made that value permanent. Note over B,R3: Reader B starts only after Reader A has returned, and still before the delayed SETs arrive. B->>R1: GET B->>R2: GET R1-->>B: (ts=0, x=A) R2-->>B: (ts=1, x=B) Note over R2: R2 is in both quorums. {R2,R3} took the write-back, {R1,R2} is being read now. Quorum intersection carries the value across. Note over B: Reader B returns x = B. No going backwards. Note over W,R3: The delayed SETs arrive only now and the write completes. R2 already holds ts=1, so nothing changes there. R1 finally installs (ts=1, x=B). ``` While the original ABD paper only described an algorithm for a single writer and multiple readers,[Lynch & Shvartsman \[1996\]](https://groups.csail.mit.edu/tds/papers/Lynch/FTCS97.pdf?from_theconsensus=1)add support for multiple writers in ABD \(MWABD\)\. In this scenario, a writer cannot safely invent the next timestamp locally because another writer may already have produced a greater one\. Therefore, before writing, a writer first queries a quorum, finds the maximum timestamp, and then writes with a greater timestamp\. ``` def query_phase(self, writer: Replica, artificially_reachable=None): ts, seen = self.quorum_read(artificially_reachable) writer.clock = max(writer.clock, ts[0]) return seen def abd_write(self, writer: Replica, value, artificially_reachable=None): self.query_phase(writer, artificially_reachable) # phase 1 return self.quorum_write(writer, value, artificially_reachable) # phase 2 ``` quorum\.py Let's see it in action\. A write reaches only one replica, but subsequent reads propagate it to the remaining replicas through write\-back\. Note that in a few of these ABD examples we are going to pull apart`abd\_write`into the two phases ourselves so that we can control execution more finely\. So if you see us using`quorum\_write`in an ABD example it isn't sleight of hand\. ``` $ python3 -c ' from quorum import ABDCluster c = ABDCluster(3) r1, r2, r3 = c.replicas c.abd_write(r3, "A") # Set initial value cluster-wide. # Manually run an ABD write of B so we can demonstrate the quorum_write failing. c.query_phase(r3, artificially_reachable=[r1, r2, r3]) c.quorum_write(r3, "B", artificially_reachable=[r3], artificially_incomplete=True) print(f"cluster internal state (B is in R3): {c}") a = c.abd_read(artificially_reachable=[r2, r3]) print(f"quorum state {{R2, R3}}: {a}") print(f"cluster internal state (B is in R2, R3): {c}") b = c.abd_read(artificially_reachable=[r1, r2]) print(f"quorum state {{R1, R2}}: {b}") print(f"cluster internal state (B is in R1, R2, R3): {c}") ' cluster internal state (B is in R3): R1 holds A at (1, 'R3'), R2 holds A at (1, 'R3'), R3 holds B at (2, 'R3') quorum state {R2, R3}: ((2, 'R3'), 'B') cluster internal state (B is in R2, R3): R1 holds A at (1, 'R3'), R2 holds B at (2, 'R3'), R3 holds B at (2, 'R3') quorum state {R1, R2}: ((2, 'R3'), 'B') cluster internal state (B is in R1, R2, R3): R1 holds B at (2, 'R3'), R2 holds B at (2, 'R3'), R3 holds B at (2, 'R3') ``` If we remove the write\-back phase from`abd\_read`and the initial timestamp\-query phase from`abd\_write`, we return to the simple quorum operations described earlier\. Note that ABD pays for the extra phase with an additional network round trip\. A read needs a query phase followed by a write\-back phase, and a multi\-writer write needs a timestamp\-query phase followed by the actual write phase\. This is one of the practical attractions of leader\-based protocols: once a Raft or Multi\-Paxos leader is established, a new command can usually be replicated and committed in one leader\-to\-quorum round trip, while also providing a stronger abstraction: a single ordered log of commands\. Let's take a look at another limitation of ABD\. ## ABD is not Compare\-and\-Swap[\#](https://theconsensus.dev/p/2026/08/02/almost-consensus.html#abd-is-not-compare-and-swap) Consider two concurrent writes:`\(t1, v1\)`and`\(t2, v2\)`, where`t2 \> t1`\. Because of network delays, messages from the second write may reach some replicas before messages from the first write\. ABD replicas are monotonic in timestamps: a replica only moves to a higher timestamp and never goes back\. Therefore, both orders below leave the replica with`\(t2, v2\)`: ``` apply(t1, v1); apply(t2, v2) => (t2, v2) apply(t2, v2); apply(t1, v1) => (t2, v2) ``` The important part is that the second case can still be acknowledged successfully by the replica\. If a replica already stores \(t2, v2\) and later receives \(t1, v1\), it does not overwrite the value, but it can still acknowledge the request\. Let's see it happen\. ``` $ python3 -c ' from quorum import ABDCluster c = ABDCluster(3) r1, r2, r3 = c.replicas # Start a first request from r1. c.query_phase(r1, artificially_reachable=[r1, r2]) # Then start and finish a second request from r2. c.abd_write(r2, "v2") # Now finish the abd_write on r1. acks = c.quorum_write(r1, "v1", artificially_reachable=[r1, r2]) print(f"the stale write got {len(acks)} ACKs, a majority of 3") print(c) assert len(acks) == c.majority # the stale write "succeeds" assert all(r.register.value == "v2" for r in c.replicas) # ...and vanishes ' the stale write got 2 ACKs, a majority of 3 R1 holds v2 at (1, 'R2'), R2 holds v2 at (1, 'R2'), R3 holds v2 at (1, 'R2') ``` This is one of the reasons ABD is not Compare\-and\-Swap \(CAS\)\. A stale ABD write is not rejected as a failed conditional update\. It is simply ignored locally if the replica has already seen a newer timestamp\. The write operation may still complete because it can collect enough acknowledgements\. Since the two writes are concurrent, the lower\-timestamped write can be linearized before the higher\-timestamped one\. The query phase guarantees a different property: if one write has already completed before another write starts, the later writer will observe it through quorum intersection and choose a higher timestamp\. But it does not prevent a concurrent writer from choosing a higher timestamp and reaching some replicas first\. Now, instead of writes, let's consider two CAS operations \(I borrowed the example and the CAS formulation from one of Roman Lipovskiy's lectures on the topic\):  CAS breaks the ABD model exactly because CAS depends on the previous value\. An ABD write says: ``` store this value if its timestamp is newer ``` This rule is monotonic\. Messages may be reordered by the network, but replicas can still process them safely: if a replica has already seen a newer timestamp, it can ignore the older value and still acknowledge the request\. CAS says something different: ``` store the new value only if the current value is still X ``` Now the "current value" is not just a local fact in one replica\. In a distributed system with concurrent and partially completed operations, the current value is the result of a global ordering choice\. In the example above,`CAS1\(x, y\)`and`CAS2\(y, z\)`are concurrent\. For`CAS2\(y, z\)`to return success, the system must first decide that`CAS1\(x, y\)`happened before it, because otherwise the value is still`x`, not`y`\. But making this decision is exactly the kind of serialization problem ABD doesn't solve\. Let's reproduce the execution from the diagram\. CAS1 stalls after reaching one replica\. CAS2 reads that replica, observes`y`, and succeeds\. When CAS1's client re\-reads to resolve the ambiguity, it finds`z`and concludes its swap never happened, yet CAS2's success was justified by that very swap\. ABD gives the wrapper no way to learn CAS1's true fate, so whatever it tells the client is a guess\. A consensus\-backed CAS cannot produce this pair of answers, because it decides CAS1's fate before letting CAS2 observe`y`\. ``` $ python3 -c ' from quorum import ABDCluster, NoQuorum c = ABDCluster(3) r1, r2, r3 = c.replicas c.quorum_write(r2, "x") seen1 = c.query_phase(r1, artificially_reachable=[r1, r2]) try: if seen1 == "x": c.quorum_write(r1, "y", artificially_reachable=[r1]) except NoQuorum as e: print(f"CAS1 stalled: {e}") seen2 = c.query_phase(r3, artificially_reachable=[r1, r3]) ok2 = seen2 == "y" if ok2: c.quorum_write(r3, "z", artificially_reachable=[r1, r3]) ok1 = c.query_phase(r1, artificially_reachable=[r1, r2]) == "x" final = c.abd_read(artificially_reachable=[r1, r2])[1] print(f"CAS1(x->y) -> {ok1}, CAS2(y->z) -> {ok2}, register = {final}") assert ok2 and not ok1 # CAS2 succeeded by consuming the y CAS1 disowned assert final == "z" ' CAS1 stalled: 1 of 3 replicas replied, 2 needed CAS1(x->y) -> False, CAS2(y->z) -> True, register = z ``` Naively combining an ABD read with a conditional ABD write does not give us a linearizable CAS: ``` read + write via ABD -> linearizable register read + conditional write via ABD -> not a linearizable CAS ``` To implement CAS, we need a serializer: a correctly fenced leader, a Paxos/Raft log, or another consensus\-like protocol that establishes a single order of conditional updates\. ## Why ABD is not consensus[\#](https://theconsensus.dev/p/2026/08/02/almost-consensus.html#why-abd-is-not-consensus) Distributed consensus is closely related to replicated state machines\. A replicated state machine usually relies on a sequence of consensus decisions: we have an ordered sequence of commands \(log records\) that must be applied to the state machine in the same order on all replicas: ``` x1 = slot1 = command1 = 1 x2 = slot2 = command2 = 2 x3 = slot3 = command3 = 3 command1 = 1 command2 = 2 command3 = 3 ... ``` In the replicated\-state\-machine setting, the problem is not only finding the latest value\. It is agreeing on the whole ordered history, or at least on an ever\-growing prefix of that history\. Now, consider the following ABD\-like execution: Replica 3Replica 2Replica 1WriterReplica 3Replica 2Replica 1WriterWrite1 \(x1=1\)Write2 \(x2=2\)Write3 \(x3=3\)R1 crasheswrite\(x1=1\)1ok2write\(x1=1\)3write\(x2=2\)4ok5write\(x2=2\)6ok7write\(x3=3\)8ok9write\(x3=3\)10ok11 ``` sequenceDiagram autonumber participant W as Writer participant R1 as Replica 1 participant R2 as Replica 2 participant R3 as Replica 3 Note over W,R3: Write1 (x1=1) W->>R1: write(x1=1) R1-->>W: ok W-xR2: write(x1=1) Note over W,R3: Write2 (x2=2) W->>R2: write(x2=2) R2-->>W: ok W->>R3: write(x2=2) R3-->>W: ok Note over W,R3: Write3 (x3=3) W->>R1: write(x3=3) R1-->>W: ok W->>R2: write(x3=3) R2-->>W: ok Note over R1: R1 crashes ``` After`R1`crashes, the historical footprint of the writes may look like this: ``` R1 unavailable: x1 = 1, x3 = 3 R2: x2 = 2, x3 = 3 R3: x2 = 2 ``` If these are ABD writes with increasing timestamps, ABD can still recover the latest register value\. A read from the available quorum`\{R2, R3\}`observes`x3 = 3`from`R2`; before returning, it writes`x3 = 3`back to a quorum, so future reads will not go back to`x2 = 2`\. That is exactly what ABD is designed to do\. But this is not enough for a replicated log\. ABD can recover the latest value, but it cannot reconstruct which earlier values were supposed to be committed log entries\. Was`x1 = 1`a real first command, or just a partial write? Was`x2 = 2`the next committed command, or just a later overwrite that is now obsolete? ABD intentionally does not preserve enough information to answer these questions\. This is the key distinction\. ABD collapses the past into the latest timestamped value\. It erases the difference between: ``` an old command that was chosen as part of the log and then followed by later commands ``` and: ``` a value that was only a partial or failed register write and can be forgotten ``` For a register, this is fine: the abstraction only promises a linearizable latest value\. For a replicated log, this is not enough: the abstraction must preserve a sequence of decisions\. That is why Murat[writes](https://muratbuffalo.blogspot.com/2019/06/is-this-consensus.html?from_theconsensus=1): "ABD is memoryless and hedonistic\. ABD is happy with unresolved, partial acceptances in the past\. Heck, it will completely overwrite a value that is accepted by all nodes if another write comes with a higher timestamp\." A curious nuance: ABD can store a value that happens to be a whole log snapshot, but then every write overwrites the whole snapshot as a single register value\. That is not the same thing as solving distributed consensus for individual log slots\. ``` $ python3 -c ' from quorum import ABDCluster c = ABDCluster(3) r1, r2, r3 = c.replicas c.abd_write(r2, ("a",)) # Two appenders read the same log concurrently. seen1 = c.query_phase(r1, artificially_reachable=[r1, r2]) seen2 = c.query_phase(r3, artificially_reachable=[r2, r3]) c.quorum_write(r1, seen1 + ("b",), artificially_reachable=[r1, r2]) c.quorum_write(r3, seen2 + ("c",), artificially_reachable=[r2, r3]) final = c.abd_read(artificially_reachable=[r1, r2])[1] print(f"both appends completed; log = {final}") assert final == ("a", "c") assert "b" not in final ' both appends completed; log = ('a', 'c') ``` ## ABD in real systems[\#](https://theconsensus.dev/p/2026/08/02/almost-consensus.html#abd-in-real-systems) Textbook ABD gives us a linearizable register: writes store a timestamped value on a quorum, reads contact a quorum, pick the newest value, and write it back before returning\. The write\-back is what prevents the system from going backward after a read has observed a newer value\. A very similar idea appears in practical systems as read repair\. For example, Cassandra's blocking[read repair](https://cassandra.apache.org/doc/stable/cassandra/managing/operating/read_repair.html?from_theconsensus=1)is designed to provide monotonic quorum reads: if one quorum read observes a newer value, a later quorum read should not return an older one\. This is probably the closest production analogy to ABD's read write\-back phase\. This also explains why systems like Cassandra need a[separate path for CAS\-like operations](https://cassandra.apache.org/doc/latest/cassandra/architecture/guarantees.html?from_theconsensus=1#lightweight-transactions-with-linearizable-consistency)\. Ordinary quorum reads and writes are good for "store this latest value" semantics, but not for "store this value only if the current value is still X"\. For that, Cassandra uses lightweight transactions based on Paxos\. This is the practical version of the same boundary: read/write quorum storage is not enough once the operation depends on a single serialized order of updates\. ## Parting thoughts[\#](https://theconsensus.dev/p/2026/08/02/almost-consensus.html#parting-thoughts) As Murat[writes](https://muratbuffalo.blogspot.com/2019/06/is-this-consensus.html?from_theconsensus=1): > As the closing word on ABD, we should note that ABD is still useful for storage and linearizability, it solves the atomic storage problem\. Here comes the difference between stateless operations \(register operations put and get\) versus stateful operations \(commands in general that mutate state, which by definition depends on the state they are invoked/executed\)\. For storage, we don't need stateful operations\. Using ABD we achieve linearizability, and can serve strong\-consistency reads via using ABD even with multiple clients\. I hope this post helps build better intuition about ABD, which is useful for understanding Paxos and Raft more deeply\. If you prefer a more academic treatment,[Quorum Systems With Applications to Storage and Consensus](https://link.springer.com/book/10.1007/978-3-031-02007-0?from_theconsensus=1)is a great choice for studying the topic with scholarly rigor\. Noticed a mistake? Have a question or comment? Write to[the editor](https://theconsensus.dev/cdn-cgi/l/email-protection#0e7e6667624e7a666b6d61607d6b607d7b7d206a6b78)\.