CAP Theorem & PACELC

Key Points

• "Pick two of C, A, P" is a misquote. Partitions happen — P is non-negotiable. The actual choice is C vs A during a partition.
• PACELC (Abadi, 2012) completes the picture: during a Partition, A vs C; Else (no partition), L (latency) vs C (consistency). The L-vs-C trade is what you actually live with day to day.
• CP systems block writes/reads to preserve consistency under partition (HBase, MongoDB default, sync-replicated SQL). AP systems stay available with stale or divergent state and reconcile later (Cassandra, DynamoDB, Cosmos at lower levels).
• Cosmos DB's five levels — Strong, Bounded Staleness, Session, Consistent Prefix, Eventual — span the consistency lattice. Pick per dataset; the default is Session.
• Linearizable, sequential, causal, read-your-writes, monotonic-reads, bounded-staleness, eventual — the consistency lattice every senior should be able to define.
• Senior framing: decide what each consumer of the data tolerates. Most user-facing apps want read-your-writes / Session; financial paths want strong; activity feeds tolerate eventual.
• Misconceptions to bust: "NoSQL = eventual" (false), "ACID is opposite of CAP" (different axis), "2PC gives you CA" (no — 2PC blocks during partition).

Concepts (deep dive)

CAP — the precise statement

Brewer (2000) conjectured, Gilbert and Lynch (2002) proved: a distributed data store cannot simultaneously provide linearizability, availability, and partition tolerance in the face of a network partition.

Read it carefully:

• C = linearizability (single global order with real-time guarantees), not "any consistency".
• A = every non-failing node returns a non-error response in bounded time — even if the answer is stale would mean violating C.
• P = the system continues to operate despite arbitrary message loss/delay between nodes.

The misinterpretation "pick 2 of 3" suggests CA is achievable. It isn't — in any system whose nodes communicate over a network, partitions are possible, so the choice is forced: under a partition, you pick A (return possibly stale data) or C (refuse to answer). P is given.

CP vs AP

Partition occurs:
                     ┌────────┐         X         ┌────────┐
                     │ Node A │  ─ ─ ─ X ─ ─ ─ ─  │ Node B │
                     └────────┘         X         └────────┘

CP behavior: minority side stops accepting writes (and possibly reads).
              Consistency preserved; availability sacrificed on the minority.

AP behavior: both sides keep accepting writes / serving reads.
              Availability preserved; state diverges; reconciliation later.

CP systems: HBase, MongoDB (default config with majority writes), traditional RDBMS with synchronous replication, Spanner-class systems, ZooKeeper, etcd.

AP systems: Cassandra (tunable; defaults AP-leaning), DynamoDB at low consistency levels, Cosmos DB at Eventual or Consistent Prefix, Riak, Couchbase.

The "AP system" label hides nuance — most AP systems offer tunable consistency: per-operation R + W > N choices in Cassandra/Dynamo flip individual operations toward CP semantics.

PACELC — the complete picture

Daniel Abadi's 2012 extension. The core insight: CAP only kicks in during a partition. What about the 99.9% of the time the network is healthy? PACELC adds that axis:

PACELC = During Partition: A or C ?
         Else (no partition): L (latency) or C (consistency) ?

Categorization:

The senior insight: the L-vs-C trade is the day-to-day reality. Partitions are rare; the latency cost of strong consistency is paid every read and every write, forever.

The consistency lattice

From strongest to weakest:

Strict / Linearizable
        │
        │  weakening: drop real-time order
        ▼
Sequential
        │
        │  weakening: per-key/per-thread order only
        ▼
Causal
        │
        │  weakening: only causally-related ops are ordered
        ▼
