Distributed Systems Theory
What you’ll learn. Why distributed systems are fundamentally harder than single-machine programs; the failure models that frame every design; what CAP and PACELC actually say (and what they do not); the spectrum of consistency models from linearizability to eventual consistency; how consensus protocols such as Raft work at an intuitive level; why physical clocks cannot be trusted and what logical clocks offer; how sagas replace distributed transactions; and why “exactly-once delivery” is a myth, while “effectively once” is achievable. Examples are Python or TypeScript, labelled.
What makes distribution hard
Section titled “What makes distribution hard”A distributed system is a set of independent computers that appear to users as one system. Leslie Lamport’s definition: “one in which the failure of a computer you didn’t even know existed can render your own computer unusable.” Three facts cause nearly all the difficulty:
- Partial failure. Parts fail independently while others keep running. In a single process, a crash kills everything; across a network, you can send a request and receive nothing, with no way to know whether the request was lost, the server crashed before or after processing it, or the reply was lost.
- Unreliable networks. Messages can be lost, delayed, duplicated and reordered. Delay and loss are indistinguishable from a crashed peer; the only tool is a timeout, which can only suspect failure.
- No shared clock or memory. Nodes cannot agree instantly on the time or on the order of events.
The fallacies of distributed computing (Peter Deutsch and colleagues): the network is reliable; latency is zero; bandwidth is infinite; the network is secure; topology does not change; there is one administrator; transport cost is zero; the network is homogeneous. Each is false, and each false assumption is a source of production incidents.
Failure models
Section titled “Failure models”A failure model states what faults an algorithm tolerates; guarantees are only valid relative to it.
- Crash-stop: a node halts and never returns.
- Crash-recovery: a node may crash and restart, retaining durable state but losing memory. This is the realistic model for servers.
- Omission: messages (or processes’ steps) get dropped.
- Timing/performance failures: responses arrive too late (slow nodes, GC pauses, network congestion).
- Byzantine: nodes may behave arbitrarily, including maliciously or by corruption. Tolerating Byzantine nodes requires replicas; used in blockchains and some aerospace systems, rarely in typical business backends where you trust your own nodes.
Timing assumptions. Synchronous systems have known bounds on delay and clock drift (unrealistic on the internet). Asynchronous systems have no bounds. Partially synchronous (Dwork, Lynch, Stockmeyer) systems behave asynchronously for unknown periods but eventually become synchronous; this is the model under which practical consensus protocols are designed: safe always, live only when the network behaves.
The FLP impossibility result (Fischer, Lynch, Paterson, 1985): in a purely asynchronous system, no deterministic consensus protocol can guarantee termination if even one process may crash. Practical systems sidestep FLP with timeouts (failure detectors) and randomization: they sacrifice liveness under bad timing, never safety.
Failure detection is unreliable by nature: a timeout-based detector must trade off detection speed against false positives. Phi-accrual detectors (Cassandra, Akka) output a suspicion level instead of a binary verdict.
CAP and PACELC
Section titled “CAP and PACELC”CAP theorem (Brewer’s conjecture, proven by Gilbert and Lynch, 2002): a distributed data store cannot simultaneously provide Consistency (specifically linearizability), Availability (every request to a non-failing node receives a non-error response) and Partition tolerance (continues operating despite network partitions). Because partitions will happen on real networks, the real choice is: when a partition occurs, choose consistency (reject or block some requests) or availability (serve possibly stale or conflicting data).
Network partition occurs | +----------------+----------------+ | | CP: refuse/stall minority side AP: both sides keep serving, (e.g. etcd, ZooKeeper, Spanner) reconcile later (e.g. Dynamo, Cassandra in default tuning, CRDT stores)Common misreadings to avoid:
- “Pick any two of three” is misleading: you cannot “choose CA” on a network that can partition; CA is just a single node.
- CAP’s “C” is linearizability, not ACID’s consistency; “A” is a strong 100% availability definition, not “high availability” in the SRE sense.
- CAP only describes behavior during partitions; most of the time there is none. Many systems are tunable per operation.
PACELC (Daniel Abadi, 2010) closes the gap: if there is a Partition, choose A or C; Else (normal operation), choose between Latency and Consistency. Even without partitions, strong consistency requires coordination across replicas, costing latency. So: Dynamo/Cassandra are PA/EL (available and fast, weaker consistency); Spanner and many consensus-based stores are PC/EC (consistent, paying latency); some systems such as MongoDB (by configuration) and PNUTS are PC/EL or PA/EC combinations.
Consistency models
Section titled “Consistency models”A consistency model is a contract specifying which orderings of operations a client may observe. Stronger models are easier to program against and costlier in latency and availability. A rough hierarchy, strongest first:
- Linearizability (strong consistency): operations appear to take effect atomically at some instant between invocation and response, in an order consistent with real time. Once a write completes, every later read (anywhere) sees it. It behaves like a single copy of the data. Needed for locks, leader election, unique constraints, and bank balances in the strict sense. Expensive: requires coordination (e.g. consensus).
- Sequential consistency: all operations appear in some single total order that respects each process’s program order, but not necessarily real time.
- Causal consistency: operations that are causally related (a reply after the post it responds to) are seen in the same order by everyone; concurrent operations may be seen in different orders. It is the strongest model achievable while remaining available under partitions (as formalized in research on the “CAC” trade-off).
- Session guarantees (Terry et al.): read-your-writes, monotonic reads (never go backward in time), monotonic writes, writes-follow-reads. Cheap and often enough for user-facing apps.
- Eventual consistency: if writes stop, all replicas converge. Says nothing about what you read in the meantime.
Distinguish from serializability (transactions behave as if executed in some serial order, an isolation property about multi-object transactions) versus linearizability (a recency property of single-object operations). “Strict serializability” combines both (Spanner provides “external consistency”).
Concrete anomaly: with asynchronous replication, a user posts a comment (leader), refreshes, and the read hits a lagging follower: the comment vanishes (violates read-your-writes). A second refresh hits a fresher replica and it reappears (violates monotonic reads). Fixes: route a user’s reads to the same replica (stickiness), read own writes from the leader for a window, or pass a version token.
Conflict handling in AP systems: last-write-wins (simple, silently loses concurrent writes and depends on clocks), version vectors to detect concurrency and surface siblings for the application to merge, and CRDTs (conflict-free replicated data types: counters, sets, registers, sequences whose merge is commutative, associative and idempotent, so replicas converge without coordination). CRDTs power collaborative editors (Automerge, Yjs) and some databases (Riak, Redis Enterprise).
Clocks and ordering
Section titled “Clocks and ordering”Physical clocks drift (typically tens to hundreds of ppm, i.e. milliseconds per minute-hour) and are corrected by NTP, which can step the clock backward. Two nodes’ timestamps cannot be compared reliably: a later event may carry an earlier timestamp. Consequences: last-write-wins with wall clocks can drop the “newer” write; leases based on local clocks can be wrongly believed valid after a GC pause (Kleppmann’s fencing token example below). Use monotonic clocks (time.monotonic(), performance.now()) for measuring durations on one node, and never use wall-clock time to order events across nodes.
Logical clocks capture causality without physical time. Lamport’s “happened-before” relation holds if precedes in the same process, if is a send and its receive, or transitively.
- Lamport clocks: each process keeps a counter ; increment on each event; attach to sent messages; on receive set . Guarantee: (but not the converse; equal-or-lower clocks do not imply concurrency).
- Vector clocks: each process keeps a vector with one counter per process; they distinguish “happened-before” from “concurrent”: iff all entries and at least one ; if neither dominates, the events are concurrent (a conflict). Cost grows with the number of processes.
# Python: Lamport clockclass LamportClock: def __init__(self): self.t = 0 def tick(self) -> int: # local event or send self.t += 1 return self.t def receive(self, msg_t: int) -> int: self.t = max(self.t, msg_t) + 1 return self.tHybrid logical clocks (HLC) combine physical time with a logical counter so timestamps stay close to real time yet respect causality (used in CockroachDB and MongoDB). TrueTime in Google Spanner exposes clock uncertainty explicitly as an interval (backed by GPS and atomic clocks) and makes a transaction wait out the uncertainty window (“commit wait”) to guarantee external consistency, an example of buying consistency with latency (PACELC).
Fencing tokens. A client holds a lock lease, pauses (GC, VM stall), the lease expires, another client acquires the lock, and then the first wakes up and writes, believing it still holds the lock. The remedy: the lock service issues a monotonically increasing token with each grant, and the storage layer rejects writes bearing an older token than it has seen. Lesson: correctness must not depend on timing assumptions held by clients.
Consensus
Section titled “Consensus”Consensus lets a set of nodes agree on a value (or a sequence of values) despite failures. It is the foundation for leader election, replicated state machines, atomic commit, distributed locks and configuration stores (etcd, ZooKeeper, Consul). Required properties: agreement (all correct nodes decide the same value), validity (the decided value was proposed by someone), termination (correct nodes eventually decide). A cluster of nodes tolerates crash failures; decisions need a majority quorum of , and any two majorities intersect in at least one node, which is the key to safety.
Replicated state machine (RSM). Make every replica a deterministic state machine and feed all of them the same ordered log of commands; they end in the same state. Consensus is used to agree on the log’s order. This is how Raft/Paxos-based systems provide linearizable storage.
Raft (intuition)
Section titled “Raft (intuition)”Raft (Ongaro and Ousterhout, 2014) was designed for understandability. It decomposes consensus into three parts:
- Leader election. Time is divided into numbered terms. Nodes are followers, candidates or leaders. A follower that hears nothing from a leader for a randomized election timeout becomes a candidate, increments the term, votes for itself and requests votes. A node grants at most one vote per term, and only to a candidate whose log is at least as up to date as its own. A candidate with a majority becomes leader; randomized timeouts make split votes rare and quickly resolved.
- Log replication. Clients send commands to the leader, which appends them to its log and sends
AppendEntriesto followers. Once an entry is stored on a majority, it is committed; the leader applies it to its state machine, replies to the client, and tells followers the commit index. Followers’ logs that diverge from the leader’s are overwritten to match it. - Safety. The election restriction (only up-to-date logs can win) ensures a new leader contains all committed entries, so committed entries are never lost.
term 1: Leader L1 -> followers F2,F3 : append(x=1) acked by majority -> committedL1 crashes. F2's election timeout fires first -> term 2, votes from F3 (+itself) -> new leaderF2 has x=1 in its log (it was committed on a majority) -> no committed data lostCost: each write needs at least one round trip to a majority (latency = time to the median-fastest follower) and goes through a single leader (throughput bottleneck; scale with sharding: many Raft groups, one per partition, as in CockroachDB, TiKV, etcd-based designs). Reads that must be linearizable need the leader to confirm its leadership (read index or lease reads).
Paxos and friends
Section titled “Paxos and friends”Paxos (Lamport, “The Part-Time Parliament,” 1998; “Paxos Made Simple,” 2001) is the original proven consensus algorithm. Single-decree Paxos has two phases: prepare/promise (a proposer with ballot number asks acceptors to promise not to accept lower ballots and to report any value already accepted) and accept/accepted (the proposer proposes a value, constrained to the highest-ballot value reported, if any, which preserves earlier decisions). Multi-Paxos chooses a stable leader to skip phase 1 for a sequence of log slots, converging on essentially the same structure as Raft. Raft is easier to implement correctly; Paxos variants appear in Google Chubby/Spanner and elsewhere. Others to know by name: Zab (ZooKeeper), Viewstamped Replication, EPaxos (leaderless), and PBFT and descendants for Byzantine settings.
Practical advice: do not implement consensus yourself. Use etcd, ZooKeeper, Consul or a managed database that already does, and understand its guarantees and failure behavior (a cluster of 3 tolerates 1 failure, 5 tolerates 2; an even-sized cluster adds no tolerance).
Distributed transactions and sagas
Section titled “Distributed transactions and sagas”Two-phase commit (2PC) coordinates atomic commit across nodes: phase 1 the coordinator asks all participants to prepare (vote yes after durably logging); phase 2, if all voted yes, it tells them to commit, otherwise abort. It is simple but blocking: if the coordinator crashes after participants voted yes, they must hold locks until it recovers. It is used inside databases and XA environments, but is rarely suitable across independent microservices (availability coupling, lock holding, latency). Consensus-based commit (Paxos Commit; Spanner’s 2PC over Paxos groups) mitigates coordinator failure.
Sagas (Garcia-Molina and Salem, 1987) break a long-running business transaction into a sequence of local transactions, each committed independently, with a compensating action for each step that semantically undoes it if a later step fails. There is no isolation: intermediate states are visible, so design for it (semantic locks such as a PENDING status, commutative updates, re-reading).
Order saga (orchestrated): 1. OrderService: create order (PENDING) compensate: cancel order 2. PaymentService: charge card compensate: refund 3. InventoryService: reserve stock compensate: release stock 4. OrderService: mark order CONFIRMED If step 3 fails -> run compensations for 2 then 1 (in reverse order).Two coordination styles: orchestration (a central saga coordinator or workflow engine such as Temporal, AWS Step Functions or Camunda issues commands and tracks state) and choreography (services react to each other’s events). Requirements: every step and every compensation must be idempotent and retryable; compensations should not fail (or must be retried until they succeed); state of the saga must be durable. The transactional outbox (Architecture Styles) ensures events are published atomically with local state change.
# Python: tiny orchestrated saga runner (state persistence omitted)def run_saga(steps): done = [] try: for action, compensate in steps: action() done.append(compensate) except Exception: for compensate in reversed(done): compensate() # must be idempotent and retried until success raise
run_saga([ (create_order, cancel_order), (charge_card, refund_card), (reserve_stock, release_stock),])Some things cannot be compensated (an email already sent, a physical shipment): order such steps last or make them “pivot” steps beyond which the saga only moves forward.
Delivery guarantees and the exactly-once myth
Section titled “Delivery guarantees and the exactly-once myth”Between two processes over an unreliable network:
- At-most-once: send once, never retry; messages may be lost.
- At-least-once: retry until acknowledged; messages may be duplicated.
- Exactly-once delivery: each message delivered exactly once. This is impossible in general (an instance of the Two Generals problem): if an acknowledgment is lost, the sender cannot distinguish “never processed” from “processed but ack lost”, so it must either risk loss (do not retry) or duplication (retry).
What is achievable is effectively-once processing: at-least-once delivery combined with idempotent or deduplicating consumers, so duplicates have no extra effect. Techniques:
- Idempotent operations by design:
SET x = 5is idempotent;x = x + 1is not (see API Design for idempotency keys). - Deduplication table: record processed message IDs in the same transaction as the side effect.
- Conditional writes and versioning (
UPDATE ... WHERE version = n). - Transactional offsets: Kafka’s “exactly-once semantics” combines idempotent producers, transactions across partitions and consumer offsets committed atomically with output records. This is exactly-once within Kafka’s pipelines (read-process-write between Kafka topics); once you touch an external side effect (send an email, call an API, write to a non-transactional database), you are back to needing idempotence.
// TypeScript: idempotent consumer using a dedup table in the same transactionasync function handle(msg: { id: string; amount: number; account: string }) { await db.transaction(async (tx) => { const inserted = await tx.query( "INSERT INTO processed_messages(id) VALUES ($1) ON CONFLICT DO NOTHING RETURNING id", [msg.id], ); if (inserted.rowCount === 0) return; // duplicate: already applied await tx.query("UPDATE accounts SET balance = balance + $1 WHERE id = $2", [msg.amount, msg.account]); }); // dedup record and effect commit atomically}Also beware ordering: at-least-once with retries can reorder messages; carry sequence numbers or versions and ignore stale updates.
Design heuristics
Section titled “Design heuristics”- Assume failure: every remote call needs a timeout, bounded retries with exponential backoff and jitter, and an idempotent target (Reliability & Performance).
- Minimize coordination: avoid linearizability where weaker guarantees suffice; partition data so most operations touch one shard.
- Prefer idempotent, commutative operations (CRDT-like), which are naturally robust to retries and reordering.
- Single-writer principle: one owner per piece of state removes conflict classes.
- Make state transitions explicit and durable (state machines, event logs).
- Use the right guarantees per feature: the checkout total needs strong consistency, the “like” count does not.
- Test failures: partition, delay, kill (Jepsen-style testing, chaos engineering, deterministic simulation).
Common pitfalls
Section titled “Common pitfalls”- Using wall-clock timestamps for ordering or last-write-wins on important data.
- Treating a timeout as proof of failure (the operation may have succeeded).
- Distributed locks without fencing tokens.
- Dual writes (database + broker/cache) without an outbox or transactional mechanism.
- Claiming exactly-once without idempotency at the effect boundary.
- Even-sized consensus clusters, or clusters spread over two failure domains (losing one takes down the majority).
- Reading CAP as a design menu rather than a statement about partition behavior.
Key takeaways
Section titled “Key takeaways”- Partial failure and unreliable networks are the root difficulty; failure models define what a design tolerates.
- CAP: during a partition choose C or A; PACELC adds the everyday latency vs consistency trade-off.
- Consistency models form a spectrum (linearizable, sequential, causal, session guarantees, eventual); choose the weakest that preserves your invariants.
- Do not trust wall clocks across nodes; use logical or hybrid clocks, and fencing tokens for leases.
- Consensus (Raft/Paxos) gives replicated state machines via majority quorums and leader election, at a cost in latency; use proven implementations.
- Sagas with idempotent compensations replace distributed ACID transactions across services.
- Exactly-once delivery is impossible; at-least-once plus idempotence gives effectively-once effects.
Exercises
Section titled “Exercises”- Conceptual. A 5-node Raft cluster loses 2 nodes. Can it elect a leader and commit? What about losing 3? Explain via quorum intersection.
- Conceptual. Classify each as needing linearizability or being fine with eventual consistency: unique username registration; a post’s like count; a distributed lock; a news feed.
- Hands-on (Python). Implement vector clocks with
mergeand acomparefunction returningbefore,after,equalorconcurrent. Test with three processes. - Hands-on (Python). Extend the saga runner so each step persists its progress to a file so a crashed orchestrator can resume; make compensations retried with backoff.
- Conceptual. A payment consumer reads a message, charges a card, then crashes before committing its offset. Describe what happens on restart and design the fix.
Solutions (sketch)
- Losing 2 leaves 3 of 5: a majority, so it works. Losing 3 leaves 2 of 5: no majority, so no leader and no commits (it stalls rather than risk divergence). Any two majorities share a node, so two disjoint leaders cannot both commit.
- Username uniqueness and the distributed lock need linearizability (or a single serialization point); like counts and feeds tolerate eventual consistency.
compare(a, b): if alla[i] <= b[i]and some<, thenbefore; the converse isafter; if all equal,equal; otherwiseconcurrent.- On restart the message is redelivered; the card is charged twice unless the charge uses an idempotency key derived from the message ID (or the consumer records the ID transactionally). Use the same key on the payment API call and store the result.
Further reading
Section titled “Further reading”- Martin Kleppmann, Designing Data-Intensive Applications (2017), chapters 5-9.
- Diego Ongaro and John Ousterhout, “In Search of an Understandable Consensus Algorithm (Raft)” (USENIX ATC 2014).
- Leslie Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System” (1978); “Paxos Made Simple” (2001).
- Seth Gilbert and Nancy Lynch, “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services” (2002).
- Daniel Abadi, “Consistency Tradeoffs in Modern Distributed Database System Design” (2012).
- Michael Fischer, Nancy Lynch, Michael Paterson, “Impossibility of Distributed Consensus with One Faulty Process” (1985).
- Hector Garcia-Molina and Kenneth Salem, “Sagas” (1987).
- James Corbett et al., “Spanner: Google’s Globally-Distributed Database” (OSDI 2012).
- Kyle Kingsbury’s Jepsen analyses (jepsen.io).
- Andrew Tanenbaum and Maarten van Steen, Distributed Systems (3rd/4th ed.).