Lesson 3 · Scaling and Trade-offs

CAP Theorem & Trade-offs

When the network fails, you must choose — and there is no middle ground.

The CAP theorem states that in the presence of a network partition, a distributed system can only provide either Consistency or Availability — but not both. It defines the constraints every distributed data store must accept by forcing a choice about how the system behaves when its components cannot communicate.

This is the first theorem in distributed systems that architects internalize as a hard constraint, not a preference. Understanding it doesn't give you a recipe — it gives you a lens for evaluating trade-offs every time you choose a data store or design a failure mode.

The Framework

Defining the Three Pillars

Consistency

Every read receives the most recent write or an error. The system acts as if there is only one copy of the data — even if replicated across nodes. C here means linearizability, not the C in ACID.

Availability

Every request receives a non-error response, without the guarantee it contains the most recent write. The system stays operational even if nodes fail.

Partition Tolerance

The system continues to operate despite an arbitrary number of messages being dropped or delayed by the network between nodes.

Partition Tolerance (P) is non-negotiable. Networks are unreliable — packets drop, cables get cut, hardware fails. Because you cannot prevent partitions, the real choice is between C and A when a partition occurs.

The Trade-off

CP vs. AP — Choosing Your Failure Mode

When a network partition splits your nodes into isolated groups, they can no longer coordinate. At that point, you must decide: does the system stop serving requests to avoid returning incorrect data, or does it continue serving requests with whatever data it currently holds?

This is not an engineering oversight — it is a fundamental constraint of distributed computing. The choice you make defines your system's behavior under failure.

Prioritize data integrity over uptime

If a node cannot verify its data is current with the other side of the partition, it returns an error or times out rather than risk serving stale information.

Use for: financial systems, inventory management, distributed locks

Prioritize uptime over data integrity

If a node is partitioned, it continues accepting writes and serving reads using whatever data it has. Nodes may diverge and must reconcile once the partition heals.

Use for: social feeds, recommendations, shopping carts, DNS

Decision tree during a network partition

Network Partition Occurs

↓

Choose Your Strategy

↓

Prioritize Integrity

↓

CP SystemReject read/write requests if sync with other nodes cannot be confirmed

Prioritize Uptime

↓

AP SystemAccept read/write requests using local, potentially stale data

Refining the C

The Spectrum of Consistency Models

CP and AP describe a decision made at the moment a partition hits. But consistency itself is not a single property. It is the contract between a data store and its clients about the ordering and visibility of writes, and that contract comes in degrees.

The C in CAP names the strictest point on that gradient. Real systems rarely apply one point across an entire application — they run different guarantees for different workflows, paying for strictness only where the business actually needs it.

The strict end

Linearizability

The strongest single-object model. Every operation appears to take effect atomically at one instant between its invocation and its completion. Once a write completes, any later read — no matter which node serves it — returns that value or a newer one.

Sequential Consistency

Relaxes real time. Operations do not have to line up with a global clock, but every client observes all operations in the same relative order. Cheaper to maintain, and enough for many coordination problems.

Both models force the CP choice. To hold either one during a network failure, a node cut off from the coordinator has to reject reads and writes rather than answer from state it cannot verify. That refusal is exactly what prevents split-brain.

The loose end

Eventual consistency guarantees only that if writes stop, all replicas converge on the same value. Until then, concurrent reads sent to different nodes can return stale data, mutations out of order, or values that flatly contradict each other.

Between full linearizability and raw eventual convergence sit the client-centric guarantees. Each is far cheaper than linearizability, and each buys one specific property that users actually notice when it is missing.

Read-Your-Own-Writes

A client always sees its own updates. Change your profile photo and a reload shows the new one, even while other users still see the old one.

Monotonic Reads

A client never moves backwards in time. Once it has observed a value, later queries never hand back an older one.

Consistent Prefix Reads

Nobody sees a write without the writes it depends on. A reply never appears before the question it answers.

These three are independent, not synonyms. A store can give you read-your-own-writes and still walk time backwards on the next query. Bundling all three and scoping them to a single client is what most databases label session consistency.

Model	Under partition	Normal latency	Replication requirement	Common use case
Linearizable	Rejects reads and writes	Highest — multi-node round trips	Synchronous consensus (Raft / Paxos)	Financial ledgers, seat booking, inventory holds
Causal	Stays available	Low — asynchronous propagation	Vector clocks, dependency tracking	Comment threads, collaborative editing
Eventual	Stays available	Lowest — local read and write	Asynchronous background repair	Social feeds, analytics counters, DNS

Replication behavior under network partition

Client Write Request

set balance = 150

↓

Network Partition

↓

Node A (Isolated)

current state: balance = 100

CP mode

↓

Write Rejected (503)

cannot reach consensus quorum

↓

Node B (Isolated)

current state: balance = 100

AP mode

↓

Write Accepted Locally

divergence risks split-brain

Under the Hood

Quorum: How a Node Knows to Say No

A partitioned node cannot tell whether the other side is dead or merely unreachable, so it never tries to guess. Consensus protocols such as Raft and Paxos require a strict majority of the cluster, ⌊N/2⌋ + 1 out of N nodes, to agree before a write is committed. A node that cannot reach that many peers refuses to act.

