Distributed systems fundamentals
Introduit
Vocabulaire
| English | Sens |
|---|---|
| distributed system | distributed system |
| partial failure | partial failure |
| idempotence | idempotence |
| Lamport clock | Lamport clock |
| happens-before | happens-before |
English
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}
Pratique
A timeout means —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
The third outcome: the request may or may not have landed - retry idempotently.
English
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}
Pratique
P1 sends at C = 3 to P0 at C = 1: on receive, P0 becomes —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
C = max(1, 3) + 1 = 4.
English
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}
Pratique
deduct(user, 25, id=xyz) twice deducts once because —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Idempotent by key: the retry is a no-op against the dedupe ledger.