Session-scoped guarantees:
   Read-your-writes          (you see your own writes)
   Monotonic reads           (reads don't go backward in time)
   Monotonic writes          (your writes apply in order)
   Writes-follow-reads       (writes after a read see at least what was read)
        │
        │  weakening: bounded only by lag
        ▼
Bounded Staleness        (≤ K versions or ≤ T seconds behind)
        │
        ▼
Eventual                 (will converge if writes stop)

Definitions to know cold:

• Linearizable: there exists a single total order of operations consistent with real time. As if ops happened atomically at some moment between invocation and response.
• Sequential: there exists a total order, but it doesn't need to match real time.
• Causal: if A happens-before B (causally), every observer sees A before B. Concurrent operations may be seen in different orders.
• Read-your-writes: after you write X, your subsequent reads return X (or newer).
• Monotonic reads: once you've read version V, you never see V-1 again.
• Bounded staleness: reads lag at most K versions or T time behind the latest.
• Eventual: given no new writes, all replicas converge.

Cosmos DB's five levels mapped

Cosmos Level         Lattice mapping
────────────────────────────────────────────────────────
Strong               Linearizable
Bounded Staleness    Strong but lag-bounded; defaults K=100k or T=5min
Session              Read-your-writes + monotonic reads (per session token)
Consistent Prefix    Reads see writes in order, but with arbitrary lag (no gaps)
Eventual             Convergence only

Default = Session. It's the sweet spot: from your own session you see your own writes, and reads never go backwards. Across sessions the global state can be slightly stale. Most user-facing apps fit here cleanly.

Pick per dataset, not per app: - Account balance / inventory hand-out → consider Bounded Staleness or Strong. - User-facing CRUD → Session. - Activity feed / analytics → Eventual.

Cross-link: see Cosmos DB Modes — Deep and Multi-Region Replication.

PACELC by .NET-relevant store

This table is the senior's mental cheat sheet. When a system asks "what consistency does X give us?" the answer is in the PACELC class plus the configured option.

Worked decision: should my service be C or L?

Senior framework — ask per consumer of the data:

1. What does the consumer DO with this read?
   - Make an irreversible decision (charge a card, ship a package)?  → strong
   - Show a UI?                                                       → session/RYW
   - Drive a metric or report?                                        → eventual
   - Render a list or feed?                                           → eventual or session

2. What's the cost of seeing a stale value?
   - Money lost / customer harmed?                                    → strong
   - Mild confusion / refresh-and-retry?                              → eventual

3. What's the cost of unavailable / blocked reads under partition?
   - Total business stop?                                             → AP
   - Tolerable for short windows?                                     → CP

4. What latency budget applies?
   - p99 < 50ms across regions?                                       → eventual / Session
   - p99 < 200ms acceptable?                                          → bounded staleness

Most interactive apps: Session for the main read path; strong only on the decision boundary (place order, deduct balance). The trick is recognizing the decision boundary.

Read-your-writes — the practical sweet spot

User submits form  ──►  POST /orders  ──►  primary writes  ──►  return 201

User clicks "My Orders" 200ms later
   ↓
Read goes to a regional replica ──► may not have the new order yet
   ↓
User: "Where's my order?? It said success!"

Read-your-writes (RYW) prevents this. Implementation options:

• Cosmos Session token — return the session token from write, send on next read; SDK routes to a replica that's caught up.
• Sticky read after write — for N seconds after a write, route the user's reads to the primary.
• Causality token — a Lamport-style version returned by write, passed by read; replica blocks until caught up.
• Increase consistency for the affected paths — Bounded Staleness or Strong selectively.

In practice, Session-level RYW handles most user-visible cases. Use stronger only where money or correctness is on the line.

Misconceptions to bust

"NoSQL = eventual." False. Cosmos has Strong; MongoDB defaults to majority writes (CP-leaning); HBase is CP. The flexibility of NoSQL is tunable consistency, not eventual-only.

"ACID is the opposite of CAP." Different axis. ACID is about transactional behavior on a single node (or a system that simulates one). CAP is about behavior across nodes during partitions. A linearizable distributed DB is both ACID and CP. An AP NoSQL store is neither ACID-strong nor CP — but it can offer per-key atomicity.

"Two-phase commit gives you CA." No. 2PC is a blocking protocol — when a participant disappears mid-protocol, the coordinator (or other participants) block, sacrificing availability. 2PC is firmly in the CP camp.

"Spanner claims CA — is that true?" Spanner's external consistency is almost CP/EC: linearizable globally via TrueTime + Paxos. Google's claim of "effectively CA" leans on the assertion that Google's network rarely partitions in practice. Theoretically still CP; practically very high availability because partitions are engineered to be rare.

"Strong consistency is always better." No. It costs cross-region RTT on every operation. Most apps don't need it everywhere; pinning Cosmos to Strong account-wide is one of the most expensive default mistakes a senior reviewer flags.

Linearizability vs serializability

Often confused. Both are "strong", but different scopes:

• Linearizability is about single-object operations: there exists a total order consistent with real time.
• Serializability is about transactions on multiple objects: the result is equivalent to some serial execution of the transactions.
• Strict serializability = serializable + linearizable: serial order matches real time.

A relational DB at SERIALIZABLE isolation level on a single node is strictly serializable. A distributed DB can be serializable (transactions appear atomic) without being linearizable (real-time order may be violated). Spanner provides strict serializability — that's the gold standard.

Where 2PC and Saga fit

• 2PC (two-phase commit): CP, blocks under partition. Not used at scale across services.
• Saga (compensating transactions): AP — each step commits locally; failures compensate previous steps. Eventually consistent. Cross-link: see Saga Compensation Patterns — Deep.

The shift from 2PC to Saga in microservices is fundamentally a CAP choice: trade global atomicity for availability under partition.

How it works under the hood

Linearizable read in a CP system

Client                  Leader                Followers
──────                  ──────                ─────────
read X       ──►  serve from leader's log,
                  but only if leader is sure
                  it's still leader (lease check
                  via heartbeat / quorum read).