This is what prevents split-brain, the failure mode where two disconnected halves of a cluster both believe they are in charge, both accept writes, and diverge into two irreconcilable versions of the truth. Since only one side of a partition can hold a majority, only one side is ever allowed to make progress.

A 5-node cluster split across two data centers

Quorum is ⌊5/2⌋ + 1 = 3 nodes. The link between the two sites goes down.

DC East

3 of 5 nodes

Majority reached

Elects a leader and keeps serving reads and writes. This side holds the authoritative state.

DC West

2 of 5 nodes

No quorum

Every write and every linearizable read sent to N4 or N5 is rejected or blocked until the partition heals.

Pitfall: always deploy an odd number of voting nodes. With an even cluster, say 4 nodes partitioned 2 and 2, neither side holds a strict majority. Both halves stop accepting writes and the cluster goes fully unavailable, even though every single node is healthy.

Real-World Example

A Banking Application Under Partition

A user has $100 in their account. The system replicates this balance across two data centers. A network partition cuts off communication between them. The user attempts a withdrawal.

CP — Consistency chosen

The system stops accepting withdrawals. It cannot guarantee the user hasn't already withdrawn $100 from the other data center, so it errors out to ensure the balance remains correct.

The user sees a "Service Unavailable" message — but the data remains accurate.

AP — Availability chosen

The system allows the withdrawal at both data centers simultaneously. It prioritizes the user's ability to complete the task, even though internal state is now inconsistent — the user effectively withdrew $200 from a $100 balance.

A reconciliation process must resolve this once the partition heals.

CAP is a framework for failure, not normal operation. During normal operation — when there is no partition — systems can generally provide both high consistency and high availability. The trade-off only forces your hand when the network degrades.

The AP Side

Conflict Resolution When Replicas Diverge

Choosing AP is not the end of a decision — it is the start of a second one. Node B accepted the write while it was isolated, so once the link comes back there are two versions of the same record and no node that witnessed both.

Every highly available store therefore ships a reconciliation strategy. Which one it picks decides whether divergence costs you data or merely costs you code.

Approach 1 — Last-Write-Wins

The database stamps every write with a physical wall-clock timestamp. When two conflicting versions meet during reconciliation, the higher timestamp overwrites the lower one. It is simple, deterministic, and adds almost no storage overhead — one timestamp per record.

The cost is silent data loss. LWW trusts physical clocks, and physical clocks drift even under NTP. A node running a few milliseconds fast stamps its write with a higher timestamp and quietly discards a genuinely newer write made elsewhere. Nothing errors and nothing logs — the write is simply gone.

Approach 2 — Vector Clocks and Version Vectors

Rather than trusting wall clocks, vector clocks record causal history. A vector clock is a set of logical counters, one per node, where each entry counts the operations that node has applied. Comparing two vectors answers a question a timestamp cannot: did one version actually descend from the other, or did they happen independently?

// One version descends from the other
V1 = [ a:1, b:1 ]   V2 = [ a:2, b:1 ]
  every entry in V1 is ≤ V2, and one is strictly less
  → V1 happened before V2, so V2 wins and V1 is safe to drop

// Neither descends from the other
V1 = [ a:2, b:1 ]   V2 = [ a:1, b:2 ]
  neither vector dominates the other
  → concurrent write, unresolvable without domain knowledge
  → both versions surface to the application as siblings

Vector clocks never lose a write, but they never decide for you either. They convert silent data loss into an explicit conflict that the application layer has to resolve — strictly more work, and strictly safer.

Approach 3 — Conflict-Free Replicated Data Types

CRDTs sidestep reconciliation entirely by choosing data structures whose merge operation cannot conflict. Every replica merges whatever it receives, in whatever order it arrives, and they all land on identical state — no coordinator, no arbitration, no application-level decision.

Commutative

A ∪ B = B ∪ A

Arrival order does not change the result.

Associative

(A ∪ B) ∪ C = A ∪ (B ∪ C)

Grouping of merges does not change the result.

Idempotent

A ∪ A = A

Applying the same update twice changes nothing.

Those three properties are precisely what make reordering, regrouping, and duplicate delivery harmless — which is exactly the list of things an unreliable network does to your messages.

PN-Counter

A counter supporting increments and decrements, by keeping one grow-only tally per node for each direction and summing them.

LWW-Element-Set

A set supporting adds and removes, where each element carries a timestamp that settles membership conflicts.

OR-Set

An observed-removed set, where each add is tagged with a unique id so a concurrent add always beats a concurrent delete.

Choosing between them is a question about the field, not the database. Use LWW where the last edit genuinely should win and losing one is survivable, such as a display name. Use vector clocks where no write may be lost and something can arbitrate, such as a shopping cart. Use a CRDT where convergence must happen with no arbitration at all, such as a like counter or a collaborative document.

These constraints form the basis for understanding database replication strategies and distributed transaction patterns — topics covered in the lessons ahead.

Quiz Review

Check your understanding

Question 1 of 14

What does the "C" in CAP mean, and what does it guarantee?

✓Consistency — every read receives the most recent write or an error. The system behaves as if there is only one copy of the data, even when replicated across nodes.