Distributed Systems

What is a distributed system, why is it useful, and what makes it hard? Tanenbaum's definition; required features (concurrency, independent failures, no global clock, no shared memory); the unique challenges (unreliable communication, lack of global knowledge, no synchronisation); CAP theorem (Brewer) and the C-vs-A trade-off under unavoidable partitions; the Two-Generals problem.

The model of a distributed program (processors, channels, events). Lamport's happened-before relation. Logical clocks: scalar (Lamport), vector, and matrix — their properties, comparison, and use-cases. The strong-consistency trap (scalar fails the converse). Physical-time synchronisation: Cristian's, Berkeley, Decentralised averaging, NTP.

Recording a consistent snapshot of a distributed system without stopping it. The C1/C2 cut conditions. Chandy-Lamport (FIFO channels), Lai-Yang (non-FIFO, white/red colouring), Acharya-Badrinath (causal channels, 2N messages). Banking example showing inconsistent vs consistent cuts.

When messages must be delivered in causal order (not just FIFO). Birman-Schiper-Stephenson (BSS) algorithm: two delivery conditions on vector clocks. Causal order vs FIFO vs total order. Use cases: replicated databases, group communication, distributed debugging.

Five canonical distributed mutex algorithms: Lamport (3(N-1) msgs, FIFO), Ricart-Agrawala (2(N-1) msgs, no FIFO), Maekawa (3√N → 5√N quorum-based with V2 deadlock fix), Suzuki-Kasami (token broadcast, 0 or N msgs), Raymond (token tree, O(log N) msgs). Safety / liveness / fairness; message complexity, synchronisation delay, throughput.

Resource request models (Single, AND, OR, AND-OR, P-out-of-Q). Wait-for graphs and the cycle-vs-knot distinction. Three handling strategies (prevention, avoidance, detection) and why detection dominates in DS. Detection algorithms: Ho-Ramamoorthy (centralised, 1-phase / 2-phase), Chandy-Misra-Haas probe (AND), Mitchell-Merritt label-passing (single-resource), Chandy diffusion (OR).

Reaching agreement among nodes that may fail. Crash-failure consensus: $f+1$ rounds, $(f+1) \cdot n^2$ messages. Byzantine bounds: $n \ge 3f+1$, $\ge f+1$ rounds. FLP impossibility in asynchronous systems. Lamport-Shostak-Pease oral-messages algorithm OM(m). Phase King — polynomial alternative with $n \ge 4f+1$. Three variants: Byzantine Agreement, Consensus, Interactive Consistency.

ACID across multiple sites. Two-Phase Commit (2PC): Prepare + Decide phases; log records; recovery rules; the BLOCKING problem when coordinator crashes after all <ready>. Three-Phase Commit (3PC): adds a PRE-COMMIT phase to break blocking; requires no-partition assumption (rarely used in practice).

Raft solves the replicated state machine problem under crash failures (not Byzantine). Decomposed into three sub-problems: Leader Election (randomised timeouts, terms), Log Replication (AppendEntries + majority commit), and Safety (election restriction — only most-up-to-date logs can be elected). Production-grade — backs etcd, Consul, CockroachDB.

Gallager-Humblet-Spira (1983): the canonical distributed MST algorithm. Cycle and cut properties. Fragments (subtrees of MST) with (name, level). Combining rules A (absorption), B (merger), C (wait). Test/Accept/Reject mechanism on basic edges. Max level ≤ log N. Complexity O(N log N + E) messages — optimal among comparison-based.

GFS architecture: single master + chunkservers + clients. 64 MB chunks replicated 3× across racks. Leases serialise mutations at a primary replica. Atomic record append. Four consistency states (defined / consistent / undefined / inconsistent). Pipelined data flow vs star control flow. Garbage collection via heartbeats + 3-day hidden retention. Copy-on-write snapshots.