CAP Theorem and Consistency Models

Advanced System Design & Software Architecture · Lesson 31 · High-Level Design and Distributed Systems

Lesson Overview

Checkout commits a payment on the PostgreSQL primary and waits for a standby, which is the design in Database Replication and Consistency. History reads sometimes run on a replica that has not replayed that commit. A second shard, from Database Sharding and Partitioning, does not even have the row. Someone in the review says "CAP means we picked AP, so stale reads are fine," and someone else says "we are CP because we use PostgreSQL." Both sentences are too blunt to design with.

CAP, as Gilbert and Lynch formalized Brewer's conjecture, is a statement about a partition: while messages between nodes are lost, you cannot promise both linearizability and a response from every non-failed node. It does not rank databases into two clubs. It does not speak about latency on a healthy network. PACELC does. Linearizability, sequential consistency, causal consistency, and eventual consistency are different promises about what a read may return. Read-your-writes is a session promise, smaller than linearizability and large enough to stop a learner paying twice.

This lesson ties those names to decisions you already made on the learning platform, and to three workloads that do not share a model: a ledger balance, an activity feed, and a shopping cart. The next lesson, Distributed Transactions and the Saga Pattern, uses the same vocabulary when a saga exposes intermediate states on purpose. SQL isolation on one primary stays in Isolation Levels and ACID Principles. Isolation and distributed consistency are related and they are not the same knob.

Learning Objectives

By the end of this lesson you will be able to:

1. State CAP as a partition-time impossibility using Gilbert and Lynch's meanings of consistency, availability, and partition tolerance.
2. Explain why "pick two of three" misleads operators who cannot opt out of network faults.
3. Use PACELC to talk about latency versus consistency when the network is healthy.
4. Define linearizability, sequential consistency, causal consistency, and eventual consistency with an example of a read that one allows and another refuses.
5. List the session guarantees: read-your-writes, monotonic reads, monotonic writes, and writes-follow-reads.
6. Describe quorum intersection (R + W > N) and the extra conditions it needs before anyone may call a read linearizable.
7. Map PostgreSQL sync commit, async replica reads, and shard fan-out onto these models without renaming the database.
8. Choose a model for a ledger, a feed, and a cart, including what the user sees during a partition.
9. Separate SQL isolation levels on one primary from a distributed consistency claim.
10. Reject a design review sentence that cites CAP and does not name the operation, the partition, and the user-visible behavior.

Prerequisites

• Lessons 29 and 30. You need a concrete replica lag and a concrete second shard, or the models stay as posters.
• Transactions and Isolation Levels. This lesson will point at them and then leave the single-node executor.
• Comfort with "the client was told the write succeeded." Every model below is about what that sentence obliges the next read to do.
• No distributed-systems textbook is required. Papers are cited in Further Reading for the definitions this lesson uses.

Detailed Core Concepts

What CAP actually says

Eric Brewer conjectured in 2000 that a web service cannot be consistent, available, and partition tolerant at the same time. Seth Gilbert and Nancy Lynch proved a precise version in 2002. In that statement:

• Consistency means linearizability. There is a single total order of operations that respects real time. If a write completes, a read that starts after that completion returns the written value or a later one. This is not the "C" in ACID. ACID consistency means constraints are true. A database can enforce constraints on one node and still serve a stale replica.
• Availability means every request to a non-failed node receives a non-error response. It does not mean "the vendor quoted 99.95%." A node that waits forever because it cannot reach its peers is not available under this definition, even if it would have answered correctly tomorrow.
• Partition tolerance means the system continues despite lost or delayed messages between nodes. On a network you do not control, partitions happen. You do not pick "no P" except by running a single node that does not need to agree with anyone else.

The theorem says: during a partition, a system cannot guarantee both linearizability and a response from every non-failed node. If you answer on both sides of the cut, those answers can disagree with a single real-time order. If you refuse to answer until the cut heals, you have given up the availability guarantee in order to keep linearizability.

"Pick two" is the slogan that drops the word "during a partition." In healthy operation a system can be linearizable and responsive. The engineering choice is what you do when the messages stop, and, separately, how long you are willing to wait when the messages are merely slow. That second choice is PACELC.

PACELC

