Distributed systems fundamentals
Introduced
Vocabulary
| English | Meaning |
|---|---|
| distributed system | distributed system |
| partial failure | partial failure |
| idempotence | idempotence |
| Lamport clock | Lamport clock |
| happens-before | happens-before |
Physics of cooperation
- A distributed system shares state across machines with partial failure: one machine crashing must not corrupt the rest. Messages reorder and duplicate; idempotence makes re-execution safe.
- A timeout does not mean failed — it means unknown: the third outcome every protocol must handle.
{exercise:uni-cs0907-physics}
Practice
A timeout means —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The third outcome: the request may or may not have landed - retry idempotently.
Clocks cannot order
- Two machines' clocks skew without bound, so timestamps cannot safely order cross-machine events. The Lamport clock respects causality: send attaches $C+1$; receive sets $C = \max(C, \text{received}) + 1$.
- P0 sends $m_1$ at $C = 1$; P1 receives at $C = 2$; P1 sends $m_2$ at $3$; P0 receives at $4$. If $a$ happens-before $b$ then $C(a) < C(b)$ — one direction only.
{exercise:uni-cs0907-lamport}
Practice
P1 sends at C = 3 to P0 at C = 1: on receive, P0 becomes —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
C = max(1, 3) + 1 = 4.
Idempotence by design
deduct(user, 25, id=xyz)executed twice must deduct once: the operation is idempotent by key — the ledger recordsxyzas done and the retry is a no-op.- Retry-safe systems are built from idempotent operations plus a dedupe ledger, not from hoping the network stops duplicating.
{exercise:uni-cs0907-idempotent}
Practice
deduct(user, 25, id=xyz) twice deducts once because —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Idempotent by key: the retry is a no-op against the dedupe ledger.