Dinesh/ Blog
systems

Designing for Scale · CAP and the Consistency Spectrum

CAP is a history argument, not a database label. A source-bounded lesson with worked reasoning, failure analysis and explicit runtime limitations.

9 min read
Checking device speech…
Lesson preparation & details

Level: advanced

Designing for scale · Lesson 3 of 20 ↗
Loading this browser’s progress…

By the end, you should be able to

  • CAP is a history argument, not a database label
  • Can an isolated minority accept all writes and still promise a single linearizable register with the majority?

Bring with you

Sources checked: . A source check does not change the publication or update date.

Editorial review: · What review means

In this article · 15 sections

The problem this post solves

In ACID, consistency refers to preserving the application's declared invariants through transactions. In replicated systems, a consistency model constrains the histories of reads and writes that clients may observe. Linearizability is one such model; “the most recent write” is not a definition covering every model or every concurrent operation.

Choose a contract for an operation and its scope. A profile editor, inventory reservation and public like count need not expose the same observations. A database brand or the label “strong” is insufficient: state the operation, transaction boundaries, regions, failure assumptions and client-visible result.

First principles

Replication communicates information across nodes, so delay and lost messages matter. A replica that has not received a write cannot infer its value merely because a read arrives. The design may route to an authority, wait for a replica position, reject/defer, or expose a weaker read contract. The options depend on what the network can still reach and what the operation promises; they are not simply “always slow” versus “always wrong.”

Local processing, leader placement, leases and quorum protocols change normal-case latency. No consistency label implies a fixed number of round trips, immediate response or a universal throughput penalty. During a partition, however, some combinations of guarantees cannot all hold. CAP is a statement about that failure model, not a purchasing guide for database products.

The CAP Theorem

Gilbert and Lynch's 2002 formalization considers atomic (linearizable) read/write objects, availability of operations at nonfailed nodes, and executions where communication can be partitioned. Availability means eventual completion of the specified operation with a valid response; returning an arbitrary error is not a trick that satisfies every read. It is not an uptime percentage or a p99 latency bound.

Consider replicas A and B starting at value 0. The network separates them. A completes write(1), then a client invokes a read at B. If B must respond without communication from A, it cannot distinguish this run from one where A completed write(2), or no write at all. One response cannot be correct for all those linearizable histories. Waiting indefinitely or rejecting the operation gives up the availability requirement for that request; answering with stale state gives up the linearizable register contract.

Thus “pick any two of C, A, P” is misleading. Partition is an execution to design for, not a feature toggle that can make communication failures impossible. Conversely, calling every “CA” description an illusion is too broad: a centralized or nonpartitioned model can supply atomicity and availability under its assumptions. The incompatibility concerns guaranteeing both through the stated partition executions. Explain those assumptions instead of attaching a permanent CP/AP adjective to an entire multipurpose system.

CP: Consistency and Partition Tolerance

For the register contract, an isolated node can refuse or defer operations it cannot serve safely. A connected majority/authority may continue while a minority stops; not every node must necessarily stop every operation. Some local immutable reads may remain safe even while new writes are unavailable. State which operations depend on the unavailable authority.

A bank example also needs a transaction invariant. Linearizable reads followed by separate unconditional writes can still race: two withdrawals both read 100 and both decide to spend 80. Use an atomic conditional update or a correctly isolated transaction for the whole rule. Choosing the letters CP alone does not prevent overdrafts.

AP: Availability and Partition Tolerance

A weaker contract can let disconnected replicas accept or serve local state and reconcile later. For a like counter, define duplicate operation IDs, increment/decrement behavior and how concurrent changes merge; “show whatever value is nearby” is not a complete algorithm. Eventual convergence needs assumptions about communication recovery and conflict resolution. Operations with preallocated independent rights can sometimes preserve a particular business invariant without a global linearizable register; that changes the operation/contract under discussion, not the theorem.

The PACELC Theorem

PACELC is Abadi's classification framework: under a partition consider availability versus consistency; else, consider latency versus consistency. The normal-operation half asks where coordination occurs and how far information must travel. It does not prove that strong reads always take two or three inter-region trips, or that weak reads are instantaneous. This section retains the familiar heading but treats PACELC as a design framework rather than asserting an additional universal impossibility theorem for every implementation.

For example, a local replica read may be fast but stale relative to another region's accepted write. A leader read can be low-latency for clients near a valid leader yet expensive for clients far away. Replication mode, read authority, conflict policy, quorum placement and failure detection determine the actual trade-off. Measure the operation in its topology and compare it against the product's freshness and failure rules, rather than assuming every financial operation is simple or every social operation tolerates arbitrary staleness.