Daniel Abadi's PACELC observation splits the life of the system in two. If there is a partition (P), choose availability (A) or consistency (C). Else (E), when the network is working, choose latency (L) or consistency (C).

TechLearningPro's payment commit with synchronous_commit = remote_apply is the "else" branch: there is no partition, and the service still waits for another host before it answers. That wait is latency paid for a stronger durability and visibility claim. An async commit is the low-latency choice on the healthy path. It also means a later partition, and a failover, can expose that the acknowledged write lived on one machine.

A partition makes the same knob sharper. If pay_standby is unreachable and the transaction requires it, the primary stops acknowledging payments. Writers are not available, in the CAP sense, so the system can avoid telling the client "your money is durable on two nodes" when the second node is a guess. If history replicas answer anyway, those reads are available and they are not linearizable. Both choices can be correct. They are correct for different operations. CAP is not a label you stamp on the whole company.

Linearizability

Linearizability (Herlihy and Wing) treats each operation as if it happened at a single instant between when the client called and when the client received the response. That instant is the linearization point. The instants form a total order. Real time constrains it: if operation A returns before operation B is invoked, A comes first.

For a register, a read returns the value of the latest write in that order. Practical consequence: after any client has seen a write complete, no client may see an older value. That is stronger than "I see my own write." Another learner, another service, another region, all of them, are covered.

A single PostgreSQL primary, with clients who send every read and write to that primary, can provide this for the data it stores. The linearization point is the commit. READ COMMITTED still allows anomalies inside overlapping transactions on that primary. Those are isolation questions. They do not make a committed row invisible to a later transaction on the same primary. The moment you send the later transaction to an async replica, the history can show a read that returns before the write in real time and misses the value. That history is not linearizable. The primary did not become "eventually consistent." The read path left the linearizable boundary.

Sequential consistency

Sequential consistency (Lamport) requires one total order of all operations that respects the order of each client's own calls. It does not require that order to match wall-clock order between clients. Client A can complete a write, and client B, who starts after A finished, can still observe the old value, as long as there exists some total order that looks legal for each client's program order. Linearizability forbids that. Sequential consistency allows it.

The difference shows up in reviews more often than the names do. "We have a single queue of writes, so we are strongly consistent" may be sequential if readers are allowed to lag that queue. It is linearizable only if a read that starts after the write's response is guaranteed to see it. Replication lag with a load balancer is the usual place the stronger claim fails.

Causal consistency

Causal consistency keeps cause before effect and lets concurrent writes diverge.

If the same client writes a lesson and then writes "I published it," everyone who sees the announcement sees the lesson. If a client reads the announcement and then posts a comment, everyone who sees the comment sees the announcement. Those are causal edges: program order on one client, and a read-from edge between clients, plus transitivity. Writes with no causal path are concurrent. Different readers may see concurrent writes in different orders.

A feed can live here. A balance cannot. Two concurrent adjustments to the same account must not both "win" on different replicas in ways that fail to commute. Causal systems either forbid concurrent writes to the same key (a single leader) or require operations that merge (counters that add, sets that union). A merge function is a design, not a default of "eventual."

Eventual consistency

Eventual consistency says that if updates stop, replicas converge to the same state. It does not say when. It does not say a read after a write on one client sees that write. It does not say two readers see the same state on Tuesday. Production systems add a lag SLO on top of the definition. The SLO is an operations target. It is not the definition.

Strong eventual consistency adds a condition: replicas that have applied the same set of updates have the same state, without a leader election. Conflict-free replicated data types are one way to get that, by restricting operations to ones that merge. A course-progress percentage overwritten by last-write-wins is not a CRDT just because two regions store it. Last-write-wins with skewed clocks drops updates. If the product cannot drop a completion event, do not call the column eventually consistent and walk away. Put a single writer on it, or store an operation that merges.

Session guarantees

Douglas Terry and colleagues, in the Bayou work, named guarantees a session can ask for even when the whole database is not linearizable:

• Read-your-writes. A read sees the updates the same session has already completed.
• Monotonic reads. A later read sees a state at least as new as an earlier read. The order does not flicker backward.
• Monotonic writes. The session's writes apply in the order the session issued them.
• Writes-follow-reads. A write is applied after the writes that this session previously read, so a comment is not stored in a replica that has never seen the post.

