Distributed Systems Reliability Fundamentals

Every reliability pattern in this course — retries, circuit breakers, multi-region failover, replication — eventually runs into one unavoidable fact: a distributed system cannot simultaneously guarantee that every node sees the same data and that every node always answers, once the network between them stops behaving. That fact has a name, the CAP theorem, and a more useful successor, PACELC, that covers the 99.9% of the time nothing is actually broken. This page treats both not as trivia to memorize but as a decision framework: every time you pick a database, a replication mode, or a consistency setting, you are choosing which failure mode your service will show its users. Get that choice deliberate instead of accidental, and half of what looks like "the database is being weird" in a postmortem stops happening in the first place.

Why every reliability decision here starts with a theorem

☺ Like you're 10: This isn't abstract computer-science trivia — it's the reason two "correct" databases can behave completely differently the moment the network hiccups, and why that's not a bug in either of them.

Most of this course treats reliability as something you build toward with retries, timeouts, redundancy, and good on-call process — see reliability patterns for the application-layer toolkit. This page is one level down: it's about the physics of the problem those patterns are compensating for. Any service whose data lives on more than one machine — which, at any real scale, is every service — has to answer a question it usually never states out loud: when a network link between two of your own nodes stops working, or slows down enough to look like it stopped working, what should the system do? There are only two families of answer, and picking between them isn't a one-time architectural nicety. It's a decision that shows up, concretely, in your achievable SLOs (SLIs, SLOs & error budgets), in what your on-call runbook tells someone to do during a region split, and in whether a payment can silently double-apply. Get the theorem straight first, and the rest of this page is just working out its consequences.

The CAP theorem, precisely

☺ Like you're 10: Three properties sound like they should all be possible at once. They're not — and the theorem is the proof of exactly why not, the moment a network cable gets cut.

Eric Brewer, then at UC Berkeley and Inktomi, first stated the idea as a conjecture in a 2000 PODC keynote, "Towards Robust Distributed Systems." Seth Gilbert and Nancy Lynch of MIT formalized and proved it two years later in a 2002 paper for ACM SIGACT News, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services." The theorem names three properties a distributed data store might provide, and proves you cannot have all three at once, for any system that spans more than one node connected by an unreliable network — which is every system that spans more than one node, because no network is perfectly reliable.

Consistency, Availability, and Partition tolerance, defined precisely

Consistency here means linearizability: every read returns the result of the most recent completed write, as if there were only a single copy of the data and all operations happened in some real, global order. This is a much stronger and narrower claim than the "C" you may already know from ACID transactions — a distinction important enough that it gets its own warning below. Availability means every request to a non-failing node receives a response, in bounded time — not necessarily the right response, just a response, rather than a timeout or an error. Partition tolerance means the system keeps operating even when the network drops or arbitrarily delays messages between nodes — not just a severed cable, but anything that makes nodes unable to hear each other promptly: a saturated link, a garbage-collection pause long enough to miss heartbeats, a misconfigured security group, a transatlantic route flapping.

Why "pick two of three" is the wrong way to read it

☺ Like you're 10: You don't get to vote partition tolerance off the island — the network will partition whether you planned for it or not, so the only real vote is what happens when it does.

CAP is almost always summarized as "pick any two of Consistency, Availability, Partition tolerance," and that phrasing has caused more design mistakes than almost any other piece of distributed-systems folklore. It implies three symmetric options — CA, CP, AP — as if "CA" (consistent and available, but not partition-tolerant) were a real, chooseable design. It isn't, for any system with more than one node talking over a real network. Partition tolerance isn't a feature you can decline; it's a property of physical reality that your system either handles gracefully or fails at ungracefully the first time it happens. A single-node database is trivially CA because it has no network to partition — the instant you add a second node for redundancy, durability, or scale, you've re-entered CAP's territory whether you meant to or not, and "CA" quietly becomes "C, until the network partitions, and then undefined behavior," which is another way of saying "AP or CP, decided by accident during your worst incident instead of on purpose beforehand."

