Tunable Consistency — R + W > N

In a leader-based database, the consistency question is answered for you. The primary decides order; followers ship along. You choose sync versus async replication and that is about it. In a leaderless Dynamo-style system (ch.75) there is no primary to decide, so the question returns: when my client receives "write OK", what does a later "read" actually promise?

The answer is not a single number. It is a knob. You turn it at the call site — per query in Cassandra, per operation in Riak — and you pay in latency and availability for the position you pick. Cassandra's consistency level is the single most important configuration choice in leaderless systems, and understanding it reduces to understanding one inequality.

The setup — N, R, W, and a key

A key cart:priya-42 is hashed onto the ring; consistent hashing (ch.76) produces a deterministic preference list of N nodes responsible for it. Every node in the cluster agrees on this list because every node runs the same hashing function against the same gossip-maintained membership.

N is fixed for a keyspace — declared at CREATE KEYSPACE time. R and W are properties of the request, not the data. Each put carries its own W; each get carries its own R.

The coordinator — any node the client talks to — handles fanout.

• Write path. Coordinator sends the new value to all N replicas in parallel. Once W have acked, it returns success. The other N−W acks may still be outstanding.
• Read path. Coordinator sends to R replicas (sometimes all N for speculative reads). Each responds with value plus metadata (timestamp or vector clock). The coordinator picks the newest by causal order and returns it.

Why the coordinator does not wait for all N on a write: tail latency of the slowest replica is usually far worse than the median. If p50 ack is 2 ms and p99 is 50 ms, waiting for all N gives p50 of 50 ms because you take the max. Waiting for the fastest W lets you ignore the slowest N−W. Quorum acks are a latency-hedging strategy, not only a consistency mechanism.

Why R + W > N gives strong consistency

The proof is one line of combinatorics, but it pays to see it carefully.

Claim. If a write to key K has been acknowledged — meaning W of the N preference-list replicas have durably stored the new value — and if a subsequent read queries R of those N replicas and returns the newest response it sees, then the read sees the new value whenever R + W > N.

Proof sketch. After the write acks, W specific replicas hold the new value; call them the fresh set F, with |F| = W. The remaining N − W replicas still hold the old value (or nothing, if the key is brand new); call them the stale set S, with |S| = N − W.

The read queries R replicas from the same preference list. Call that subset Q. Suppose, for contradiction, that Q contains only stale replicas — that is, Q ⊆ S. Then |Q| ≤ |S|, i.e. R ≤ N − W, i.e. R + W ≤ N. Contrapositive: if R + W > N, then Q cannot fit entirely inside S; at least one member of Q is in F. That member holds the new value and returns it. The coordinator picks the newest response among the R it received, and since at least one of them is fresh, the newest is at least as new as the committed write. Done.

This is the classical Gifford quorum argument (Gifford 1979, SOSP). The subtlety the proof sweeps under the rug is "newest" — the coordinator needs a way to compare two responses and say which is newer. In practice that is a timestamp (Cassandra), a vector clock (Riak, original Dynamo), or a dotted version vector. The quorum argument guarantees only that a newer-or-equal value is among the R responses; the comparison step actually surfaces it.

Why R + W ≤ N leaks stale reads

The contrapositive is worth sitting with. If R + W ≤ N, then there exists a pair of subsets (one of size W, one of size R) that are disjoint — specifically, you can write to the first W replicas on the preference list and then read from the last R, and those two sets do not touch. In a real cluster, which W happened to ack first depends on network timing; which R the coordinator happens to query depends on load-balancing heuristics. Over millions of requests, the disjoint case will occur.

When it does, the read returns only stale values. The coordinator cannot tell that a newer value exists elsewhere — it only sees the R responses it received. It returns the newest of those, which happens to be old.

This is not catastrophic. The next round of background repair — read repair on a subsequent query (ch.80), or anti-entropy via Merkle trees (ch.81), or a hinted handoff delivery from a coordinator that remembered the write (ch.79) — will eventually propagate the new value to all N replicas. At that point reads converge. This is the meaning of eventual consistency: stale now, correct later.

Whether that window matters depends on the workload. For an analytics dashboard showing "approximately 1.2 M requests in the last hour", a few seconds of staleness is invisible. For a shopping-cart checkout, staleness means the user saw an empty cart, pressed "place order", and bought nothing. R + W > N buys you the guarantee that your read reflects the most recent committed write; you pay for it in latency.

Tuning R and W — the latency axis

Once you accept R + W > N as the right line, the remaining degree of freedom is where on it. The trade-off shape is asymmetric between reads and writes.

Higher W. The coordinator waits for more replicas to ack. With N=3, moving from W=1 to W=2 waits for the second-fastest of three; p50 goes up 1–3 ms. Moving to W=3 waits for the slowest, whose p99 is often 10x the median — tail latency balloons. Durability goes up accordingly.

Higher R. Similar shape, usually smaller because reads avoid fsync. Merge work goes up: with R=1 there is nothing to compare; with R=3 the coordinator compares timestamps or vector clocks, picks a winner, and enqueues a read-repair write-back to stale replicas.