Lesson 29 implemented read-your-writes with an LSN token and implemented monotonic reads by not sending the session backward to a more lagged replica. Those are session guarantees. They do not make a second learner's read linearizable. Say the smaller thing in the API review. It is the thing you built.

Quorums

A quorum scheme writes to W of N replicas and reads from R of N. If R + W > N, a read set and a write set overlap, so the read hits at least one replica that saw the latest acknowledged write, if "latest" is visible as a version and if the W replicas are members of the configured N. You still have to return that latest version, not the first response, and you still have to define what concurrent writes do. Intersection is a mechanism. Linearizability needs the real-time story as well.

Sloppy quorums, as described for Dynamo-style systems, accept the write on temporary nodes when the preferred nodes are down, and catch up later with hinted handoff. Those temporary nodes are not in the overlapping set you counted. The system stays available for writes and gives up the intersection guarantee until the hint is delivered. That is an explicit PACELC-style choice, not a broken quorum. It is also not what PostgreSQL synchronous replication does. A named standby either flushes the WAL or the commit waits. There is no silent write to a third volunteer node.

FIRST 1 of two standbys is a small quorum for durability of the commit record. Reads from a random async replica are R = 1 against a node that was not required to be in the write set. You should not describe that read as quorum-fresh.

One system, several models

TechLearningPro does not have one consistency model. It has one per operation.

During a partition between application and primary, you cannot complete a linearizable payment. The honest behaviors are: wait, fail the request, or accept a write you might have to reconcile. The third one is a product decision with a reconciliation owner. CAP does not make it for you.

Architecture and Design Diagrams

mermaidCopy
flowchart TD
    client[Client operation]
    part{Network partition?}
    healthy{Wait for the latest copy?}
    lin[Answer only if the linearizable source responds]
    avail[Answer from a local copy that may be stale]
    fast[Respond after local commit]
    strong[Wait for sync standby or quorum]
    client --> part
    part -->|yes| lin
    part -->|yes| avail
    part -->|no| healthy
    healthy -->|pay latency for consistency| strong
    healthy -->|pay consistency for latency| fast

The top split is CAP during a partition. The bottom split is PACELC while the network works. Payment checkout takes the strong branch on the healthy path and the linearizable-or-fail branch during a partition. The activity feed takes the fast branch when healthy and the available stale branch during a partition. Drawing one box labeled CP for the whole platform erases the split.

mermaidCopy
sequenceDiagram
    participant Buyer
    participant Primary
    participant Replica
    Buyer->>Primary: write cart line
    Primary-->>Buyer: committed
    Buyer->>Replica: read cart immediately
    Replica-->>Buyer: old cart
    Note over Buyer,Replica: breaks read-your-writes and linearizability
    Buyer->>Primary: read cart with session pin
    Primary-->>Buyer: new cart
    Note over Buyer,Primary: read-your-writes held, other users may still read the replica

A second buyer who reads the replica can still see the old cart. That is allowed by a session guarantee and forbidden by linearizability. The diagram is the interview answer.

Technical Explanation

How to test which model you have

Write a test that does not use the word "consistent."

Linearizability probe. Client 1 commits a write and receives success. Client 2 starts a read only after that response. If client 2 can observe the old value, the path is not linearizable. Run this against the URL the second client will really use, not against the primary by habit.

Read-your-writes probe. The same client writes, then reads through the same session. A miss fails the session guarantee even if some other replica is caught up.

Monotonic-read probe. The client reads the new value, then reads again through a different replica. The old value reappearing fails monotonic reads.

Causal probe. Write a parent row, then a child that assumes the parent. A replica that shows the child and not the parent fails causal delivery. Ordinary PostgreSQL physical replication preserves this for WAL order on one primary: the replica applies in WAL order, so it will not show a later commit and hide an earlier one on that stream. The failure appears when two shards or two services publish events independently and a consumer applies them out of cause order. That is a lesson 32 and lesson 33 concern. Do not claim causal consistency across services because one PostgreSQL standby applies WAL in order.

Convergence probe. Stop writers. Wait past the lag SLO. Compare checksums of business keys per tenant across replicas. Eventual consistency without a wait bound is not an SLO. The test needs a number.

SQL isolation is a different axis