If lease unsure:
                  send read-index probe         confirm via majority quorum
                  ──────────────────────► ────────────────────────────────►
                  ◄──────────────────────────────────────────────────────
                  return X with confidence

The "lease confirmation" is what makes linearizability expensive — every read pays at least one round-trip to confirm the leader hasn't been deposed.

Eventual consistency convergence

Time   Replica A           Replica B           Replica C
────   ─────────           ─────────           ─────────
t=0    write X=5          (idle)               (idle)
t=1    replicate ──►       receive             (idle)
t=2    write X=7          (idle)               receive
t=3                        replicate ──►       X=5
t=4                                            X=7
t=5    convergence: all replicas agree X=7 (assuming LWW with t=2 latest)

If a concurrent write happens at t=1 to B, the convergence requires a deterministic merge function — LWW, vector clocks, or CRDT. Cross-link: see Multi-Region Replication.

Cosmos Session token mechanics

Client SDK keeps the most-recent session token per partition.

Write:  primary commits → returns token "0:1#1234"  (LSN)
        SDK stores token.

Read:   SDK sends "x-ms-session-token: 0:1#1234"
        Replica:
          - if my LSN ≥ 1234, serve immediately
          - else, wait for replication / forward to a caught-up replica

That's how Session gives RYW without paying full Strong cost on every read.

TrueTime in Spanner — making CP fast

Every transaction commits at timestamp T_commit.
TrueTime API: TT.now() returns interval [earliest, latest].

To commit safely:
   1. Pick T_commit > TT.now().latest  (so the timestamp is after all clocks)
   2. Wait until TT.now().earliest > T_commit
      (so all clocks agree the timestamp is in the past)
   3. Reply commit

The "commit wait" is typically 5-10ms — dwarfed by Paxos latency, so net cost is small.

TrueTime is engineered (atomic clocks + GPS in every datacenter) — the rest of us simulate it loosely with HLC (Hybrid Logical Clocks).

Code: correct vs wrong

❌ Wrong: defaulting Cosmos to Strong account-wide

var client = new CosmosClient(connStr, new CosmosClientOptions
{
    ConsistencyLevel = ConsistencyLevel.Strong   // pays inter-region RTT on every op
});

Pays the full latency tax even for read-only feeds and analytics queries.

✅ Correct: account at Session, opt down per query

var client = new CosmosClient(connStr, new CosmosClientOptions
{
    ConsistencyLevel = ConsistencyLevel.Session   // default; cheap RYW
});

// For an analytics read where staleness is fine:
await container.ReadItemAsync<Telemetry>(id, partition,
    new ItemRequestOptions { ConsistencyLevel = ConsistencyLevel.Eventual });

