Deep dive — beyond the basics

Distributed Systems
Complete Reference

Everything beyond the Educative lesson — CAP theorem, PACELC, linearizability, CRDTs, Paxos, Raft, TrueTime, and how real systems like Cassandra, Spanner, DynamoDB, and Kafka apply these concepts.

CAP theorem PACELC Linearizability Serializability Vector clocks Hybrid Logical Clocks CRDTs Paxos Raft Google Spanner Cassandra 2PC
01 — Foundation

CAP Theorem + PACELC

The deeper "why" behind every consistency trade-off

CAP theorem (Brewer, 2000)

In the presence of a network Partition, a distributed system can guarantee either Consistency or Availability — but not both simultaneously.

Consistency C Availability A Partition P CP AP CA
CP systems — choose Consistency over Availability during a partition.
When nodes can't communicate, the system refuses to respond rather than return potentially stale data.
Examples: HBase, Zookeeper, etcd, Redis (in cluster mode), MongoDB (default).
Use when: correctness is non-negotiable — banking, leader election, configuration.
PACELC theorem (Abadi, 2012) — the full picture

CAP only covers the partition case. PACELC extends it: If Partition → choose C or A. Else (normal operation) → choose Latency or Consistency. Most real systems trade latency for consistency even without partitions.

System Partition behaviour Normal behaviour Classification
DynamoDB Prefers Availability Prefers Latency (async replication) PA/EL
Cassandra Prefers Availability Tunable (ONE→ALL) PA/EL
Google Spanner Prefers Consistency Prefers Consistency (TrueTime) PC/EC
Zookeeper Prefers Consistency Prefers Consistency PC/EC
MongoDB Prefers Consistency Prefers Latency PC/EL
02 — Consistency Precision

Linearizability vs Serializability

Two terms often confused — they mean very different things

Linearizability

A single-object guarantee. Every operation appears to take effect atomically at some point between its invocation and completion. The system behaves as if there's one copy of the data. Also called "atomic consistency" or "strong consistency."


Key property: real-time ordering is preserved. If operation A completes before operation B starts, B must see A's result.

Serializability

A multi-object / transaction guarantee. Concurrent transactions produce a result equivalent to some serial (one-at-a-time) execution. Does NOT require real-time ordering — a "serializable" execution might look like transactions ran in the past.


Key property: used in databases (SQL ISOLATION LEVEL SERIALIZABLE). Weaker than linearizability in terms of time.

Strict Serializability = Linearizability + Serializability

The strongest guarantee: transactions appear to execute serially AND in real-time order. Google Spanner provides this. Most systems provide one or the other, not both.

Why the confusion?

Both terms use the word "consistency" in conversation. The difference: linearizability is about individual reads/writes on one object. Serializability is about transactions across multiple objects. A bank transfer (debit account A, credit account B) needs serializability. Reading the latest balance needs linearizability.

Isolation levels (weakest → strongest)

Level Prevents Still allows Real system
READ UNCOMMITTED Nothing Dirty reads, phantoms, lost updates Rarely used
READ COMMITTED Dirty reads Non-repeatable reads, phantoms PostgreSQL default
REPEATABLE READ Dirty + non-repeatable reads Phantom reads MySQL InnoDB default
SNAPSHOT ISOLATION Most anomalies Write skew CockroachDB, Spanner
SERIALIZABLE All anomalies — PostgreSQL (explicit)
03 — Time in Distributed Systems

Clocks: Lamport → Vector → HLC

How distributed systems reason about time without a global clock

Lamport Clocks (1978)
Each process keeps a counter. On send: increment and attach. On receive: take max(local, received) + 1. Gives a partial ordering — if A → B then LC(A) < LC(B). But LC(A) < LC(B) does NOT mean A → B. Can't detect concurrency.
Vector Clocks (Fidge/Mattern, 1988)
Each process keeps a vector of counters (one per process). On send: increment own slot, attach full vector. On receive: element-wise max + increment. Now: A → B iff VC(A) < VC(B) component-wise. Concurrent if neither dominates. Detects concurrency — used in Dynamo, Riak.
Version Vectors (different from vector clocks!)
Similar structure but track data versions, not event causality. Used to detect conflicts in replicated data. DynamoDB uses version vectors internally. The difference: vector clocks timestamp events; version vectors version data objects.
Hybrid Logical Clocks — HLC (Kulkarni et al., 2014)
Combines physical time (wall clock) with logical time. Tracks the maximum observed physical time + a logical counter for same-millisecond events. Gives causality tracking while staying close to real time. Used in CockroachDB and YugabyteDB.
TrueTime — Google Spanner (2012)
Uses atomic clocks + GPS receivers in every datacenter. Exposes time as an interval [earliest, latest] with bounded uncertainty (~7ms). Spanner commits wait out this uncertainty before returning — guaranteeing that if transaction A commits before B starts, commit_ts(A) < commit_ts(B). Enables globally consistent snapshots.
HLC — how it works 
// Each node tracks: (physical_time, logical_counter)
// abbreviated as (pt, l)