READ COMMITTED, PostgreSQL's default, means a statement sees rows committed before the statement started, and does not mean a distributed replica is current. REPEATABLE READ and SERIALIZABLE change which anomalies concurrent transactions on that primary can observe. They do not ship a snapshot to an async replica any faster. Cite Isolation Levels when the bug is two checkouts racing on one seat row. Cite this lesson when the bug is a committed seat invisible on a replica or another shard.

Serializable snapshot isolation on the primary is the right tool for the seat row. It is local. The shard that owns the course runs it. A second region that accepted the same seat because it could not reach the owner has left that tool behind and is in reconciliation.

What a partition looks like in the platform

Application cannot reach the primary, replicas are reachable. History can still be served from a replica if the product accepts staleness. Checkout cannot commit a linearizable payment. Queueing writes on the replica and hoping to apply them later is multi-master. PostgreSQL physical replicas will reject the insert (25006). Building your own queue in front of a down primary is a decision to accept writes you cannot yet order. Name the reconciliation.

Primary cannot reach the sync standby. Commits that require the standby block. That is availability given up for the durability claim. Heartbeats configured as local still commit. They are a different operation with a different model. Do not let a heartbeat helper "temporarily" wrap payments.

Shard directory reachable, one shard not. Tenants on the down shard fail. Others proceed. The platform is not uniformly available or uniformly down. CAP applied to "the platform" hides this. Apply it per operation and per shard.

Two regions, each with a primary, partition between them. Unless one region refuses writes, you will have two histories. Repair is not replication catch-up. It is a merge policy. If you do not have a merge policy, do not take writes in both regions.

Clocks

Last-write-wins needs a clock. Wall clocks jump. A write from a lagging region can overwrite a newer completion because its timestamp is behind. Hybrid logical clocks and version vectors exist so "later" is a causal notion rather than a wristwatch. If you do not want to operate that machinery, give the row a single primary and use the commit order PostgreSQL already has. That is the boring linearizable path, and it is available inside one shard.

User-visible copy

Each model needs a sentence the product can show.

• Linearizable payment: "If we said it succeeded, a later read of the order on the account page shows it."
• Session read-your-writes: "You see your update. Another device might take a moment."
• Eventual feed: "New reviews can take up to a minute to appear for other learners."
• Partition: "Checkout is paused. We are not placing a second charge."

If the sentence is missing, the model has not been chosen. It has been nicknamed.

Practical Implementation or Design Walkthrough

Problem

Three TechLearningPro operations are sharing the word "consistent" in one ADR. Split them.

Ledger-style payment record

Need. Once the API returns success, a later read of that payment by any service that is allowed to decide money must see it. A partition must not create two successes.

Design. One primary owns the payment row for that tenant shard. The transaction sets synchronous_commit = on or remote_apply against a named standby. Readers that decide money use the primary, or a replica only after the LSN compare from lesson 29, and a service that cannot reach the primary returns an error rather than guessing. Idempotency keys stop a client retry from inserting a second payment. Isolation on the primary is at least READ COMMITTED with a unique idempotency key. Use SERIALIZABLE or a single-row UPDATE ... WHERE seats > 0 where the invariant is a counter, not because CAP told you to, but because two local transactions can still race.

Partition behavior. Fail the payment request. Do not write it to a replica.

Activity feed

Need. A learner posts a review. They see it on their profile immediately. Other learners see it soon. Order between unrelated reviews does not matter. A review reply must not appear without the review.

Design. The author's read uses the primary or an LSN pin: read-your-writes. Other readers use async replicas or a feed cache. Lag SLO is 30 seconds at p99, alert at 60. Replies store review_id. The consumer that builds the feed applies the review before the reply, which is easy if both rows commit on one primary in one WAL. If a reply is a different service, it carries the review id and waits until the review is visible, or it is produced in causal order through a single partition log. That log is Message Queues and Event Streaming. This lesson only requires the cause edge to be explicit.

Partition behavior. Keep serving the feed from the last replica snapshot. Hide the composer if the primary is down, so you do not accept a review you cannot order.

Cart

Need. The shopper adds a course and sees it in the cart on the next click. Two devices should not lose lines. Inventory is not the cart: the seat is taken at checkout, on the shard that owns the course, with an atomic update.