So the theorem's real, practical content compresses to one sentence: partition tolerance is mandatory for any real distributed system, which means the only genuine design choice is what you sacrifice when a partition happens — consistency, or availability. Everything a database vendor calls "CP" or "AP" is really answering that one question, and it's exactly the question this page's two worked examples — a payments ledger and a social feed — answer differently, on purpose, for good reasons.

PACELC: what happens the other 99.9% of the time

☺ Like you're 10: CAP only tells you what happens on the rare day the hallway is blocked. PACELC also tells you what you're quietly paying every single normal day the hallway is wide open.

CAP's biggest practical gap is that partitions, while inevitable eventually, are rare in any given hour — most requests happen with the network working fine. CAP has nothing to say about that overwhelming majority of traffic, yet replication mode clearly still matters then too: a system doing synchronous cross-region replication for strong consistency pays a real, constant latency tax on every single write, partition or not. Daniel Abadi, then at Yale, named and formalized this gap in a 2010 blog post and a fuller 2012 IEEE Computer paper, "Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Not Enough." His extension is PACELC, read "pass-elk": if there is a Partition (P), the system must trade off Availability against Consistency (A vs C); Else (E) — the normal, non-partitioned case — it must trade off Latency against Consistency (L vs C). A full PACELC classification names one letter from each half, giving four possible combinations: PA/EL, PA/EC, PC/EL, and PC/EC.

Classifying real systems against this grid makes the abstraction concrete fast:

The dial in practice: quorums and consistency levels

☺ Like you're 10: "Strong" and "eventual" consistency aren't the only two settings — most real systems let you dial a number, and the math behind that dial is simpler than it looks.

Two different machines for buying consistency

It's worth keeping two distinct mechanisms apart, because they fail differently and cost differently. Dynamo-style quorums — Cassandra, Riak, DynamoDB's underlying model — let every individual read or write choose how many of N replicas must participate: a write quorum of W nodes, a read quorum of R nodes. The standard rule of thumb, used across this whole family of systems, is that if W + R > N, every possible read quorum and write quorum are guaranteed to overlap by at least one replica, so a read is guaranteed to see the most recent acknowledged write. This isn't full linearizability on its own — the overlapping replica has to be identified as the newest via a timestamp or version vector, and concurrent writes still need conflict resolution — but it's the practical rule Cassandra's, Riak's, and DynamoDB's quorum reads are built on, and it composes cleanly with the fault tolerance you get for free: with N=3, W=2, R=2, the system tolerates exactly one unreachable replica while still guaranteeing overlap.

Consensus-based replication — Raft, Paxos, and the systems built on them (etcd, ZooKeeper, Consul, CockroachDB, Spanner) — works differently: a write isn't considered committed until a strict majority of nodes (> N/2) durably persist it in the same total order, decided by an elected leader. This buys real linearizability without any application-level conflict resolution, because there's never more than one accepted history to reconcile — but it means every write pays at least one network round trip to a majority of nodes, and the cluster becomes read-only (or fully unavailable, for writes) the instant it can't reach a majority, which is precisely the PC choice made explicit.

Dynamo-style quorum math (Cassandra, Riak, DynamoDB-style):
  N = 3   (replication factor)
  W = 2   (nodes that must ack a write)
  R = 2   (nodes that must respond to a read)

  W + R = 4  >  N = 3   ->  read and write quorums always overlap
  tolerates exactly 1 replica down or unreachable, on either path

Consensus quorum math (Raft/Paxos: etcd, CockroachDB, Spanner):
  N = 5 nodes  ->  majority = floor(N/2) + 1 = 3
  a write commits only once 3 of 5 nodes have durably logged it
  losing 3 of 5 nodes (no majority left) = no new writes, at all,
  until enough nodes rejoin — this is PC, made concrete

Tunable consistency in real systems

Cassandra exposes the Dynamo-style dial directly as a per-query consistency level: ONE (fastest, weakest), QUORUM (a majority of replicas, floor(N/2)+1), LOCAL_QUORUM (quorum within one datacenter only — the workhorse setting for multi-region Cassandra, since it avoids a wide-area round trip on every request), and ALL (strongest, least available — a single unreachable replica fails the whole request).