// For a balance check before committing a charge:
await container.ReadItemAsync<Account>(id, partition,
    new ItemRequestOptions { ConsistencyLevel = ConsistencyLevel.BoundedStaleness });

You can opt down (weaker than account default) per request; opting up requires raising the account-level setting.

❌ Wrong: write then immediately read from replica without session token

await container.UpsertItemAsync(order);            // primary
var fresh = await container.ReadItemAsync<Order>(  // some replica
    order.Id, partition);
// May return null or older — RYW violated

✅ Correct: pass the session token

var resp = await container.UpsertItemAsync(order);
var token = resp.Headers.Session;

var fresh = await container.ReadItemAsync<Order>(order.Id, partition,
    new ItemRequestOptions { SessionToken = token });
// SDK routes / waits until the read replica is caught up

✅ Correct: Azure SQL geo-replication (async, PA/EL on replicas)

// Primary connection — strong within region (PC/EC for the region)
var primary = new SqlConnection("Server=tcp:primary.database.windows.net;...");

// Read-only routing — uses async replicas
var readonlyConn = new SqlConnection(
    "Server=tcp:primary.database.windows.net;ApplicationIntent=ReadOnly;...");

ApplicationIntent=ReadOnly opts into the async replica, accepting RPO seconds for lower load on the primary.

✅ Correct: choosing per consumer

public class OrderService
{
    // Decision boundary: must read fresh balance.
    public async Task<Result> PlaceOrder(OrderRequest req) =>
        await _accounts.ReadStrong(req.AccountId)         // ← strong here
            .Pipe(charge => Charge(charge, req));

    // UI feed: stale OK.
    public async Task<List<OrderSummary>> GetMyOrders(string userId) =>
        await _orders.ReadEventual(userId);                // ← eventual here
}

The senior anti-pattern is using one consistency level for the whole app. It's per-path.

Design patterns for this topic

Pattern 1 — "Session-by-default, strong-on-decision"

• Intent: Session consistency for UI; Strong only at the irreversible-decision boundary.

Pattern 2 — "Read-your-writes via session token"

• Intent: preserve self-visibility without paying full Strong cost.

Pattern 3 — "Sticky-read-after-write window"

• Intent: for N seconds after a write, route reads to primary.

Pattern 4 — "Bounded staleness for near-real-time"

• Intent: dashboards / hot reads that can lag by K updates or T seconds.

Pattern 5 — "Pick consistency per dataset, document why"

• Intent: every store has a written rationale; future-you remembers the trade.

Pattern 6 — "PACELC scoring sheet"

• Intent: when adding a data store, fill in P? E? L? C? before committing to it.

Pros & cons / trade-offs

When to use / when to avoid

• ✅ Use Session as the default for user-facing apps.
• ✅ Use Strong / Bounded Staleness at decision boundaries (charge, deduct, allocate).
• ✅ Use Eventual for telemetry, analytics, activity feeds.
• ✅ Use Saga for cross-service workflows where 2PC is impractical.
• ✅ Use the PACELC table when picking a new store; write down the class.
• ❌ Avoid defaulting any store to Strong without measuring.
• ❌ Avoid "we need consistency" without specifying which consistency.
• ❌ Avoid 2PC across microservices.
• ❌ Avoid treating ACID and CAP as opposites — they aren't.
• ❌ Avoid assuming partitions are rare enough to ignore — cloud networks blip daily.

Interview Q&A

Q1. State CAP precisely without the "pick 2 of 3" misquote. In a distributed data store under a network partition, you cannot simultaneously preserve linearizability and availability. P is given (partitions happen); the choice is C-vs-A during a partition.

Q2. Why is P not really optional? Any system whose nodes communicate over a network is subject to partitions — packet loss, NIC failures, rack outages, region issues. Saying "I'll skip P" means assuming a partition will never occur, which is unsafe.

Q3. What's PACELC and what does it add over CAP? PACELC adds the no-partition axis: Else (no partition) = Latency vs Consistency. Captures that you live with the L-vs-C trade 99.9% of the time, while CAP only kicks in during rare partitions.