Design. Cart rows live on the tenant or learner shard, one primary. Session reads are pinned to the primary for a short period after a write, or they carry the LSN. That is read-your-writes and monotonic reads. Another shopper does not need a linearizable view of this cart. Checkout of the last seat is a conditional update on the inventory owner, not a read of the cart replica. If the conditional update affects zero rows, checkout says the seat is gone. The cart can still display the course. Those are different rows with different models.

Partition behavior. Cart edits fail closed when the cart primary is unreachable. The page can show the last cart the client cached, labeled as possibly stale, and must not pretend the cached cart checked out.

A Spring boundary that records the choice

javaCopy
public enum ReadPolicy {
    PRIMARY,          // linearizable with respect to commits on that primary
    SESSION_LSN,      // read-your-writes for the caller's token
    REPLICA_TOLERANT  // stale within the lag SLO
}

OrderHistoryReader from lesson 28 takes a ReadPolicy. Payment confirmation uses PRIMARY. The home page uses SESSION_LSN when a token exists and REPLICA_TOLERANT when it does not. The feed uses REPLICA_TOLERANT. There is no CONSISTENT enum value. The word was too large.

Validation

• Run the linearizability probe against the payment GET. It must not hit an unpinned replica.
• Run the read-your-writes probe on the cart through the session.
• Pause apply on a replica in a lab and show the feed still answers and the payment path does not use that replica.
• Block the sync standby and show payment commits time out while the feed still serves.
• Document the sentence the UI is allowed to display in each case.

Enterprise Real-World Scenarios

Scenario 1: Ledger, feed, and cart on one platform

Context. TechLearningPro billing, the course review feed, and the cart were described in one diagram as "the PostgreSQL cluster, strongly consistent."

What breaks. Billing reads a replica to "scale" and under-states a payment that committed. The feed is served from the primary and becomes the capacity problem. The cart is cached in the browser and also written on two regions during a drill, and a line disappears under last-write-wins.

Design. Billing reads and writes the shard primary, with sync commit for the capture. The feed is replica reads plus read-your-writes for the author, causal order for a reply, lag SLO 30 seconds. The cart is one shard, session pin, no second writer. The browser cache is a hint that revalidates against the session policy before checkout. Three sentences in the ADR replace the one adjective.

Scenario 2: A regional outage and a tempted second writer

Context. A staff-training bank design keeps balances on one primary in region A, with a sync standby in region B. Region A becomes unreachable from customers in B. The standby has the flushed WAL. Operators can promote it, which is lesson 29, if and only if region A is fenced.

The CAP moment. If region A is not fenced and region B is promoted, both accept debits. Linearizability is gone and availability of writes is up, and Monday's merge is insolvency. If region B refuses to promote until the fence succeeds, writers in B see an error. Availability of the debit operation is down, and the balance order is intact. If region B serves read-only balances from the standby while A is still primary, those reads can be stale by the replay lag. Say so on the screen. Do not also accept withdrawals against that snapshot.

The feed of marketing messages can keep serving from a stale replica through the same incident. The temptation is to reuse the withdrawal screen's data path for that feed's availability story. They are different operations.

Best Practices

• Name the model per operation. Include the client, the data item, and the partition behavior.
• Reserve linearizability for decisions that move money, inventory, or permissions.
• Use session guarantees for the caller's own subsequent reads when other users can wait.
• Put a lag SLO and an alert on every eventual path. The definition without a bound is not operable.
• On a healthy network, write down the latency you pay for sync commit. That is the PACELC "else" branch.
• During a partition, fail closed on linearizable operations. Serve stamped stale data only where the product copy allows it.
• Keep a single writer for data you cannot merge. Add a merge function before you add a second writer.
• Do not treat quorum intersection as linearizability. State versions, membership, and real-time.
• Do not treat SQL isolation as a replica freshness setting.
• Probe with two clients and a clock order. A unit test on one connection never sees lag.
• Fence before a second region accepts writes.
• Store the choice in the code as an explicit read policy, not as a comment that says "consistent."

Common Mistakes and Anti-Patterns

"We picked AP." The platform still has payments that block when the standby is gone, which is not the availability side of CAP, and a feed that serves stale rows, which is. One label cannot describe both. Name the operation.

"PostgreSQL is CP." A primary that clients all use can give you linearizable commits for those clients. An async replica read is a different system on the same files. The engine did not pick for you.

