V distribuovaných systémech chybí sdílená paměť a globální hodiny. To vytváří fundamentální problém: Jak zajistit, aby procesy spolupracovaly a nepřekážely si?
Tento problém se nazývá koordinace a jeho řešení vyžaduje synchronizaci - koordinovanou spolupráci procesů pomocí výměny zpráv.
Důsledek: Musíme explicitně řešit problémy, které v centralizovaných systémech řeší OS automaticky (mutexes, semafory, system clock).
Otázka: Jak sjednotit pohled na čas?
Synchronizace reálného času (hodiny na zdi) mezi uzly.
Místo sekund měříme kauzální pořadí událostí. Pokud události nesouvisí, jsou souběžné (concurrent).
Použití: Ordering zpráv, conflict detection, debugging distribuovaných systémů
Otázka: Jak zajistit, aby procesy spolupracovaly bez konfliktů?
Řešíme synchronizační problémy - konkrétní koordinační úlohy:
Problém: Kdo smí vstoupit do kritické sekce?
Náhrada za semafory/mutexy v prostředí bez sdílené paměti.
Algoritmy: Centralized, Token Ring, Ricart-Agrawala, Maekawa
Algoritmy pro výběr nového leadera (např. po pádu toho starého). Problém: Kdo bude vůdce skupiny? Algoritmy: Bully, Ring-based, Raft election
Problém: Jak se shodnout na jedné hodnotě? Dosažení shody mezi procesy i při selháních.
Algoritmy: Paxos, Raft
Limity: konsenzus v distribuovaných systémech#FLP Impossibility - konsenzus v asynchronním systému s možností selhání není vždy možný
Problém: Jak zajistit ACID vlastnosti napříč více uzly? Trade-off: Konzistence vs. dostupnost (blokující při výpadcích) Algoritmy: 2PC, 3PC
Problém: Kdo je členem skupiny?
Problém: V jakém stavu náš systém je? Jsou nějaké uzly mrtvé? Trade-off: Rychlost detekce vs. přesnost (false positives)
Všechny synchronizační problémy lze řešit pomocí tří základních návrhových vzorů.