cqlsh> CONSISTENCY QUORUM;
Consistency level set to QUORUM.

cqlsh> SELECT balance FROM ledger.accounts WHERE account_id = 4471;
-- On a keyspace with replication_factor: 3, QUORUM requires
-- 2 of 3 replicas to agree before this read returns.

cqlsh> CONSISTENCY LOCAL_QUORUM;
-- Majority within the local datacenter only — avoids a cross-region
-- round trip on every request. The usual default for multi-DC clusters.

DynamoDB exposes the same idea as a single boolean, with one important, frequently-missed asterisk:

// Base table or a Local Secondary Index: strongly consistent
// reads are available, but only within the table's home region.
GetItem({
  TableName: "Ledger",
  Key: { accountId: { S: "4471" } },
  ConsistentRead: true        // costs 2x the read capacity of an eventual read
})

// Global Secondary Indexes never honor ConsistentRead — GSI reads
// are always eventually consistent, no exceptions.
// Global Tables (cross-region replicas) are always eventually
// consistent across regions, regardless of ConsistentRead.

Azure Cosmos DB takes the dial furthest, exposing five named levels along the same spectrum rather than a binary switch: Strong (linearizable — PC/EC), Bounded Staleness (reads lag writes by at most K versions or T time), Session (the default — a single client always sees its own writes, other clients may lag), Consistent Prefix (reads never see writes out of order, but may be behind), and Eventual (no ordering guarantee at all, lowest latency). Confirm the exact current names and guarantees against Microsoft's own documentation before you design against them, since managed-service consistency offerings are exactly the kind of detail vendors refine over time — but the shape of the idea, a named spectrum rather than one on/off switch, is the durable lesson.

Case study: a payments service that chooses consistency

☺ Like you're 10: When the thing you're tracking is money, being unavailable for a minute is annoying. Being wrong about someone's balance is a headline.

Consider a ledger service that debits and credits account balances. The failure mode that's genuinely unacceptable here is two concurrent requests each seeing a stale balance and both succeeding — a classic double-spend, or an overdraft nobody actually approved. That single constraint pulls the whole design toward the CP corner of the PACELC grid, and the consequences are concrete, not abstract.

What CP looks like in the actual write path

The ledger's writes go through a consensus protocol — Raft or Paxos, whether hand-rolled or via a distributed SQL engine like CockroachDB or Spanner — so a balance change isn't considered committed until a majority of replicas have durably logged it, exactly the mechanism from the section above. When a network partition splits the cluster and a minority side can't reach a majority, that side does not guess: it rejects the write outright, fails closed, and returns an error rather than an approximate answer.

function commit_balance_change(account_id, delta, request_id):
    entry = LedgerEntry(account_id, delta, request_id)
    acked = raft_log.append(entry)     # blocks until a majority of
                                        # replicas durably log the entry
    if not acked:                      # no majority reachable — partition
        return Error(503, "retry")     # fail CLOSED: no partial, no guess
    apply(entry)
    return Success(new_balance)

# request_id doubles as an idempotency key: replaying the same
# request after a client-side timeout returns the prior committed
# result instead of applying the delta a second time.

That idempotency key is doing load-bearing work: a CP system that fails closed will generate more client-side timeouts and retries than an AP one, precisely because it sometimes refuses to answer rather than answer wrong — so the retry path has to be provably safe, using the same idempotency-key discipline covered in reliability patterns for exactly this reason. Cross-service money movement — debiting a wallet in one service while crediting an order in another — typically layers a saga with compensating transactions on top of this per-service consistency, rather than a single distributed transaction spanning both; that pattern deserves its own treatment in database reliability engineering.

The SLO consequence is the part teams most often get wrong: a CP ledger has a hard ceiling on availability during any partition long enough to break majority, no matter how good the on-call response is — because the system is designed to refuse traffic in that window rather than serve it wrong. Setting a 99.99% availability SLO on a system engineered to fail closed during every partition, without accounting for that, is setting an SLO the architecture itself cannot hit; see SLIs, SLOs & error budgets for how that ceiling should be reflected in the number you actually commit to, and multi-region & multi-AZ architecture for how quorum placement across regions changes how often that ceiling gets tested.