Equating ACID's C with CAP's C. A check constraint can hold on a replica that is an hour behind. Constraints are local invariants. Linearizability is about time and visibility of the latest write.

Last-write-wins as a universal conflict policy. Clocks skew, and a stale region overwrites a completion. Use it only when losing one of the writes is acceptable and the clock is good enough. Otherwise use one primary.

Quorum arithmetic without membership. R + W > N on a slide, sloppy quorum in the outage. The read misses the write. Document whether fallback nodes count.

Session guarantee described as strong consistency. The buyer sees the cart. The auditor's replica does not. Both descriptions can be true. The audit path needs its own model.

Serving a withdrawal from a read replica to stay available. You stayed available and you lost the linearizable balance. If the product wanted availability, it wanted a read-only estimate with a label, not a debit.

Troubleshooting and Design Review

Review checklist: For each operation, what may a read return one millisecond after a successful write, for the same caller and for a different caller? What happens when the primary's peer is unreachable? What is the merge policy if two writers exist? What sentence does the UI show?

Interview Questions and Answers

Q1. How do you state the CAP theorem in a design review?

During a network partition, a system cannot guarantee both linearizability and a response from every non-failed node. Gilbert and Lynch's consistency is linearizability, not ACID constraints. Availability means a non-failed node answers, not a marketing uptime number. Partition tolerance is required if you communicate over a faulty network. Outside a partition the theorem is silent. Latency versus freshness on a healthy network is the PACELC question. Apply the choice per operation. A payment can fail closed while a feed serves a stale page.

Q2. Why is "pick two of C, A, and P" a weak answer?

It treats partition tolerance as optional. For any system that must talk across hosts, message loss is a condition you handle, not a feature you disable. The real pick, during the partition, is whether to answer with a possibly stale or divergent result or to wait or fail. When there is no partition, you can be linearizable and responsive, and you still choose how long a commit waits. A review that stops at "we're AP" has not said what the user sees when a standby dies.

Q3. What does linearizability require that sequential consistency does not?

Both want a single total order. Linearizability also respects real time across clients: a read that starts after a write has returned must see that write or a later one. Sequential consistency only preserves each client's program order inside some global order. A write can have completed for client A, and client B can still read the old value, without breaking sequential consistency. Replica lag in front of a second client breaks linearizability and can still be sequentially explainable. Money paths usually need the real-time clause.

Q4. What does causal consistency guarantee that eventual consistency does not?

A learner publishes a review and then a reply that refers to it. Causal consistency says anyone who sees the reply sees the review, because the reply was caused by a state that included the review. Eventual consistency only says that if you stop writing, replicas will match later. It allows a window where the reply is visible and the review is not. Physical WAL order on one primary preserves that cause. Two independent services that emit both facts can violate it unless you order them.

Q5. Which session guarantees did the order-history LSN design implement?

Read-your-writes: the session remembers pg_current_wal_lsn() and will not read a replica whose pg_last_wal_replay_lsn() is behind that token. Monotonic reads: the session does not later pick a replica behind a value it already observed, if the pin only moves forward. It does not make another user's read linearizable. Monotonic writes and writes-follow-reads matter when the same session issues a series of updates or writes based on a read. One history GET after checkout does not exercise those two. Name the ones the code enforces.

Q6. When does R + W > N fail to give you the read you expect?

When "latest" is not identifiable, so you return a stale overlapping replica's value. When concurrent writes need a rule you did not define. When sloppy quorum counts a temporary node outside the preferred set, so the sets you actually used do not intersect. When the read is served from an async PostgreSQL replica that was never in the write's sync set. Intersection is about the nodes that acknowledged the write and the nodes the read contacts. Draw those sets before you claim the property.

Q7. How do you place a bank balance, a social feed, and a cart on the models in this lesson?

The balance is linearizable for anyone who debits or displays a figure the customer can withdraw against: one primary, sync durability, no stale replica on that read, fail the debit if the owner is unreachable. The feed is eventual for other readers, with a lag SLO, plus read-your-writes for the author, plus causal order for replies. The cart is read-your-writes and monotonic reads for the shopper on one shard. The seat inventory is a separate linearizable update on the course owner, not a field on the cart. Three models, three sentences in the ADR.

Q8. A colleague says serializable isolation makes the replica read linearizable. What do you answer?