On send message:
  pt = max(pt, wall_clock_now())
  l = l + 1
  attach (pt, l) to message

On receive message with timestamp (msg_pt, msg_l):
  if msg_pt == pt:
    l = max(l, msg_l) + 1
  else if msg_pt > pt:
    pt = msg_pt
    l = msg_l + 1
  else:
    l = l + 1

// Result: stays within a few ms of wall time,
// but still captures causality within the same ms
04 — Conflict-Free Data Structures

CRDTs

Data structures that merge automatically — no coordination needed

The core idea

CRDTs (Conflict-free Replicated Data Types) are data structures designed so that any two replicas can be merged and the result is always the same, regardless of merge order. This makes eventual consistency correct by construction — no conflict resolution logic needed.

State-based CRDTs (CvRDTs)

Nodes periodically exchange their full state. Merge function must be commutative, associative, and idempotent. Example: a G-Counter (grow-only counter) where each node tracks its own increment. Merge = element-wise max. Value = sum of all.

Operation-based CRDTs (CmRDTs)

Nodes broadcast operations (not full state). Operations must be commutative. Smaller messages — just send "increment" instead of full state. Requires reliable delivery (no lost ops). Example: collaborative text editors.

Interactive G-Counter demo

Node A — [clicks add here]
0
Vector: [0, 0]
Node B — [clicks add here]
0
Vector: [0, 0]
Merged value (element-wise max, then sum)
0

Common CRDT types

Type Operations Merge rule Used in
G-Counter increment element-wise max, sum View counters, likes
PN-Counter increment, decrement two G-Counters (P - N) Inventory, balance
G-Set add set union Tags, membership
2P-Set add, remove union of adds ∪ removes Shopping cart (limited)
OR-Set add, remove (any order) unique tags per add Riak, collaborative lists
LWW-Register write with timestamp last-write-wins Profile fields
RGA / LSEQ insert, delete at position unique position IDs Google Docs, Figma
05 — Consensus Algorithms

Paxos + Raft

How distributed nodes agree on a single value despite failures

The consensus problem

Given N nodes, some of which may crash or be unreachable, reach agreement on a single value such that: (1) only proposed values are chosen, (2) only one value is chosen, (3) a node only learns a chosen value. FLP impossibility theorem: no deterministic algorithm can guarantee consensus in an asynchronous system with even one crash failure. Paxos and Raft work around this with timeouts and probabilistic guarantees.

Paxos — phase by phase

Phase 1a: Prepare Phase 1b: Promise Phase 2a: Accept Phase 2b: Accepted Learn
Proposer
sends Prepare(n) to all Acceptors
n
proposal number (must be unique, higher than any seen)
The proposer picks a proposal number n higher than any it has used before, and broadcasts Prepare(n) to a majority of acceptors. It is asking: "Will you promise not to accept any proposal numbered less than n?"
The proposal number is like a ballot number in an election. Higher = more recent. The proposer doesn't send a value yet — just asks for a promise.
Acceptor
replies Promise(n, v_prev)
v_prev
highest-numbered accepted value so far (if any)
If n is the highest proposal number the acceptor has seen, it replies with a Promise — it will ignore any future proposals with number < n. It also includes the value it last accepted (if any), so the proposer can maintain safety.
If any acceptor returns a previously accepted value, the proposer MUST use that value — not its own. This is how Paxos ensures consistency across failed rounds.
Proposer
sends Accept(n, v) to majority
v
its value OR highest v_prev received
Once the proposer receives promises from a majority, it sends Accept(n, v). The value v is either the proposer's own value (if no acceptor returned a prior value), or the highest-numbered previously accepted value from the promises.
Majority quorums are the key. Any two majorities overlap by at least one node — so any two rounds of Paxos share at least one acceptor, preventing contradictory decisions.
Acceptor
accepts if n >= promised_n
Notification
sends Accepted(n, v) to Learners
Each acceptor that receives Accept(n, v) accepts it if n is still the highest proposal number it has promised. It then notifies all Learners of the accepted value.
An acceptor can receive multiple Accept messages from competing proposers. It only accepts the one with the highest proposal number — this is the "last writer wins" of Paxos.
Learner
waits for Accepted from majority
Consensus
value is chosen when majority accepts
A value is "chosen" when a majority of acceptors have accepted the same (n, v). Learners (which may overlap with proposers/acceptors) can now act on this value. Multi-Paxos extends this to a log of values by electing a stable leader to skip Phase 1 for subsequent entries.
Paxos is notoriously hard to implement correctly. Raft was designed specifically to be easier to understand — same guarantees, more prescriptive structure.

Raft — leader election simulator

Node 1
Leader
term: 1
Node 2
Follower
term: 1
Node 3
Follower
term: 1
Node 4
Follower
term: 1
Node 5
Follower
term: 1
Ready. Click "Kill leader" to simulate a leader failure and watch election.
Paxos vs Raft

Paxos: theoretical foundation. Flexible but underspecified — each implementation makes different choices. Used in Chubby (Google), Zookeeper (ZAB variant).


