Distribuovaný algoritmus je algoritmus navržený pro běh na více než jednom procesoru. Distribuované algoritmy se používají v různých aplikačních oblastech distribuovaných výpočtů, jako jsou telekomunikace, vědecko-technické výpočty, distribuované zpracování informací a řízení procesů v reálném čase. Mezi standardní problémy, které se řeší distribuovanými algoritmy, patří volba vedoucího, hledání shody, distribuované vyhledávání, konstrukce kostry grafu, vzájemné vyloučení a přidělování prostředků.
Distribuované algoritmy jsou podtypem paralelních algoritmů, které se obvykle provádějí paralelně (souběžně), přičemž jednotlivé části algoritmu běží současně na nezávislých procesorech a mají omezené informace o tom, co dělají ostatní části algoritmu. Jedním z nejobtížnějších problémů při vývoji a implementaci distribuovaných algoritmů je úspěšná koordinace chování nezávislých částí algoritmu v prostředí, kde mohou selhávat procesory nebo komunikace mezi nimi. Výběr vhodného distribuovaného algoritmu pro řešení daného problému závisí jak na vlastnostech řešeného problému tak na vlastnostech systému, na kterém má algoritmus běžet, včetně druhů a pravděpodobností selhání procesoru nebo komunikačního spoje, druhu dostupné meziprocesové komunikace a úrovně časové synchronizace mezi jednotlivými procesy.
Standardní problémy Atomický commit Atomický commit je operace, při které je třeba sadu různých změn provést jako jedinou operaci. Pokud se podaří provést všechny změny, je atomický commit úspěšný; pokud se nepodaří provést všechny změny, musí se zrušit i změny, které v rámci commitu již byly provedeny. K algoritmům pro řešení atomického commitu patří dvoufázový commit protokol a třífázový commit protokol. Hledání shody (konsensu) Algoritmy hledání shody se snaží vyřešit problém, kdy se několik procesů musí shodnout na společném rozhodnutí. Přesněji řečeno, protokol shody musí splňovat následující čtyři formální kritéria: Ukončení: každý správný proces určí nějakou hodnotu. Validita:, pokud všechny procesy navrhují stejnou hodnotu , pak každý správný proces musí vrátit . Integrita: každý správný proces určí nejvýše jednu hodnotu, a pokud vydá nějakou hodnotu , pak to musí být hodnota navržená některým z procesů. Shoda:, pokud správný proces vrátí , pak každý správný proces musí vrátit . Běžnými algoritmy pro hledání shody jsou Paxos algoritmus a Raft algoritmus. Distribuované vyhledávání Volba vedoucího Volba vedoucího je proces určení jediného procesu jako organizátora určitého úkolu distribuovaného mezi několik počítačů (uzlů). Před zahájením úkolu žádný z uzlů neví, jaký uzel bude fungovat jako „vedoucí,“ nebo koordinátor řešení úkolu. Po provedení algoritmu volby vedoucího každý uzel v síti musí vědět, který konkrétní uzel je vedoucí. Vzájemné vyloučení Neblokující datové struktury Spolehlivé rozesílání Spolehlivý rozesílání je komunikační primitivum v distribuovaných systémech definované následujícími vlastnosti: Validita -, pokud správný proces odešle zprávu, pak ji nakonec nějaký správný proces doručí. Shoda -, pokud správný proces doručí zprávu, pak všechny správné procesy nakonec doručí tuto zpráva. Integrita - každý správný proces doručí každou zprávu nejvýše jednou a pouze v případě, že tato zpráva byla odeslána nějakým procesem. Spolehlivý rozesílání může mít sekvenční, kauzální nebo úplné řazení zpráv. Replikace Přidělování prostředků Konstrukce kostry grafu Porušení symetrie, např. barvení vrcholů
Odkazy
Reference
Literatura
Externí odkazy MIT Open Courseware - Distributed Algorithms