CAP in Practice — Fencing Tokens, Sloppy Quorums, BFT & Consistency Models (Deep Dive)

CAP's three letters describe what a system promises in the abstract — they say nothing about what happens once a client's own clock lies to it, once a quorum's write set stops overlapping its read set, once a participant is lying instead of merely crashing, or once a schedule needs to look right to every observer rather than to one object at a time. This page is the layer between the theorem and the incident report: the mechanisms a working engineer reaches for once “we run a CP store” turns out not to be the whole answer. It assumes you already have the CAP components, PACELC, and the quorum/consensus basics (covered elsewhere in this guide) and goes one level deeper into seven places where that basic picture is incomplete.

1. A perfectly consistent lock is still not a safe lock — fencing tokens

Mechanism: a lock service such as ZooKeeper or etcd is itself linearizable — every acquire and release is globally, atomically ordered — but that guarantee is about the lock object, not about what the client holding the lock does next. Linearizability orders the messages exchanged with the lock service; it cannot reach into a paused client and stop it from acting on stale information once the message has already been delivered. A client can believe it holds the lock long after the lock service has quietly given it to someone else.

Here is the failure, traced with real numbers. Client A wants to write to a shared resource (say, a file in cloud storage, or a row in a database) that only one client should touch at a time, so it takes a lease from the lock service first.

Without the token, step t5 would have silently overwritten whatever B wrote at t4 — two clients both believing, correctly per their own information, that they alone hold the lock. The lock service was never wrong; it correctly reports that B now holds the lock. The bug is that A's stale belief and A's actual write are separated by unbounded real time, and nothing in a linearizable register can bound how long a paused client takes to act once it already has an answer in hand.

The fix, and why it has to live at the resource

The fencing token is a monotonically increasing number handed out with every lease grant (71, then 72, then 73, …). The fix is not a smarter lock — it is teaching the resource being protected to remember the highest token it has ever accepted and reject anything lower. That placement is the whole trick: the lock service cannot force a paused thread to stop running, and no amount of strengthening its own consistency guarantee changes that — the only reliable enforcement point is the last hop, where the write actually lands. This is Martin Kleppmann's canonical example, and it generalizes: any time a CP coordination service is granting access to something external to itself (a storage bucket, a device, a payment gateway), that external thing needs to be token-aware, or the lock is advisory only.

