Distributed Systems
CS3.401Prof. Kishore Kothapalli•Monsoon 2025-26•4 credits
High-Yield Topics
If time is short, study these first.
CAP theorem + examples for each side
5-8 markseasy
Always asked; pair with one real system per choice (Spanner, Dynamo, RDBMS).
Lamport scalar vs vector vs matrix clocks
8-10 marksmedium
Compare on size, causality, strong consistency; matrix-specific use (obsolete-message GC).
Chandy-Lamport snapshot algorithm (FIFO assumption, marker rules, C1/C2)
10-15 marksmedium
Algorithm trace with a 3-process banking example is exam gold.
DME comparison table (msgs/CS, sync delay, assumptions)
10-12 markseasy
Lamport 3(N-1), R-A 2(N-1), Maekawa 3√N→5√N, Suzuki-Kasami 0 or N, Raymond O(log N).
Maekawa V2 — FAILED / INQUIRE / YIELD deadlock fix
8-10 marksmedium
Why V1 deadlocks + the 3 new messages.
Chandy-Misra-Haas probe algorithm (AND model)
8-10 marksmedium
Probe(i, j, k) format + termination criterion = deadlock when initiator receives own probe.
Byzantine bounds: n ≥ 3m+1, ≥ m+1 rounds, async impossibility (FLP)
5-8 markseasy
1-mark sub-parts in every BA question.
Lamport-Shostak-Pease OM(m) algorithm
10-15 markshard
Recursion + final majority; trace for N=4, m=1.
Phase King — when to use, N ≥ 4f+1, 2(f+1) rounds, polynomial msgs
8-10 marksmedium
Often missed by students; pair with OM(m) comparison table.
2PC blocking problem
8-10 markseasy
Coordinator crash after all <ready> = blocking; this is THE central drawback.
3PC PRE-COMMIT phase + assumptions
8-10 marksmedium
How replicated decision avoids blocking; why not used in practice (no-partition assumption).
Raft: election + log replication + safety (election restriction)
10-15 marksmedium
Term + randomised timeout + 'most up-to-date log' rule.
GHS combining rules A, B, C + max level log N
10-12 markshard
Rule trace on a 4-node graph; mutual MWOE → merge to level L+1.
GFS architecture: single master + chunkservers + 64 MB chunks + 3× replicas
10-15 marksmedium
Always asked; pair with write flow (lease + pipelined data).
GFS consistency outcomes (defined / consistent / undefined / inconsistent)
6-10 marksmedium
Table of outcomes for serial write vs concurrent write vs append vs failure.
Physical time: Cristian's, Berkeley, NTP — assumptions and use cases
5-8 markseasy
Quick 1-mark questions; UTC vs internal-only sync.
Singhal-Kshemkalyani vector-clock optimisation
5-8 marksmedium
LS / LU arrays; send only changed entries; needs FIFO.
Acharya-Badrinath snapshot (causal channels) — SENT/RECD arrays
5-8 marksmedium
2N messages; channel state from {RECDⱼ[i]+1, ..., SENTᵢ[j]}.
BSS / Birman-Schiper-Stephenson causal delivery
6-10 marksmedium
Two delivery conditions (V_m[j] = V_i[j]+1 and V_m[k] ≤ V_i[k]).