Distributed Systems Theory

Paxos

Leslie Lamport's Paxos (1990) is the theoretical foundation. Proposers, acceptors, and learners coordinate in two phases (prepare + accept) to agree on a value. Correct but notoriously difficult to implement and reason about. Google Chubby, early ZooKeeper internals, and Spanner's Paxos groups build on these ideas.

Raft — leader election + log replication

Raft (2014) decomposes consensus into leader election, log replication, and safety—designed to be understandable. Used by etcd, Consul, TiKV, and KRaft (Kafka metadata).

stateDiagram-v2
  [*] --> Follower
  Follower --> Candidate: election timeout
  Candidate --> Leader: wins majority vote
  Candidate --> Follower: discovers higher term
  Leader --> Follower: discovers higher term
  Follower --> Follower: receives AppendEntries from leader

  note right of Leader
    Client writes go to leader
    Leader appends to log
    Replicates to majority
    Commits then applies
  end note

Raft log replication (simplified)

1. Client sends command to leader
2. Leader appends entry to its log, assigns term + index
3. Leader sends AppendEntries RPC to followers
4. Entry committed once replicated on majority
5. Leader applies to state machine; responds to client
6. Followers apply committed entries in order

Redis SETNX

Basic pattern: SET key unique_token NX EX 30. Only set if not exists, with TTL to prevent deadlock if holder crashes. Release with Lua script comparing token before delete—prevents deleting another holder's lock.

-- Safe lock release (Redis Lua)
if redis.call("GET", KEYS[1]) == ARGV[1] then
  return redis.call("DEL", KEYS[1])
else
  return 0
end

Redlock critique

Redis Redlock algorithm (Salvatore Sanfilippo) acquires locks on N independent Redis masters with quorum. Martin Kleppmann's critique (2016): if the lock holder pauses (GC, VM migration) longer than TTL, another process can acquire the lock—both believe they hold it. Fencing tokens are required: monotonically increasing token passed to storage; storage rejects writes with stale tokens.

Two-Phase Commit (2PC)

Coordinator sends prepare to all participants → all vote commit/abort → coordinator sends commit/abort. Blocking: if coordinator crashes after prepare, participants hold locks indefinitely. Not used across microservices in practice.

sequenceDiagram
  participant C as Coordinator
  participant A as Service A
  participant B as Service B

  C->>A: prepare
  C->>B: prepare
  A-->>C: vote commit
  B-->>C: vote commit
  C->>A: commit
  C->>B: commit

Three-Phase Commit (3PC)

Adds pre-commit phase to reduce blocking—participants can timeout and abort if coordinator disappears after pre-commit. Still rarely used; network partitions can cause inconsistency.

Saga pattern

Transactional Outbox

Problem: how to atomically update DB and publish to Kafka? Outbox pattern: write business row + outbox row in same DB transaction. Separate relay process (Debezium CDC or polling publisher) reads outbox and publishes to message bus. Guarantees at-least-once delivery without 2PC across DB and broker.

flowchart LR
  App[Order Service]
  DB[(Orders DB\n+ outbox table)]
  Relay[Outbox Relay\nDebezium / Poller]
  Kafka[Kafka]

  App -->|single TX| DB
  Relay -->|read outbox| DB
  Relay -->|publish| Kafka

TrueTime and Spanner

Spanner assigns every transaction a commit timestamp from TrueTime—a bounded uncertainty interval (e.g., [earliest, latest]). Before commit, Spanner waits out the uncertainty window so all transactions get globally consistent timestamps. This provides external consistency (linearizability) at the cost of added commit latency (~7 ms wait typical).

Timeout tuning

• Too aggressive — GC pauses trigger false failover, split-brain, cascading restarts
• Too lenient — real failures take minutes to detect; extended downtime
• Rule of thumb — timeout > p99.9 peer response time × 3–5; account for GC (Java: 1–5s for full GC)
• Separate liveness from slowness — health check "can respond" vs SLA "responds in <100ms"

flowchart LR
  A[Node A\nstate v3] -->|push/pull| B[Node B]
  B -->|push/pull| C[Node C]
  C -->|push/pull| D[Node D]
  D -->|push/pull| A
  B -.->|anti-entropy| D

Properties

• O(log n) convergence — information spreads exponentially with rounds
• Fault tolerant — no single point of failure; works with partial connectivity
• Eventually consistent — nodes may have stale views temporarily
• Bandwidth efficient — small periodic messages vs full mesh broadcast

Use cases

Two families

Common CRDT types

Real-world use cases

Figma uses CRDTs (and custom conflict resolution) for multiplayer design editing—multiple designers move objects simultaneously; merges happen locally without a central lock. Offline edits sync on reconnect.

Notion applies CRDT-inspired techniques for block-level collaborative editing—each block is independently mergeable; operational transforms handle rich text within blocks. Mobile offline mode queues operations that merge on sync.

flowchart TB
  subgraph clientA [Designer A — offline]
    A1[Move icon x+10]
    A2[Add rectangle]
  end
  subgraph clientB [Designer B — online]
    B1[Move icon y+5]
    B2[Change color blue]
  end
  Merge[CRDT merge\ncommutative join]
  State[Converged document\nboth edits preserved]

  A1 & A2 --> Merge
  B1 & B2 --> Merge
  Merge --> State