This page's companion, Split-Brain, Fencing & Safe Failover, works the same token mechanism in the leader-promotion setting and covers the alternative when the resource can't check a token — STONITH, physically powering off the stale node. The point here is narrower and CAP-specific: CP alone (the lock's own linearizability) is necessary but not sufficient; the fencing token is the piece that closes the gap between “the lock service is correct” and “the system is correct.”

2. Sloppy quorums & hinted handoff — when R+W>N stops meaning what you think

Mechanism: the inequality R+W>N only guarantees a fresh read when both the read set and the write set are drawn from the same fixed list of N replicas (a key's “preference list” or “home” nodes). That is a strict quorum. A sloppy quorum keeps the arithmetic — it still waits for W acks and still queries R replicas — but during a failure it lets those acks come from whichever healthy nodes it can reach, including nodes outside the key's home list. The write still succeeds and durability is preserved, but the guarantee that R+W>N was actually protecting — read set ∩ write set ≠ ∅ — is gone the moment the write set is allowed to drift.

Concretely: key x has home nodes {A,B,C}, N=3, W=2, R=2. A partition makes B and C unreachable from the writer's side, so the coordinator writes to A and to a fallback node D instead, which stores the value tagged with a hint — “this really belongs to C.” Two acks (A, D) satisfy W=2, so the write succeeds. Later, once B and C are reachable again but before D has handed its hint back, a reader queries B and C to satisfy R=2. Neither has ever seen the new value, so the read returns stale data — even though R+W = 4 > N = 3 held the whole time. The write set {A,D} and the read set {B,C} are disjoint; the inequality never promised anything about those two sets, only about sets drawn from {A,B,C}. Hinted handoff is what heals this: D periodically checks whether C has recovered and replays the buffered write once it has, after which reads through the home list are correct again.

Get the per-system attribution right: Amazon's original Dynamo design (and its open-source descendants, Riak) support a sloppy quorum by default — availability during a partition beats a rejected write. Cassandra's consistency levels (e.g. QUORUM) enforce a strict quorum over the natural replicas for the purposes of counting W and R — it does separately support hinted handoff as an auxiliary write-path durability mechanism, but that does not substitute for, or loosen, the consistency-level quorum count. For the full traced walkthrough — including the recovery-storm failure mode when many buffered hints replay onto a just-recovered node at once, and the read-repair / Merkle-tree anti-entropy backstop that makes eventual consistency actually converge — see Failure Under Scale: Hinted Handoff & Sloppy Quorum in this guide; the point here is narrower: R+W>N is a claim about a fixed set of N nodes, and sloppy quorum is exactly the mechanism that breaks that fixedness in exchange for availability.

3. Byzantine faults — when a replica can lie, not just crash

Mechanism: Paxos and Raft assume a crash-fault model — a node either follows the protocol correctly or goes silent; it never sends a well-formed but wrong message to fool its peers. Byzantine fault tolerance drops that assumption: a faulty node may send different answers to different peers, forge messages, or actively try to break the protocol, and the system must still reach the one correct decision.

The node-count arithmetic is the tell in an interview. Crash-tolerant consensus needs 2f+1 nodes to survive f crashes: any two majorities (of size f+1) out of 2f+1 nodes overlap in at least one node, and because a correct-but-possibly-crashed node never lies, that one overlapping node is enough to prevent two conflicting values both being decided. Byzantine-tolerant consensus needs 3f+1 nodes to survive f arbitrary/malicious nodes — a strictly bigger cluster for the same f.

Why 3f+1 and not 2f+1: with n=3f+1 total nodes, a decision requires agreement from a quorum of n−f = 2f+1 nodes (you can only count on the ones that respond correctly; up to f might not). Two such quorums, drawn from n=3f+1, overlap in (2f+1)+(2f+1)−(3f+1) = f+1 nodes. Since at most f nodes are faulty, that overlap of f+1 is guaranteed to contain at least one honest node — and an honest node never endorses two different values, so it becomes the witness that catches an attempt to certify two conflicting decisions. Drop to 2f+1 total nodes under a Byzantine model and the same math gives an overlap of only 1 — and that one overlapping node could itself be a liar, so no contradiction is guaranteed to surface. That extra f nodes of headroom is the entire cost of tolerating malice instead of mere silence.

The judgment call is about trust, not scale: if every replica is a machine you operate and its only failure mode is a crash or a network blip, paying for 3f+1 nodes plus cryptographic signing is pure waste — Raft/Paxos at 2f+1 already gives you the correct answer. Byzantine tolerance earns its cost only when a replica might be run by someone with an incentive to cheat.

4. Client-centric / session consistency — the pragmatic middle ground

Mechanism: instead of promising one global order that every observer in the system agrees on (linearizable), or promising almost nothing (eventual), guarantee a consistent order only to the same client or session. That is a far cheaper promise — no cross-client coordination at all — and it happens to eliminate the two anomalies users actually file bug reports about.

The two implementation families trade off differently. Sticky session routing (a load balancer or proxy pins a session to one replica or the primary) needs no client changes and is simple to reason about, but concentrates load on whichever replica a busy session is pinned to, and a failover that silently reroutes the session breaks the guarantee unless the new replica is verified caught-up first. Client-tracked version/token (the client carries a token recording the highest version it has observed on every request) survives routing changes and load-balancer reshuffles, at the cost of extra request metadata and requiring the store to expose a “serve only once you've reached version V” primitive.

Session consistency is the right default for the large majority of consumer-facing reads — a user's own comments, cart, or profile edits need to feel consistent to that user, but global cross-user ordering is irrelevant to them. Escalate to linearizable only for the small set of operations where a stale or wrong-order read is actually dangerous — a balance check immediately before a transfer, a uniqueness check on account creation.

5. Linearizability vs. serializability vs. strict serializability

Mechanism: linearizability is a claim about real time on a single object — does one instant per operation, respecting the real-time order of calls and returns, explain every read and write on that one register? Serializability is a claim about transactions, possibly touching many objects — does some total order of the transactions exist, such that running them one-at-a-time in that order produces the same result, with no promise that the order matches real time?

Concrete example of serializable-but-not-linearizable: transaction T1 writes account X and commits entirely within the real-time window [0ms,10ms]. Transaction T2, invoked afterward at 20ms, reads account Y — a completely different object that T1 never touched — and commits at 30ms. Because T1 and T2 touch disjoint objects, either serial order (T1-then-T2, or T2-then-T1) is a valid serialization: both produce identical results, since neither transaction's outcome depends on the other. A serializability checker is free to report the order T2-before-T1 — it is a completely legal witness — even though in real wall-clock time T1 had already finished before T2 even started. That is not a bug: serializability never promised to respect real time, only that some safe interleaving existed. The identical reordering on the same object, in the same real-time relationship, would be a linearizability violation — which is exactly why the two guarantees are orthogonal, not one a special case of the other.

Strict serializability is the conjunction: transactions are serializable, and the chosen serial order additionally respects real time (if T1 commits before T2 is invoked, T1 must precede T2 in the order). This is the guarantee Google Spanner targets, paying for it with TrueTime-bounded commit-wait (covered in this guide's PACELC page) — the real-time discipline of linearizability applied across a whole multi-object transaction schedule, not just one register.

6. Verifying linearizability at scale

Mechanism: this guide's CAP Components page hand-checks linearizability on a 3-operation history by eye — asking whether one instant explains both reads is tractable when there are three operations. At production scale, with thousands of concurrent, overlapping operations recorded during a real fault-injected run, you cannot eyeball it, and the general problem — does any permutation of a recorded concurrent history exist that is both a valid sequential execution of the object and consistent with every operation's real-time window — is NP-hard in the number of concurrent operations.

The real technique senior engineers cite is Jepsen-style testing (Kyle Kingsbury): inject real faults — network partitions, clock skew, process pauses, node kills — into a live cluster of the database under test while client workloads hammer it, and record the full history of invocations and responses with real timestamps. That history is then fed to a checker such as Knossos, which searches for a permutation of the operations that (a) is a legal sequential execution given the object's semantics (register, set, queue, …) and (b) respects every operation's real-time call/return window. Because the raw search space is exponential in the number of concurrent operations, practical checkers survive by pruning aggressively using the real-time constraints, analyzing one key/register's history at a time to keep the concurrent-operation count small, and — for the broader problem of checking multi-object serializability rather than single-object linearizability — using dependency-cycle detection over the transaction graph instead of brute-force permutation search (the approach Jepsen's newer Elle checker takes).

The contrast with the hand-check earlier in this guide is the point: that manual trace is literally the same question — does one instant of the write's effect explain every read — asked and answered by inspection because there were only three operations. Jepsen/Knossos-style checking automates exactly that reasoning across a real, fault-injected, thousands-of-operations run. That automated, adversarial check is the only credible evidence that a store's advertised consistency model actually holds under failure; a vendor's claim without one is marketing, not proof.

7. When to prefer Multi-Paxos/EPaxos over Raft

Mechanism: Raft buys understandability by funneling every decision through one elected leader — every write is proposed by the leader, replicated to followers, and only the leader may order operations. EPaxos removes the leader entirely: any replica can propose a command directly to the replicas nearest it and commit it without ever routing through a single node.

Raft's single leader creates two costs that scale with geography and load. It is a throughput ceiling: every write from every client, anywhere, must first reach the one leader before it is even proposed, so the leader's own CPU and network are the whole cluster's write ceiling, and a client far from the leader pays that round trip on every single write regardless of which replica is physically closest to it. It also creates a failover gap: when the leader dies, the cluster cannot accept writes until a new election completes — a real, bounded but non-zero availability dip on every leader failure.

EPaxos's mechanism: on receiving a command, a replica computes which other outstanding commands it might conflict with (based on the keys/effects touched) and proposes the command together with its perceived dependencies to a fast quorum near it. If enough replicas agree on the identical dependency set — meaning no one detected interference — the command commits in a single round trip to the nearest quorum (the fast path). If replicas disagree about dependencies (a genuine concurrent conflict on the same keys), it falls back to an extra round to agree on the ordering (the slow path), at a cost similar to classic Paxos.

The trade-off: EPaxos removes the leader bottleneck and the failover gap, and lets every replica commit non-conflicting commands in one round trip to its own nearest quorum — a large tail-latency win specifically for geo-distributed deployments, where a client in one region no longer pays a round trip to a leader sitting in another. The cost is a materially harder protocol: correctness now depends on a dependency-graph conflict-detection and execution-ordering scheme that is genuinely more complex to implement and reason about than Raft's single log, and workloads with real contention on the same keys fall back to the slower path anyway — so the win is concentrated in low-contention, multi-region traffic, not universal. (Multi-Paxos, a stable-leader optimization of classic Paxos used historically at Google before Raft existed, sits close to Raft structurally — the real axis to reason about is leader-based, whether Raft or Multi-Paxos, versus leaderless, EPaxos and its descendants — not Paxos-the-paper versus Raft-the-paper.)

Choose Raft/Multi-Paxos by default: it is simpler, far more widely implemented and operationally battle-tested (etcd, Consul, CockroachDB's per-range Raft, Kafka KRaft), and a natural fit when the deployment is single-region or has one clearly-nearest leader. Reach for an EPaxos-family design only when the deployment is genuinely multi-region, cross-region write latency to a single leader is the dominant cost you are trying to cut, and the workload's key contention is low enough that the fast path actually dominates — and budget real engineering time for the harder correctness story; EPaxos-family protocols remain far less battle-tested in production than Raft.

Pitfalls

• Trusting a CP lock service to protect an external resource, with no token check at the resource. Without enforcement at the last hop, the lock is advisory — a paused-then-resumed client will write anyway.
• Assuming R+W>N always means consistency. True only under a strict quorum. The moment sloppy quorum / hinted handoff engages during a failure, the guarantee is provisional until read-repair or anti-entropy reconciles it.
• Applying 2f+1 crash-fault math in an adversarial or multi-organization setting. A node that can lie, not just crash, breaks the overlap argument crash-tolerant protocols rely on — you need 3f+1 and a real BFT protocol, not a bigger Raft cluster.
• Treating session consistency as “basically strong consistency.” It only protects the guarantees for the same client/session; a different client can simultaneously observe an entirely different, older view of the same data.
• Confusing serializable with linearizable. They are orthogonal guarantees (multi-object/no-real-time vs. single-object/real-time) — a serializable database is not automatically strongly consistent for cross-replica reads, and claiming so is a common wrong answer in interviews.
• Trusting a vendor's consistency claim with no Jepsen-style evidence. The only credible proof is a fault-injected run with an algorithmic linearizability/serializability check against the recorded history — not a whitepaper claim.
• Reaching for EPaxos/leaderless designs on a high-contention workload. If most commands touch the same hot keys, you pay the added implementation complexity and still fall back to the slow path most of the time — Raft would have been simpler and just as fast.

Judgment layer — when to use each, and the named alternative

Fencing tokens — use whenever a CP coordination service (ZooKeeper, etcd, Consul) grants access to a resource that has no other way to detect a stale holder. Named alternative: STONITH (power off or isolate the old node) — needs no cooperation from the resource, but requires a reliable out-of-band kill channel and a tiebreaker to avoid mutual kills. Prefer a fencing token when the resource can cheaply check one; fall back to STONITH when it can't.

Sloppy quorum + hinted handoff — use for high write-availability, staleness-tolerant data (carts, feeds, telemetry); never for money, inventory decrement, or uniqueness. Named alternative: strict quorum — a genuine R+W>N guarantee, at the cost of refusing writes/reads it cannot satisfy from the home replicas during a failure.

Byzantine fault tolerance — use only when replicas are operated by mutually distrusting parties or the environment is adversarial (permissionless or cross-org ledgers). Named alternative: crash-fault consensus (Paxos/Raft at 2f+1) — strictly cheaper, and the correct choice inside any single trusted operator's datacenter where the only failure mode is a crash.

Session consistency — the right default posture for consumer-facing reads of a user's own data. Named alternative: full linearizability — reserve it for the specific operations where a stale or wrong-order read is actually unsafe, not as the default for everything.

Strict serializability — use when a workload genuinely needs both transaction-level correctness and real-time ordering across it (multi-account ledgers, global uniqueness with ordering guarantees), and can afford the coordination cost. Named alternative: plain serializability — much cheaper, and sufficient whenever the system's chosen transaction order doesn't need to match wall-clock time, only that some safe order existed.

Raft/Multi-Paxos vs. EPaxos — default to Raft/Multi-Paxos for its simplicity and operational maturity. Reach for an EPaxos-family leaderless protocol specifically for genuinely multi-region deployments with low key contention, where shaving cross-region tail latency outweighs the real cost of a harder-to-implement, harder-to-debug conflict-resolution protocol.

Scope check — none of the above makes CAP the only daily trade-off. Partitions are rare; the latency-vs-consistency dial (PACELC's else-clause) is paid on every request, so it usually shapes more of the design than the partition case does. Reach for this page's machinery when a partition, a pause, or a liar is actually in your failure model.

Takeaways

• A linearizable lock is necessary but not sufficient — only a fencing token enforced at the resource closes the gap between “the client believes it holds the lock” and “the client actually still holds it.”
• R+W>N is a guarantee about a fixed set of N replicas; a sloppy quorum breaks that fixed set for availability, so the identical arithmetic no longer promises a fresh read until hinted handoff and anti-entropy reconcile it.
• “Linearizable or eventual” isn't the only axis in play — trust model (crash-tolerant 2f+1 vs. Byzantine-tolerant 3f+1) and observer scope (global order vs. per-session order) are separate dials real systems tune independently.
• Linearizability, serializability, and strict serializability are three distinct guarantees (single-object real-time / multi-object order / both) — and the only credible evidence a real system provides one is an automated, fault-injected check (Jepsen/Knossos-style), never a vendor's say-so.
• Keep three properties separate: durability of a write, linearizability of reads, and exclusion of stale leaders — quorum arithmetic gives you the first, not the other two.

Sources: M. Kleppmann, “How to do distributed locking” (2016) and Designing Data-Intensive Applications; DeCandia et al., “Dynamo: Amazon's Highly Available Key-value Store” (SOSP 2007); Castro & Liskov, “Practical Byzantine Fault Tolerance” (OSDI 1999); Lamport, “The Part-Time Parliament” and Ongaro & Ousterhout, “In Search of an Understandable Consensus Algorithm” (Raft, 2014); Moraru, Andersen & Kaminsky, “There Is More Consensus in Egalitarian Parliaments” (EPaxos, SOSP 2013); Herlihy & Wing, “Linearizability: A Correctness Condition for Concurrent Objects” (1990); Terry et al., “Session Guarantees for Weakly Consistent Replicated Data” (1994); Corbett et al., “Spanner: Google's Globally-Distributed Database” (OSDI 2012); Kyle Kingsbury / Jepsen.io reports and the Knossos linearizability checker. Re-authored/Deepened for this guide.