Serializable isolation on the primary controls interleaving of transactions that run on that primary. It changes which snapshots those transactions see. It does not advance replay on a standby. A serializable transaction sent to a lagged replica is a perfectly isolated look at an old state. Freshness is where you send the query and how far that node has applied. Cite both axes when a bug could be either a race on one node or a stale replica.

Q9. What should the payment service do when it cannot reach the primary during a partition?

Return an error and keep the idempotency key so a retry is safe. Do not record success. Do not write the payment to a hot standby that is still a replica. Do not invent a second primary in the other region unless the first is fenced and the promote runbook from lesson 29 has finished. Waiting is the CAP choice that protects linearizability of the debit. The feed may keep reading. The payment method may not call the feed's read policy because it is convenient.

Q10. What is the PACELC trade-off in synchronous_commit = remote_apply when nothing is broken?

There is no partition. The commit still waits until a named standby has replayed the WAL, which adds a network round trip and apply time to the response. That is latency paid so a read on that standby, and a failover to it, observes the commit. synchronous_commit = local returns after the primary flush and is faster, and an async replica or a sudden primary loss can hide or drop the commit. Choose per transaction. Heartbeats and payments do not have to share the setting.

Q11. How do you prove a design is not linearizable without a theorem?

Client A receives a successful write. After that response, client B issues a read to the documented read endpoint and receives the old value. One counterexample is enough. If only the same client can miss the write, you have broken read-your-writes and you still might not have been claiming linearizability. Record the endpoints. A probe that reads the primary while production reads a replica proves nothing about production.

Hands-On Exercises

Exercise 1: Three models

Problem. Specify consistency for TechLearningPro payments, review feeds, and carts, including partition behavior.

Tasks.

1. For each operation, name the model and the mechanism (primary, LSN, replica with SLO, warehouse).
2. Write the linearizability probe and the read-your-writes probe as steps a test can run.
3. State what the UI says when the primary is unreachable and when a replica is 45 seconds behind.
4. Explain why one cluster-wide "CP" label does not survive this table.

Deliverables. A one-page decision record and the two probes.

Exercise 2: Quorum claim review

Problem. A proposal says: N = 3, R = 2, W = 2, therefore balances are linearizable, and PostgreSQL async replicas will be the read quorum.

Tasks.

1. Draw the write set for a sync PostgreSQL commit and the read set for an async replica.
2. Say whether those sets intersect.
3. List two further conditions intersection would still need before a linearizability claim.
4. Rewrite the proposal so the read path matches the claim, or so the claim matches the read path.

Rubric.

Lesson Summary

CAP says that during a partition you cannot guarantee linearizability and an answer from every non-failed node. PACELC adds the healthy-network choice between latency and freshness. Linearizability orders operations in real time. Sequential consistency keeps a total order without that real-time edge. Causal consistency keeps cause before effect. Eventual consistency promises convergence after writes stop, and an SLO is extra. Session guarantees cover one caller: read-your-writes and monotonic reads are what the LSN pin actually built.

Payments on one shard primary, with sync commit and fail-closed partitions, can be described as linearizable for clients who use that primary. Feeds can be eventual with a causal edge for replies. Carts need session guarantees. SQL isolation stays on the node that runs the transaction. The next lesson accepts a weaker global story on purpose: a saga commits locally in several databases and compensates, so intermediate states are visible. That is Distributed Transactions and the Saga Pattern.

Further Reading

• Seth Gilbert and Nancy Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services," SIGACT News, 2002.
• Eric Brewer, "Towards Robust Distributed Systems," PODC 2000 keynote.
• Daniel Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design," IEEE Computer, 2012 (PACELC).
• Maurice Herlihy and Jeannette Wing, "Linearizability: A Correctness Condition for Concurrent Objects," ACM TOPLAS, 1990.
• Leslie Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs," 1979.
• Douglas Terry and colleagues, "Session Guarantees for Weakly Consistent Replicated Data," 1994.
• Giuseppe DeCandia and colleagues, "Dynamo: Amazon's Highly Available Key-value Store," 2007, for sloppy quorums and hinted handoff.
• PostgreSQL: Isolation Levels, ACID Principles, Streaming Replication.
• This module: Database Replication and Consistency, Distributed Transactions and the Saga Pattern.