Common configurations with N=3:

• W=2, R=2 (QUORUM/QUORUM). Balanced. R + W = 4 > 3. Tolerates one replica down on either path. The default for correctness-sensitive Cassandra deployments.
• W=3, R=1 (ALL/ONE). Writes pay full tail latency; reads are single-node fast. Good when writes are rare and reads are hot: reference data, configuration, pre-computed recommendations.
• W=1, R=3 (ONE/ALL). Writes feel instant; reads tour every replica and merge. Good for bursty-write, accuracy-sensitive reads — audit logs, event streams.
• W=1, R=1 (ONE/ONE). R + W = 2 ≤ 3 — stale reads possible until repair. Good when staleness is tolerable: metrics, telemetry, caches.

The first three satisfy R + W > N; only the last does not.

Python implementation — the quorum read/write

The core loop is short enough to fit in one screen.

# quorum_kv.py
import time
from dataclasses import dataclass

@dataclass
class Versioned:
    value: object
    timestamp: float

class QuorumFailed(Exception): pass

class QuorumKV:
    def __init__(self, ring, N=3, W=2, R=2):
        self.ring, self.N, self.W, self.R = ring, N, W, R

    def put(self, key, value):
        replicas = self.ring.preference_list(key, self.N)
        ts = time.time()
        acks = 0
        for r in replicas:
            if r.write(key, Versioned(value, ts), timeout=1.0):
                acks += 1
            if acks >= self.W:
                return True
        raise QuorumFailed(f"only {acks}/{self.W} acks")

    def get(self, key):
        replicas = self.ring.preference_list(key, self.N)
        responses = []
        for r in replicas:
            v = r.read(key, timeout=1.0)
            if v is not None:
                responses.append(v)
            if len(responses) >= self.R:
                break
        if not responses:
            raise QuorumFailed("no replicas responded")
        return max(responses, key=lambda v: v.timestamp)

Why the loop breaks early on acks >= W and len(responses) >= R: the whole point of the quorum is that you do not wait for the remaining N − W replicas. In production the writes to those stragglers are fired in parallel (the sequential loop here is pedagogic), but the coordinator returns to the client the moment the quorum is reached. Waiting for all N would cost you p99 latency and defeat the purpose.

A production implementation adds parallel fanout (gevent, asyncio, or thread-pool), retries, read-repair write-backs when responses disagree, and hinted-handoff bookkeeping — but the control flow stays the same shape.

Availability — the other axis

The same knob controls availability under replica failure, and the direction is the opposite of what you might hope. With N=3:

• W=2. One replica down and writes still succeed. Two down and writes halt. Tolerates one failure.
• W=3. Any replica failure halts writes immediately. Zero failures tolerated.
• W=1. Any two replicas can be down and writes still succeed. Two failures tolerated, at the cost of durability — the write is "committed" before it has spread.

Symmetric for R. A cluster running W=3, R=3 cannot tolerate a single failure anywhere on either path. The double-edge: bigger W means stronger durability and, combined with R+W>N, stronger consistency — but worse availability under failure.

Per-query tunability

Cassandra made a specific bet: expose the consistency knob per query, not per table or per cluster. One clause on every statement:

SELECT items FROM carts WHERE id = ? USING CONSISTENCY QUORUM;
INSERT INTO events(id, body) VALUES(?, ?) USING CONSISTENCY ONE;

ONE means R=1 or W=1. QUORUM is ⌊N/2⌋+1. ALL is N. There are also LOCAL_QUORUM (majority within one datacentre), EACH_QUORUM (majority within each), and ANY (accept a hinted-handoff stub).

The benefit is that one table serves both workload shapes. A Cassandra cluster storing user-feed rows can accept writes at QUORUM (never lose a post) and serve them at ONE (feed is a cache; stale is fine). One schema, two consistency levels, no cluster split.

Why per-query rather than per-table: the relevant property is not the data's "importance" but the specific call site's tolerance for staleness and latency. The same row might be read by a billing job that wants QUORUM and by a dashboard happy with ONE. Making the knob per-query lets the application choose at the line of code where the trade-off exists.

Per-key vs per-operation

• N is per-keyspace (replication factor). Fixed at schema time. Changing it triggers a rebalance.
• R and W are per-operation. Every get and put specifies its own — no schema change, no rebalance, just edit the call site.

Riak uses n_val, r, w in the same way. DynamoDB exposes a stripped-down version: ConsistentRead=true is roughly R=N; writes are always quorum. Structural shape identical.

The CAP / PACELC trade-offs

R + W > N places the system on the CP side of CAP during a partition: if enough replicas are unreachable that you cannot get W acks or R responses, the request fails. R + W ≤ N sits on the AP side: writes continue to whichever replicas the coordinator can reach, and background repair reconciles later.

The strength of Dynamo-style systems is that this choice is per-request. In the same Cassandra cluster during the same partition, a SELECT ... AT QUORUM might fail while a SELECT ... AT ONE on the next line succeeds. PACELC makes the steady-state explicit: even without a partition, you trade latency for consistency on every request.