Case study: a social feed that chooses availability

☺ Like you're 10: Nobody's balance sheet gets audited over a like count that's three seconds behind. An error page over a stale number is the actual bad outcome here, and it's backwards from the payments case.

Now consider the opposite service: a social feed's like counter, view count, and ranked timeline. Here the failure mode that's genuinely unacceptable inverts — a user seeing an error page, or a "this feature is temporarily unavailable" banner, is a worse product outcome than that same user seeing a like count that's a few seconds stale, or a feed that hasn't fully caught up with a post made ninety seconds ago in another region. That constraint pulls the design toward the AP corner, and the engineering choices that follow look almost like a mirror image of the ledger's.

What AP looks like in the actual write path

Counters and feed writes go to an AP-family store — DynamoDB or Cassandra are the standard choices, both descended from the original Amazon Dynamo design (DeCandia et al., SOSP 2007, "Dynamo: Amazon's Highly Available Key-value Store") that coined the phrase "always writable" for exactly this workload. During a partition, both sides keep accepting writes locally rather than blocking, and the conflict-resolution problem this creates is solved by choosing operations that are safe to apply out of order and more than once.

// A commutative, associative increment — safe to apply on both
// sides of a partition and merge afterward with no lost update:
UpdateItem({
  TableName: "PostCounters",
  Key: { postId },
  UpdateExpression: "ADD likeCount :one",
  ExpressionAttributeValues: { ":one": 1 }
})

// A last-writer-wins field (e.g. a post's caption edit) instead
// needs an explicit timestamp or version to pick a winner on merge —
// unlike the counter above, this one CAN silently lose an update.

The counter increment above is a small example of a CRDT (conflict-free replicated data type): because addition is commutative and associative, two regions can each apply their own increments independently during a partition and arrive at the same total once they reconcile, with no manual conflict resolution and no lost update. Not every field is this well-behaved — a caption edit needs an explicit last-writer-wins timestamp or a version vector, and genuinely conflicting edits (two users editing the same shared caption at once) need either a real merge function or accepting that one edit silently wins, which is a product decision, not just an engineering one.

The user-experience gap this design opens — "I just posted, why don't I see my own post yet" — gets closed with a much cheaper trick than strong consistency: session consistency (sometimes called read-your-writes), where a client is routed back to the same region or replica it just wrote to for some short window, so the one person who'd actually notice staleness doesn't, while everyone else still reads from whichever nearby replica answers fastest. This is exactly the Session level in Cosmos DB's spectrum above, and it's why "eventually consistent" in production usually means "consistent within tens to low-hundreds of milliseconds for everyone, and consistent immediately for the person who just wrote it" rather than the unbounded staleness the term technically permits.

Making the failure mode an explicit engineering decision

☺ Like you're 10: The whole point of learning the theorem is so nobody on your team finds out which failure mode a service has by watching it happen live, during an incident, instead of reading it off a design doc beforehand.

The practical output of everything above is a single question that belongs in every design review and every production readiness review for a service that replicates data across more than one node: "when this service's replicas can't reach each other, what happens to a request — does it fail, or does it lie?" Teams that never ask this find out the answer during their worst incident, usually phrased afterward as "we didn't realize the database would do that." Teams that ask it upfront get to choose, in advance, with the business context to choose correctly — a ledger, an inventory count that prevents overselling, or an authentication check earns a CP answer nine times out of ten; a like count, a view count, a recommendation feed, or a non-authoritative cache earns an AP answer just as often, and forcing either one onto the wrong workload is its own reliability bug.

This decision doesn't stay theoretical once you're operating the system. It shows up directly in how you plan multi-region topology — a CP quorum's placement across regions determines exactly which region failures it can survive without losing majority, covered in multi-region & multi-AZ architecture — and in your actual disaster-recovery posture, where "AP with eventual reconciliation" and "CP with a hard failover runbook" imply very different recovery-point objectives, covered in disaster recovery & business continuity. It also belongs on the same page as your error budget: a CP system's partition-time unavailability should be modeled into the SLO you set, not discovered as an SLO miss after the fact.