Distributed systems fundamentals
Введено
Словарь
| English | Значение |
|---|---|
| distributed system | Independent computers coordinating through messages to provide a service or perform work. |
| partial failure | Failure of some components while other components continue operating. |
| idempotence | The property that repeating an operation has the same effect as performing it once. |
| Lamport clock | A logical counter scheme assigning timestamps consistent with the happens-before relation. |
| happens-before | A causal ordering induced by local event order and message transmission, including transitive consequences. |
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}
Практика
A timeout means —
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
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}
Практика
P1 sends at C = 3 to P0 at C = 1: on receive, P0 becomes —
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
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}
Практика
deduct(user, 25, id=xyz) twice deducts once because —
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Idempotent by key: the retry is a no-op against the dedupe ledger.