The Consistency Spectrum

These contracts have several dimensions; they are not all points on one universal safety/cost ladder. Read-your-writes concerns a session, bounded staleness concerns freshness, and linearizability constrains real-time order across clients within the object's scope.

Strong Consistency

Use the precise term linearizable when that is intended. Operations appear to take effect atomically in a single sequential order that respects real-time ordering of nonoverlapping operations. A read after a completed write must respect that write, but may return a later write's value; overlapping operations can have more than one valid order.

Replicas need not all hold identical bytes at every physical instant. A protocol can use a quorum/authority while some followers lag. The read path must establish that it is entitled to serve the chosen committed state; merely calling one process “primary” is not proof after failover or a partition. Multi-object transactional isolation is a separate contract unless the implementation explicitly supplies the required combination.

Eventual Consistency

If updates cease and the system's communication/repair assumptions hold, replicas converge according to the specified resolution rule. Concurrent writes may require a merge or winner rule; there need not be one self-evident physical “last update.” This promise alone does not bound how stale a read can be, mandate a particular replication algorithm or guarantee low latency. It is an intentional option where the product can tolerate and explain its outcomes, not a defect label or a default property of every large-scale system.

Read-Your-Own-Writes Consistency

A session should not observe state preceding its own accepted write within the relevant scope. Suppose a write returns durable position 120. A later session read may go to replica B only after B's applied position reaches at least 120. If B is at 118, wait within a bound, route to a valid up-to-date authority or return the documented failure—not stale success. Carry the required position as a trusted session/consistency token, not just a wall-clock timestamp that different machines may interpret differently.

On failover, verify that the new authority actually retains position 120 under its durability contract. If acknowledged writes could be lost, a routing trick cannot recover the lost data. Across devices/sessions, decide whether the client carries the token or the service stores the minimum required version. Time-based “stick to primary for five seconds” is a heuristic, not a guarantee unless a proven lag bound and authority protocol support it.

Bounded Staleness

Specify a bound in versions or time and define its reference—for example, lag relative to a known committed position. A time guarantee needs adequate clock/measurement semantics. When replication cannot maintain the bound, the system must wait, reject or change the explicit contract; continuing stale reads while advertising the same bound violates it. Bounded staleness is not equivalent to read-your-writes: a user's just-completed write can still be newer than the allowed stale result unless both guarantees are enforced.

Failure modes

  • Quorum arithmetic mistaken for a full protocol: overlapping read/write sets do not alone define version resolution, concurrent-write ordering, durable acknowledgment or safe reads.
  • Consistency mistaken for business correctness: an atomic register can store an invalid price or an overdraft if the application never enforces the invariant.
  • A lost session token: routing to an arbitrary lagging replica can regress the user's view. Define token propagation and bounded-wait fallback explicitly.
  • Clock freshness mistaken for applied state: an apparently recent replica timestamp is not proof that a particular accepted write has been replayed.
  • Availability measured with a changed denominator: excluding all failed partition-time requests from an SLI does not satisfy the theorem's availability or the original product SLO.

Worked history exercise

Replica B has applied writes through position 118. A user's update commits at A as 120 and returns a token. A and B then partition. The user reads through B with token 120. Can B return its old value and still promise read-your-writes? Would a different user with no such token necessarily require the same behavior?

Contract-scoped answer

B cannot return the old value as a successful read-your-writes result for that session. It must reach an authority that can serve 120, wait within the declared policy, or fail/defer. Another user may be allowed a stale local read if that operation explicitly offers a weaker contract. If the API promises global linearizable reads, lack of a session token does not weaken that promise. The answer follows the operation's contract, not whether the database was casually described as CP or AP.

What to carry forward

Define allowed histories, failure model and atomic scope. Use CAP to reason about partition executions and PACELC to ask about normal-operation coordination. Implement session freshness with actual accepted/applied state, not optimistic clocks or product labels. The histories here are conceptual counterexamples, not a formal verification of a deployed replica protocol.

Sources and review boundary

Checked 2026-10-07: Gilbert and Lynch, 2002 CAP formalization and Abadi's 2010 PACELC explanation. PostgreSQL 16 warm standby provides a concrete versioned discussion of synchronous/asynchronous replication trade-offs; the position-routing trace is a conceptual contract, not copy-paste PostgreSQL failover code. No distributed service, bank invariant test under concurrency or consensus implementation was executed as part of this lesson review.

Pause / Recall / Apply

Can you explain it without the page?

Close the example. Reconstruct the core idea, then change one assumption. Mark complete when you’re ready; you can always undo it.

Stored in this browser only. No account, no sync. Clearing browser data removes your record.