Distribuovaný algoritmus - Distributed algorithm

A distribuovaný algoritmus je algoritmus navržen tak, aby fungoval dál počítačový hardware konstruovány ze vzájemně propojených procesory. Distribuované algoritmy se používají v mnoha různých aplikačních oblastech distribuované výpočty, jako telekomunikace, vědecké výpočty, distribuováno zpracování informací a v reálném čase kontrola procesu. Mezi standardní problémy řešené distribuovanými algoritmy patří volby vůdce, shoda, distribuováno Vyhledávání, kostra generace, vzájemné vyloučení, a přidělení zdrojů.^[1]

Distribuované algoritmy jsou podtypem paralelní algoritmus, obvykle provedeny současně, přičemž oddělené části algoritmu běží současně na nezávislých procesorech a mají omezené informace o tom, co dělají ostatní části algoritmu. Jednou z hlavních výzev při vývoji a implementaci distribuovaných algoritmů je úspěšná koordinace chování nezávislých částí algoritmu tváří v tvář poruchám procesoru a nespolehlivým komunikačním spojům. Volba vhodného distribuovaného algoritmu k řešení daného problému závisí jak na charakteristikách problému, tak na vlastnostech systému, na kterém bude algoritmus fungovat, jako je typ a pravděpodobnost selhání procesoru nebo spojení, druh meziprocesové komunikace které lze provést, a úroveň synchronizace načasování mezi samostatnými procesy.^[1]

Standardní problémy

Atomové potvrzení: Atomová revize je operace, kde se sada samostatných změn použije jako jediná operace. Pokud je atomové potvrzení úspěšné, znamená to, že byly použity všechny změny. Pokud dojde k selhání před dokončením atomového potvrzení, je „potvrzení“ přerušeno a nebudou použity žádné změny.; Algoritmy pro řešení protokolu atomového potvrzení zahrnují dvoufázový protokol potvrzení a třífázový protokol potvrzení.

Shoda: Konsenzuální algoritmy se snaží vyřešit problém řady procesů, které se shodují na společném rozhodnutí.; Přesněji řečeno, konsensuální protokol musí splňovat čtyři formální vlastnosti uvedené níže.

Ukončení: každý správný proces rozhoduje o nějaké hodnotě.
Platnost: pokud všechny procesy nabízejí stejnou hodnotu ${ displaystyle v}$ , pak rozhodne každý správný proces ${ displaystyle v}$ .
Integrita: každý správný proces rozhoduje nejvýše o jednu hodnotu, a pokud rozhoduje o nějaké hodnotě ${ displaystyle v}$ , pak ${ displaystyle v}$ musel být navržen nějakým procesem.
Dohoda: pokud rozhodne správný proces ${ displaystyle v}$ , pak rozhodne každý správný proces ${ displaystyle v}$ .

Běžné algoritmy pro řešení konsensu jsou Algoritmus Paxos a Raftový algoritmus.

Distribuované vyhledávání

Vůdce volby

Volba vůdce je proces určování jediného procesu jako organizátora nějakého úkolu distribuovaného mezi několik počítačů (uzlů). Před zahájením úlohy všechny síťové uzly nevědí, který uzel bude sloužit jako „vedoucí“ nebo koordinátor úkolu. Po spuštění volebního algoritmu vůdce však každý uzel v síti rozpozná určitý jedinečný uzel jako vedoucí úkolu.

Vzájemné vyloučení

Neblokující datové struktury

Spolehlivé vysílání

Spolehlivé vysílání je v distribuovaných systémech primitivní komunikace. Spolehlivé vysílání je definováno následujícími vlastnostmi:

Platnost - pokud správný proces odešle zprávu, pak nějaký správný proces tuto zprávu nakonec doručí
Dohoda - pokud správný proces doručí zprávu, pak všechny správné procesy tuto zprávu nakonec doručí
Integrita - každý správný proces doručí stejnou zprávu maximálně jednou a pouze v případě, že byla tato zpráva odeslána procesem

Spolehlivé vysílání může mít sekvenční, kauzální nebo úplné řazení.

Replikace
Přidělení zdrojů
Překlenující strom generace
Přerušení symetrie, např. vrchol zbarvení

Reference

^ ^A ^b Lynch, Nancy (1996). Distribuované algoritmy. San Francisco, Kalifornie: Nakladatelé Morgan Kaufmann. ISBN 978-1-55860-348-6.

Další čtení

Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), Úvod do spolehlivého a bezpečného distribuovaného programování (2. vyd.), Springer, ISBN 978-3-642-15259-7
C. Rodríguez, M. Villagra a B. Barán, Asynchronní týmové algoritmy pro Boolean Satisfiability, Bionetics2007, s. 66–69, 2007.

externí odkazy

Média související s Distribuované algoritmy na Wikimedia Commons
MIT Open Courseware - distribuované algoritmy

[lynch1997-1] A ^b Lynch, Nancy (1996). Distribuované algoritmy. San Francisco, Kalifornie: Nakladatelé Morgan Kaufmann. ISBN 978-1-55860-348-6.

[1]