Q4. Read-your-writes — what does the system need to give you? A guarantee that after you've written X, your subsequent reads see X or newer. Implemented via session tokens, sticky-read windows, causality tokens, or stronger consistency on the affected paths.

Q5. Cosmos DB's five consistency levels — which is the default and why? Session is the default. It gives read-your-writes and monotonic reads per session, at much lower latency than Strong. Most user-facing apps need exactly that.

Q6. Strong consistency vs serializability vs linearizability — define each. - Linearizability: single-object total order consistent with real time. - Serializability: transactions on multiple objects appear in some serial order. - Strict serializability: both — the serial order matches real time. Spanner's guarantee.

Q7. Two-phase commit and CAP — what's the relationship? 2PC is CP-leaning: during a partition where a participant or coordinator is unreachable, the protocol blocks rather than risk inconsistency, sacrificing availability.

Q8. Spanner claims CA — is that true? Theoretically Spanner is CP (it's strict serializable, blocks under partition). Google's claim of "effectively CA" rests on the empirical observation that their network rarely partitions thanks to engineered redundancy. The CAP theorem still applies; Spanner just experiences A nearly always because P is engineered to be rare.

Q9. Bounded staleness — what does it bound? Reads lag at most K versions or T time behind the latest committed write. K and T are configured. Lower bounds = closer to Strong (and pay closer to Strong's latency).

Q10. AP system — how is data reconciled? Strategies: Last-Write-Wins (clock-skew sensitive), vector clocks (push to app), CRDTs (deterministic merge), application-level merge, or surfaced conflict feed for human resolution. Cross-link: see Multi-Region Replication.

Q11. "NoSQL = eventual" — true or false? False. NoSQL stores typically offer tunable consistency. MongoDB defaults to majority writes (CP-leaning); Cosmos has Strong; HBase is CP. AP-leaning defaults are common but not universal.

Q12. Linearizability vs sequential consistency? Linearizable: total order matches real time. Sequential: total order exists, but doesn't have to match real time. A sequentially consistent system can return "old" data even after newer is written, as long as the per-thread order is preserved.

Q13. PACELC for Azure SQL DB? PC/EC for the primary; PA/EL for async geo-replicas. Sync replicas (Always On) within region are PC/EC.

Q14. How does session-token-based RYW work in Cosmos? The SDK tracks the latest LSN it has observed (the session token). On reads, the SDK forwards the token; the replica only serves once its own LSN catches up — otherwise it forwards the read or waits.

Gotchas / common mistakes

• ⚠️ "Pick 2 of 3" as the working summary — leads to bad architectural decisions.
• ⚠️ Equating ACID with strong consistency — different axis; a single-node DB can be ACID without being linearizable across partitions.
• ⚠️ Defaulting Cosmos to Strong account-wide — pays cross-region RTT everywhere, forever.
• ⚠️ Assuming partitions are rare in cloud — they happen daily; planning matters.
• ⚠️ Over-spec'ing Strong consistency when Session would do — needless latency tax.
• ⚠️ One consistency level for the whole app — should be per consumer / per data set.
• ⚠️ Forgetting RYW is a session property, not a global one — across sessions you can still see stale.
• ⚠️ Treating LWW as a merge strategy without acknowledging clock skew — cross-link: see Multi-Region Replication.
• ⚠️ 2PC across microservices — blocks; doesn't scale; choose Saga.
• ⚠️ Ignoring the L in PACELC — focusing only on the partition case misses the daily-cost trade-off.
• ⚠️ Confusing linearizability with serializability in interviews — define both crisply.

Further reading

• Brewer: CAP Twelve Years Later (2012)
• Gilbert & Lynch: CAP proof (2002)
• Daniel Abadi: Consistency Tradeoffs in Modern Distributed Database System Design (PACELC)
• Martin Kleppmann: Designing Data-Intensive Applications — chapters 5, 7, 9
• Jepsen analyses — empirical consistency testing of real systems
• Azure Cosmos DB consistency levels
• Google Spanner: TrueTime and external consistency
• Peter Bailis: Highly Available Transactions
• MS Learn: Microservices data considerations