Every distributed database vendor claims "strong consistency," and they all mean something different. Linearizability (Herlihy & Wing 1990), serializability, sequential consistency (Lamport 1979), snapshot isolation, causal consistency, and eventual consistency — the formal hierarchy that makes "strong" a precise word. Understanding which level you need (and which level your DB actually provides) is the specific Expert-tier competence that turns "we lost some writes" postmortems into "we chose the right consistency for our workload from the start."
Every distributed database\'s docs page claims "strong consistency." MongoDB says it. Cassandra says it (with caveats). CockroachDB says it. Amazon DynamoDB says it. Google Spanner says it. They all mean different things. MongoDB provides linearizable reads when configured with readConcern: linearizable, but snapshot isolation by default. Cassandra provides "tunable consistency" via quorum settings but doesn\'t provide linearizability at any level. DynamoDB provides "strongly consistent reads" which are linearizable single-object reads, but transactions have their own model. CockroachDB provides serializable transactions with a specific mix of linearizable and serializable guarantees. Spanner provides external consistency via TrueTime — the strongest of all. Each of these is called "strong consistency" in marketing copy, but they give you completely different guarantees. This module introduces the formal vocabulary that lets you tell them apart, understand what your DB actually provides, and pick the right level for your workload.
The specific misunderstanding that generates most consistency bugs is treating "strong consistency" as a binary property (either you have it or you don\'t) rather than as a formal hierarchy where each level has specific semantics. Consider "we need strong consistency for our banking system." What does this actually require? Linearizable single-account operations — so that when you check your balance twice in a row, you don\'t see the balance decrease then increase (linearizability). Serializable multi-account transactions — so that a transfer between two accounts either fully commits or fully aborts, and no other transaction sees the intermediate state (serializability). External consistency for regulatory audit trails — so that if the auditor reads at time t and a transaction was committed before t in real time, the audit read sees the committed state (strict serializability). Depending on which of these you actually need, you might use PostgreSQL with serializable isolation (covers first two), Google Spanner (covers all three), or CockroachDB with serializable transactions (covers first two, causal for the third). Each choice has different cost and different operational profile. Saying "strong consistency" without specifying which formal level obscures this decision.
Each earlier attempt over-optimizes for one dimension. Always linearizable is safe but too expensive. Always eventual is cheap but breaks correctness for many workloads. Trust vendor claims ignores the formal-vs-marketing gap that Jepsen has repeatedly exposed. The composite pattern: identify the workload\'s specific correctness requirements, pick the formal level that satisfies them at minimum cost. Money needs linearizable + serializable; social ordering needs causal; convergent operations survive eventual. Modern databases increasingly support tunable consistency exactly to enable this per-workload choice. §02 defines linearizability formally; §03 walks through the rest of the ladder; §04 shows how each level fits (or fails) different workloads.
The historical arc of consistency models is a specific case where the theoretical framework was worked out incrementally over four decades and continues to be refined. 1979: Lamport publishes "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs." Introduces sequential consistency — operations appear in some serial order consistent with each process\'s program order. This is weaker than linearizability (no real-time requirement) but strong enough to reason about shared-memory algorithms. Foundational for concurrent programming theory. 1990: Herlihy and Wing publish "Linearizability: A Correctness Condition for Concurrent Objects." Introduces linearizability — every operation appears to happen atomically at a single instant between its invocation and response, respecting real-time order between non-overlapping operations. Strongest single-object consistency. Basis for reasoning about concurrent data structures, distributed atomic registers, and any system claiming "strong" single-key consistency. Early 1990s: Database serializability is well-established (Bernstein & Newcomer, various). Different from linearizability — serializability is about multi-object transactions, doesn\'t require real-time ordering between transactions. Every SQL database\'s "serializable" isolation level implements this. 2000: Brewer conjectures CAP. "You can\'t have consistency, availability, and partition-tolerance simultaneously." Formalized by Gilbert & Lynch 2002. This popularizes the tradeoff conversation for distributed systems. 2007: Amazon Dynamo paper. Introduces eventual consistency at industrial scale — many replicas, tunable quorum, application-level conflict resolution. Also introduces vector clocks for causality tracking. 2012: Abadi\'s PACELC. Extends CAP: even when there\'s no partition (Else), you still have a tradeoff between Latency and Consistency. This is what actually shapes system design most of the time — partitions are rare, latency-consistency tradeoffs are constant. 2012: Google Spanner paper. Introduces external consistency via TrueTime. First production system providing strict serializability at global scale. 2013+: Jepsen (Kyle Kingsbury). Systematic formal testing of database consistency claims. Repeatedly exposes gaps between vendor marketing and formal guarantees. Now the de facto verification standard — any database serious about consistency claims runs Jepsen. 2014+: CRDTs (Shapiro et al.) formalize convergent replicated data types — eventual consistency with mathematically-guaranteed convergence for specific data structures. Enables provably-correct eventual consistency for shopping carts, counters, sets, sequences. 2020+: Consistency models are commodity vocabulary in distributed systems. Every senior architect understands the formal ladder; the specific level a system provides is a first-class architectural concern. Understanding this arc explains why "we need strong consistency" is not a decision but the start of a decision.
Linearizability (Herlihy & Wing 1990) is the strongest single-object consistency model. The formal definition is deceptively simple but precisely constraining: each operation appears to happen atomically at some single instant between its invocation (call) and its response (return), and the order of non-overlapping operations respects real time. This means: (a) you can pick a "linearization point" for each operation somewhere in its execution interval; (b) if the linearization points are laid out in order, the sequence must be a valid execution of the object; (c) if operation A completed before operation B started (in real wall-clock time), then A\'s linearization point comes before B\'s. Understanding exactly what this definition rules in and rules out is Expert-tier competence about what "linearizable" actually means when a vendor claims it.
write(1) → write(2) → read()=2. This is what the definition requires. If C had returned 1 instead of 2, linearizability would be violated only if we couldn\'t find any valid linearization — since A and B overlap, both orders are permitted, so returning 1 is also legal.Each operation appears to happen at a single instant between its call and its return. This is the atomicity part — the operation isn\'t partial or interruptible from the perspective of other operations. In implementation terms: the moment your write hits the leader\'s in-memory state after majority-acknowledge is typically the linearization point.
If operation A completes (returns to its caller) before operation B starts (is called), then A\'s linearization point comes before B\'s. This is what "linearizability" adds over sequential consistency: linearizations respect real-time order of non-overlapping operations. The specific cost of this: every operation must complete before the next can start in real time.
If A and B overlap in real time (their intervals intersect), linearization can order them either way — as long as the resulting sequence is a valid execution. This is why linearizability is a local property: implementations can choose orderings freely within overlap windows without violating the model.
Linearizability is compositional: if each individual object is linearizable, the entire system is linearizable when considered as one object. This is a specific advantage over serializability (which is NOT compositional) and is why linearizability is preferred for reasoning about concurrent data structures — you can reason about each object independently.
Every write requires majority quorum coordination before returning to the client. Every read requires either fresh coordination (worst case) or a proof that the leader\'s state is current (best case). Cost floor: one network round-trip per operation. Cross-region linearizability: 100-300ms per op. This is why linearizability is expensive.
etcd, ZooKeeper, and CockroachDB provide linearizable single-key operations. Spanner provides stronger (strict serializable) via TrueTime. DynamoDB provides linearizable "strongly consistent reads" as an option. MongoDB provides linearizable reads with readConcern: linearizable. In all cases, linearizability requires consensus (§ M.47/M.48) at the protocol level.
The real-time constraint (ii) is what specifically distinguishes linearizability from all weaker models. Sequential consistency requires that operations appear in some order matching each process\'s program order — but that order can violate real time. Two clients from different processes might see different real-time-ordered operations execute in different orders under sequential consistency. Linearizability forbids this: if I finish a write and then tell my colleague about it via out-of-band communication (Slack message, phone call), and my colleague immediately reads, they must see my write. This is called the "hallway phone problem" — sequential consistency allows the colleague to see stale data (their local replica hasn\'t caught up); linearizability forbids it. The engineering cost of this: linearizability requires that reads pay coordination cost too, not just writes. Systems like Spanner (via TrueTime) and CockroachDB (via HLC + consensus) engineer around this to minimize the cost, but the fundamental floor is one network round-trip per linearizable operation.
The compositionality property (iv) is a specific and important distinction from other consistency models. If I have two linearizable objects (say, two separate keys in a linearizable K-V store), and I do operations on each, the composite behavior is still linearizable — I can reason about them independently. This is not true for serializability: two serializable databases connected by transactions don\'t compose to a serializable system (each database serializes internally, but cross-database transactions can produce anomalies). It\'s not true for eventual consistency: composing two eventually-consistent stores can produce complex divergence patterns that are hard to analyze. Compositionality is what makes linearizability the "gold standard" for reasoning about distributed algorithms — you can decompose a system into linearizable objects, reason about each in isolation, and the composition is well-defined. This is why textbooks and academic papers treat linearizability as the reference model even though real systems often provide weaker levels for cost reasons.
The engineering implementation of linearizability (vi) requires consensus — you cannot achieve linearizability without something like Paxos or Raft (§ M.47) coordinating operations. The pattern: (a) operations go to a leader elected via consensus; (b) leader assigns each operation a sequence number and replicates to a majority quorum via consensus; (c) leader acknowledges the client only after the operation is committed to the majority quorum; (d) reads either go through the leader (leader ensures its state is fresh via a "read lease" or heartbeat protocol) or use quorum reads to verify freshness. Each step has a specific cost. Modern optimizations: lease-based reads (leader has a time-bounded lease during which it can serve reads without further coordination), quorum reads (read from a majority, take the value with the highest timestamp), TrueTime waits (Spanner waits out clock uncertainty at commit for external consistency). Understanding these optimizations is what turns "linearizability is expensive" into "linearizability costs specifically one round-trip in most cases, plus commit-wait for external consistency." Real numbers matter for architecture: a single-region etcd cluster does linearizable operations in ~5-10ms; Spanner cross-region external-consistent transactions take ~50-150ms including commit-wait.
Below linearizability sits a specific hierarchy of consistency models, each dropping a particular constraint to gain cost efficiency. Understanding what each level provides (and specifically, what it stops providing compared to the level above) is what makes "we\'ll use snapshot isolation for this workload" a considered decision rather than a default choice. This section walks down the ladder — serializability, snapshot isolation, sequential consistency, causal consistency, eventual consistency — enumerating what each level guarantees and which real systems provide it.
The most common conflation. Serializability is about multi-object transactions equivalent to some serial order; linearizability is about single-object atomic ops respecting real-time. A database can be serializable but not linearizable (transactions can commit in an order that doesn\'t match real time). Real example: PostgreSQL SERIALIZABLE isolation is not linearizable across regions.
Most SQL databases default to snapshot isolation, not serializable. Susceptible to write skew: two transactions read overlapping sets of rows, then each writes based on what the other read. Classic example: two doctors both on-call check "at least one other doctor is on-call" (true), then both go off-call — invariant violated. Serializable would prevent this; SI wouldn\'t.
Lamport\'s sequential consistency (1979): operations appear in some order consistent with each process\'s program order. Doesn\'t require real-time ordering. Two processes can observe operations in orders that respect their own program orders but don\'t match wall-clock time. This is what CPU memory models (x86, ARM) actually provide — sequential consistency, not linearizability.
M.49\'s happens-before relation, applied as a consistency model. If a → b, all replicas see a before b. Concurrent ops (not related by happens-before) can be seen in different orders at different replicas. Sufficient for many use cases: social media threads, collaborative editing. Requires vector clocks or similar causality tracking. COPS and Eiger are the reference implementations.
Replicas converge if updates stop. No ordering guarantees. Applications must handle concurrent conflicting writes. Suitable for genuinely commutative operations (add to cart, upvote counters) where any convergent merge produces correct results. CRDTs formalize this — data types with mathematically-guaranteed convergence. Cassandra, Dynamo, Riak in default modes.
CAP (Brewer, Gilbert & Lynch): during a partition, choose consistency or availability. PACELC (Abadi 2012): even without partition, choose latency or consistency. PACELC is what actually shapes systems most of the time — partitions are rare; latency-vs-consistency is a constant tradeoff. Spanner (CP + PC), Cassandra (AP + PA), DynamoDB (CP + PA by default).
The serializability vs linearizability confusion (i) is one of the most common and expensive misunderstandings in distributed systems architecture. Serializability comes from database theory (Bernstein & Newcomer et al.) and is about transactions — a schedule of transactions is serializable if it\'s equivalent to some serial (one-at-a-time) execution of those transactions. Nothing in this definition requires real-time ordering. Two transactions T1 and T2 can execute concurrently, and the serializable execution might treat T2 as if it happened before T1 (from a serial-order perspective) even though T1 committed first in wall-clock time. This is fine for many database workloads — as long as the final state is achievable by some serial ordering, the invariants are preserved. Linearizability adds the real-time constraint: if T1 completes before T2 starts, then T1 must come before T2 in the equivalent serial order. Strict serializability combines both — multi-object serializable transactions with real-time ordering. Spanner provides strict serializability; PostgreSQL SERIALIZABLE provides serializability but not linearizability across sessions; CockroachDB provides serializability with additional causal guarantees. Understanding this distinction is what turns "our database is serializable so we\'re fine" into "our database is serializable but if we need real-time ordering across sessions we need to use CockroachDB\'s AS OF SYSTEM TIME with special semantics."
The snapshot isolation write-skew anomaly (ii) is worth understanding concretely because it\'s the specific anomaly that breaks most "we thought SI was strong enough" designs. Consider a hospital where at least one doctor must be on-call at all times. The system enforces this via a check: SELECT COUNT(*) FROM doctors WHERE on_call = true. If count > 1, transactions can remove a doctor from on-call. Under snapshot isolation, two doctors (Alice and Bob) both start transactions simultaneously. Alice reads: count = 2 (herself and Bob on-call). Bob reads: count = 2 (himself and Alice on-call). Both see "other doctor is still on-call, safe to go off-call." Both UPDATE their own row to on_call = false. Both commit successfully (no write-write conflict — they wrote different rows). Result: zero doctors on-call, invariant violated. Serializability would prevent this because in any serial ordering, one of the two transactions would see the other already off-call and be forbidden from proceeding. Snapshot isolation allows it because each transaction sees a consistent snapshot but the writes don\'t directly conflict. This is why PostgreSQL\'s SERIALIZABLE (not READ COMMITTED, not REPEATABLE READ) is the correct choice for correctness-critical workloads — it uses SSI (Serializable Snapshot Isolation, Cahill et al. 2008) to detect and abort write-skew scenarios.
The PACELC extension of CAP (vi) is the specific framework that captures what actually shapes distributed database design. Brewer\'s CAP theorem states: during a partition (P), a distributed system must choose between consistency (C) and availability (A). This is true and important, but partitions are rare in practice — well-run production systems see partitions maybe a few times per year. PACELC (Abadi 2012) extends this: even when there is no partition (E for "else"), the system must trade off latency (L) against consistency (C). Strong consistency requires coordination, which requires network round-trips, which increases latency. Weaker consistency lets replicas serve reads locally without coordination, reducing latency. This tradeoff is constant, not partition-dependent. Modern distributed databases can be classified by their PACELC choice: Spanner is PC/EC (chooses consistency during partition and normally); Cassandra is PA/EL (chooses availability during partition, latency normally); DynamoDB default is PA/EL, DynamoDB strongly-consistent-reads is PC/EC. Understanding your system\'s PACELC classification is the specific competence for reasoning about its always-on latency profile, not just its partition behavior. Real-world systems choose different PACELC profiles for different workloads within the same infrastructure — CockroachDB\'s different transaction types, Cassandra\'s per-query consistency levels, and DynamoDB\'s per-read consistent-vs-eventual choice all reflect this.
Below: each of three consistency levels (Linearizable · Causal · Eventual) evaluated against three workloads (Bank transfer · Social feed · Shopping cart). Watch how each level fits or fails each workload — the sharp diagonals show exactly which levels are safe for which use cases, and the off-diagonals show the specific failure modes. This is the matrix Expert engineers implicitly consult when designing consistency for a new workload.
The failure modes of consistency choices are the source of many high-profile production incidents — lost writes, split-brain scenarios, mysterious data corruption, "how did we get into this state?" postmortems. Each of these is a specific mismatch between what the workload needs and what the chosen consistency level provides. Recognizing these patterns is the specific competence that turns "we chose the wrong DB" into "we chose the wrong consistency level and could have used a different feature of the same DB."
Applying linearizable consistency where eventual would suffice pays the coordination cost without gaining any correctness benefit. Search indexes, product catalogs, session storage, social feeds, most read-heavy workloads don\'t require linearizable reads — users won\'t notice if a product description is 500ms stale. Deploying linearizability for these workloads means paying ~5-20ms of coordination latency per operation, plus a throughput ceiling from the consensus leader. The fix: (a) identify the specific correctness requirements of each workload — does anyone actually see the "old value" as a bug? (b) use the weakest level that satisfies requirements — eventual consistency with CDN caching for catalogs, causal consistency for feeds, linearizability for money; (c) use tunable consistency features when available — DynamoDB eventual reads for the catalog, strongly-consistent reads for money movement. The general principle: consistency isn\'t free; over-consistency is a specific antipattern.
Eventual consistency for correctness-critical workloads (money, inventory, ordering-sensitive ops) produces silent data loss under concurrent writes. The failure mode is specific: two writes to the same key hit different replicas within replication lag; both succeed locally; when replicas sync, application-level conflict resolution can\'t undo the effect. Once you\'ve told the user "transfer successful" and shown them the money in another account, you can\'t take it back without losing customer trust. The fix: (a) use linearizable single-object operations for balance changes — DynamoDB strongly-consistent reads + conditional writes, or a linearizable K-V store; (b) use serializable multi-object transactions for transfers — PostgreSQL SERIALIZABLE, CockroachDB, Spanner; (c) if you must use eventual consistency for money, use CRDT-based commutative operations (increment-decrement) with careful invariant enforcement, and accept that occasional double-spend will happen. The general principle: money, inventory, and correctness-critical workloads require linearizability at minimum; anything less is a specific class of bug waiting to manifest.
Vendor "strong consistency" marketing claims are frequently gap-filled with weaker formal guarantees. This has been repeatedly exposed by Kyle Kingsbury\'s Jepsen tests since 2013 — MongoDB, Cassandra, Redis, RethinkDB, various others have all had gaps between marketing claims and formal reality. The pattern: vendor says "strong consistency"; formal analysis shows the DB actually provides "linearizable single-object reads under normal conditions, but split-brain during specific failover scenarios can lose acknowledged writes." The fix: (a) read Jepsen reports for your chosen DB before deploying — jepsen.io has comprehensive analyses of most distributed databases; (b) for correctness-critical deployments, prefer DBs with formal verification (Spanner\'s TLA+ specs, FoundationDB\'s deterministic simulation testing) or extensive Jepsen validation (CockroachDB, YugabyteDB); (c) design idempotently — if a write can be lost, make the operation idempotent so re-executing it produces the same result. The general principle: trust formal verification, not marketing copy; Jepsen is the industry-standard verification tool.
Confusing serializability with linearizability is one of the most common architectural mistakes. PostgreSQL SERIALIZABLE means transactions are equivalent to some serial order — but that serial order doesn\'t have to match wall-clock time. Two sessions can commit transactions T1 and T2 in wall-clock order T1-then-T2, but the serializable execution can treat T2 as if it happened before T1. From a session-A-then-session-B perspective, session B might not see session A\'s committed data. This is legal under serializability but violates the intuition of "if I write, then immediately read, I see my write." The fix: (a) if you need real-time ordering across sessions, use a linearizable database (Spanner, etcd) or Postgres with specific patterns (SELECT FOR UPDATE, advisory locks); (b) for read-your-writes semantics from a single client, use session-consistency guarantees (most databases support this via connection-pinned sessions); (c) understand which level your DB actually provides — check the docs, run formal tests. The general principle: serializability is not linearizability; the difference matters specifically when real-time ordering is expected.
Even when eventual consistency is acceptable for the workload overall, specific client-side expectations often require session-level guarantees. "Read your own writes" (RYW): a client that just wrote data should be able to read it back. "Monotonic reads": a client shouldn\'t see time going backward (read newer, then read older data from a replica that hasn\'t caught up). "Monotonic writes": a client\'s writes should be applied in the order the client sent them. These are session-consistency guarantees — weaker than global consistency but stronger than pure eventual. The fix: (a) use session tokens or client-tracked timestamps that identify "the version I saw" — subsequent reads must return at least that version; (b) pin session to a specific replica or region so subsequent reads hit the same node; (c) use HLC-based versioning to detect and delay reads that would see time-reversed data. The general principle: eventual consistency at the global level often requires specific session-level guarantees at the client — RYW, monotonic reads, monotonic writes are the four canonical ones.
The composite pattern across all five is that consistency choices are workload-specific and layer-specific. Global consistency level is only one dimension; session-level guarantees (RYW, monotonic reads), object-level guarantees (linearizable single-key vs serializable multi-key), and application-level invariant enforcement (idempotency, compensating transactions) all matter. Expert-tier consistency design is not "pick a global level" but "understand what each layer needs and provide it explicitly". Modern distributed databases increasingly support this — tunable consistency, per-operation isolation levels, session tokens, causal contexts. Using these features correctly is what separates "our DB claims to be consistent" from "we\'ve architected consistency into every workload correctly."
The terms that show up in every distributed database architecture review, every "what does our DB actually guarantee?" investigation, every Jepsen report.
Test the ladder. Click an answer; explanation drops in instantly.
Perfect. Linearizability\'s real-time atomicity, serializability\'s transaction ordering, snapshot isolation\'s write-skew gap, causal\'s happens-before preservation, eventual\'s CRDT convergence — the tools for matching workloads to formal levels. Phase J foundations complete. Next up: M.51, distributed transactions.
The composite understanding that turns "strong consistency" into a precise architectural decision.
Not a binary property. From strict serializability (Spanner via TrueTime) down through linearizability, serializability, snapshot isolation, sequential consistency, causal consistency, to eventual consistency (Dynamo). Each level drops a specific constraint and costs less coordination. Choose deliberately at every layer.
The most common confusion. Serializability is multi-object transactions equivalent to some serial order — no real-time constraint. Linearizability is single-object atomic ops respecting real-time. A serializable database is not necessarily linearizable. PostgreSQL SERIALIZABLE alone doesn\'t guarantee read-your-writes across sessions.
Money requires linearizable + serializable. Social feeds require causal. Shopping carts survive eventual with CRDTs. Search indexes are fine with eventual. Client sessions need read-your-writes and monotonic reads regardless of global level. Modern databases increasingly support tunable consistency — use it deliberately per workload.
M.47 taught consensus. M.48 extended it to Byzantine adversaries. M.49 exposed distributed time. M.50 formalized consistency itself. Together these four modules establish the theoretical foundation for every subsequent Expert topic — geo-distributed transactions, storage engine internals, hardware-aware systems, formal verification. The primitives are now in your hands.