Raft: designed for understandability. Prescribes leader election, log replication, and safety rules explicitly. Used in etcd, CockroachDB, TiKV, Consul.

Raft key properties

One leader at a time (per term). Leader replicates log entries to followers. Entry committed when majority acknowledges. Leader election via randomized timeouts — reduces split votes. Safety: a node only votes for a candidate whose log is at least as up-to-date as its own.

06 — Real Systems

How Real Systems Apply These Concepts

Cassandra, Spanner, DynamoDB, MongoDB, Kafka

Cassandra — tunable consistency

Cassandra lets you choose consistency level per query. The magic number: R + W > N guarantees strong consistency (where R = read replicas, W = write replicas, N = total replicas).

N (replicas)
3
Write (W)
2
Read (R)
2

Google Spanner — TrueTime explained

Spanner uses atomic clocks + GPS to bound clock uncertainty to ~7ms. Every transaction must wait out this uncertainty before committing — this pause is the price of global consistency.

TrueTime.now() → returns interval [T_earliest, T_latest]
On commit → wait until T_latest passes (commit_wait)
Guarantee → if Txn A commits before Txn B starts: ts(A) < ts(B)
This is the only production system providing external consistency (linearizability + serializability) at global scale. Other systems either relax consistency or require explicit coordination per transaction.

MongoDB — evolution of consistency

Before v3.6 — eventual consistency only
Reads from secondaries could return stale data. No causal guarantees across sessions. Primary failure could lose acknowledged writes.
v3.6 — causal consistency sessions
Client sessions can opt into causal consistency. Uses cluster time (a hybrid logical clock) to ensure reads always see the writes from the same session in order.
v4.0+ — multi-document transactions
Added ACID transactions across multiple documents and collections. Uses snapshot isolation. Combined with causal sessions gives near-serializable guarantees within a replica set.
07 — Distributed Transactions

Two-Phase Commit (2PC) + Failure Modes

How distributed transactions work — and why they're fragile

Phase 1: Prepare Phase 2: Commit Failure: coordinator crash Failure: participant crash 3PC — the fix
Coordinator
sends PREPARE to all participants
Participants
lock resources, reply VOTE-YES or VOTE-NO
The coordinator sends a PREPARE message to all participants. Each participant checks if it can commit (sufficient resources, no conflicts), locks the relevant rows/records, writes to a redo log, and replies VOTE-YES or VOTE-NO.
Once a participant votes YES, it's locked in — it cannot unilaterally abort anymore. This is the "point of no return" for that participant.
Coordinator
if all YES → COMMIT. If any NO → ABORT
Participants
apply or roll back, release locks, send ACK
If all participants voted YES, the coordinator sends COMMIT to all. Each participant applies the transaction, releases locks, and acknowledges. If any voted NO, the coordinator sends ABORT — all participants roll back.
The coordinator must durably log its decision before sending — if it crashes after deciding but before all participants hear it, the recovery process must re-send the decision.
Coordinator crashes
after receiving all votes but before sending decision
Participants
blocked — can't commit OR abort
The blocking problem: participants who voted YES are stuck. They've locked resources and can't proceed without the coordinator's decision. They can't abort (coordinator might have decided COMMIT) and can't commit (coordinator might have decided ABORT). They must wait for the coordinator to recover.
This is 2PC's fatal flaw. It is a blocking protocol — a coordinator crash can hold locks indefinitely. In practice, timeouts + coordinator recovery logs mitigate but don't eliminate this.
Participant crashes
after voting YES, before receiving decision
Recovery
check redo log — if prepared, ask coordinator for decision
When a participant recovers, it checks its redo log. If it finds a PREPARE record, it asks the coordinator for the decision and applies it. If it finds a COMMIT record, it commits. If it finds nothing (crashed before voting), it can safely abort.
The redo log is essential. Without durable logging, recovery is impossible. This is why 2PC requires both coordinator and participant to write to durable storage before any network message.
Phase 1
PREPARE (same as 2PC)
Phase 2
PRE-COMMIT (new!)
Phase 3
COMMIT
Three-Phase Commit adds a PRE-COMMIT phase. After all YES votes, the coordinator sends PRE-COMMIT before the actual COMMIT. If participants see PRE-COMMIT, they know a COMMIT is coming — they can safely commit even if the coordinator crashes, making 3PC non-blocking in most failure scenarios.
3PC works under crash failures but NOT under network partitions — a partitioned participant that received PRE-COMMIT and one that didn't can make conflicting decisions. In practice, 2PC + recovery is more commonly used than 3PC.
Modern alternatives to 2PC

Saga pattern: break a distributed transaction into a sequence of local transactions, each with a compensating action for rollback. No global locks — eventual consistency with explicit rollback logic. Used in microservices.

Percolator (Google): optimistic concurrency with timestamps. Read a snapshot, detect conflicts at commit time. Used in TiKV / TiDB.

Calvin: pre-order transactions before executing — avoids distributed locking entirely by making sequencing the only coordination step.