Common confusions

• "R + W > N gives linearisability." No. The quorum argument gives you read-your-writes plus monotonic reads in a sequential client. It does not give linearisability across concurrent writes: two clients writing the same key at the same time can both hit W acks at different replicas, and the read returns one or the other (or both as siblings in vector-clock systems). True linearisability under concurrent writes needs consensus — Paxos or Raft — which Cassandra provides via lightweight transactions at a 4-round-trip cost.
• "Bigger W is always safer." Once R + W > N holds, additional W buys nothing for consistency — it only adds latency and reduces failure tolerance. W=2, R=2 is strictly better than W=3, R=2 for most workloads because the former survives a replica failure and the latter does not.
• "R=1 is always fastest." Per request, yes. System-wide, maybe not: R=1 reads surface stale values that trigger read-repair round-trips, force application retries on inconsistent views, or generate extra anti-entropy traffic. Measure end-to-end.
• "Tunable means you must tune every query." Most applications pick one default (usually QUORUM/QUORUM) and override only on specific performance-critical paths.
• "Eventual consistency is always cheaper." Cheap in latency, expensive in application complexity. Code that handles "this read might be slightly stale" is harder to test and a frequent source of bugs.

Going deeper

The quorum intersection theorem

Gifford's 1979 SOSP paper Weighted Voting for Replicated Data is the origin. Each replica holds a vote weight v_i; a read requires weight Qr and a write requires weight Qw. The intersection property is Qr + Qw > ΣV. Dynamo's R + W > N is the unit-weight special case. Gifford also discusses weighted variants — a datacentre's master copy might have weight 3 while read-only cache replicas have weight 1 — which is how ZooKeeper's "observers" and etcd's "learners" relate to their voting counterparts.

Probabilistic bounded staleness

Bailis et al. (Berkeley 2012, Probabilistically Bounded Staleness, VLDB) showed that even when R + W ≤ N, the probability of a stale read decays quickly with wall-clock time since the write. At R=W=1 with N=3, the staleness probability drops from ~33 % immediately to under 1 % after 100 ms in typical deployments. Cassandra's PBS metrics expose this directly; the result justifies aggressive use of ONE/ONE for latency-sensitive workloads where millisecond staleness is tolerable.

Lightweight transactions — when quorum is not enough

Cassandra added INSERT ... IF NOT EXISTS and UPDATE ... IF col = x in 2013 for cases where quorum is insufficient — specifically, serialisability across concurrent writers. The implementation uses Paxos at 4 round-trips per LWT versus 1 for a normal quorum write. LWTs are reserved for operations that genuinely need atomicity: unique-username registration, distributed locking, leader election within a keyspace.

Where this leads next

R + W > N is a sufficient condition under the assumption that the coordinator actually reaches W nodes on the preference list. When failures push past that — a coordinator cannot get W acks from the preference-list replicas — Dynamo-style systems have a choice: fail the write (strict quorum, CP behaviour) or accept acks from substitute nodes off the preference list (sloppy quorum, AP behaviour). The write is later shipped to the correct replicas by hinted handoff. Chapter 79 covers both. Chapter 80 covers read repair, the mechanism that catches the staleness introduced by R + W ≤ N or by sloppy quorums. Chapter 81 covers anti-entropy via Merkle trees for the keys that reads never touch. Each of these is the machinery that makes R + W > N a usable model in a real network rather than a textbook inequality.

References

1. Gifford, Weighted Voting for Replicated Data, SOSP 1979 — the original formalisation of quorum intersection. Introduces the Qr + Qw > V inequality in its weighted form; Dynamo's R + W > N is the unit-weight special case.
2. DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007 — the paper that brought N, R, W into the distributed-systems vernacular. Section 4.5 is the specific treatment of quorum parameters and sloppy quorums.
3. Apache Cassandra, Consistency Levels Documentation — the canonical reference for Cassandra's per-query CONSISTENCY clause, including QUORUM, LOCAL_QUORUM, EACH_QUORUM, and the less-common ANY and SERIAL levels for lightweight transactions.
4. Basho, Riak KV — Replication Properties — Riak's per-bucket and per-operation n_val, r, w, pr, pw, and dw parameters. Notable for separating "any-node quorum" from "primary-node quorum" to distinguish sloppy from strict.
5. Kleppmann, Designing Data-Intensive Applications, Chapter 5 — Replication, O'Reilly 2017 — the clearest pedagogical treatment of leaderless replication, the w + r > n inequality, and the limitations of quorum consistency relative to linearisability. Worked examples with multiple clients and concurrent writes.
6. Bailis et al., Probabilistically Bounded Staleness for Practical Partial Quorums, VLDB 2012 — the quantitative treatment of R + W ≤ N staleness. Derives closed-form bounds for staleness probability as a function of time since write, calibrated against real Cassandra deployments. Motivates aggressive use of eventual-consistency configurations where application tolerance is known.