Algoritmus Dijkstra – Scholten - Dijkstra–Scholten algorithm - Wikipedia

The Algoritmus Dijkstra – Scholten (pojmenoval podle Edsger W. Dijkstra a Carel S. Scholten ) je algoritmus pro detekci ukončení v distribuovaný systém.[1][2] Algoritmus navrhli Dijkstra a Scholten v roce 1980.[3]

Nejprve zvažte jednoduchý případ graf procesu což je strom. Distribuovaný výpočet, který má stromovou strukturu, není neobvyklý. Takový graf procesu může vzniknout, když je výpočet striktně a rozděl a panuj typ. A uzel spustí výpočet a rozdělí problém na dvě (nebo více, obvykle na násobek 2) zhruba stejných částí a distribuuje tyto části k dalším procesorům. Tento proces pokračuje rekurzivně, dokud problémy nejsou dostatečně malé, aby je bylo možné vyřešit v jediném procesoru.

Algoritmus

Algoritmus Dijkstra – Scholten je stromový algoritmus, který lze popsat následujícím způsobem:

  • Iniciátorem výpočtu je kořen stromu.
  • Po obdržení výpočetní zprávy:
    • Pokud přijímací proces aktuálně není ve výpočtu: proces se připojí ke stromu tím, že se stane podřízeným odesílatele zprávy. (V tomto okamžiku není odeslána žádná potvrzovací zpráva.)
    • Pokud je proces přijímání již ve výpočtu: proces okamžitě odešle potvrzovací zprávu odesílateli zprávy.
  • Když proces nemá žádné další podřízené položky a stal se nečinným, proces se oddělí od stromu odesláním potvrzovací zprávy jeho nadřazenému stromu.
  • Ukončení nastane, když iniciátor nemá žádné děti a nečinný.

Algoritmus Dijkstra – Scholten pro strom

  • U stromu je snadné zjistit ukončení. Když listový proces určí, že byl ukončen, odešle signál svému rodiči. Obecně proces čeká, až všechny jeho děti pošlou signály, a poté odešle signál svému rodiči.
  • Program se ukončí, když root přijme signály od všech svých podřízených.

Algoritmus Dijkstra – Scholten pro směrované acyklické grafy

  • Algoritmus stromu lze rozšířit na acyklické směrované grafy. Na každou hranu přidáme další celočíselný atribut Deficit.
  • Na příchozí hraně bude Deficit označovat rozdíl mezi počtem přijatých zpráv a počtem signálů odeslaných v odpovědi.
  • Když si uzel přeje ukončit, čeká, až přijme signály odchozích hran, čímž sníží jejich deficity na nulu.
  • Poté vyšle dostatek signálů, aby se ujistil, že deficit je na každé příchozí hraně nulový.
  • Protože je graf acyklický, některé uzly nebudou mít žádné odchozí hrany a tyto uzly budou první, které se ukončí po odeslání dostatečného počtu signálů na jejich příchozí hrany. Poté uzly na vyšších úrovních ukončí úroveň po úrovni.

Dijkstra – Scholtenův algoritmus pro cyklicky směrované grafy

  • Pokud jsou povoleny cykly, předchozí algoritmus nefunguje. Je to proto, že nemusí existovat žádný uzel s nulovými odchozími hranami. Potenciálně tedy neexistuje žádný uzel, který by mohl skončit bez konzultace s jinými uzly.
  • Algoritmus Dijkstra – Scholten řeší tento problém implicitním vytvořením a kostra grafu. Rozpínací strom je strom, který zahrnuje každý uzel podkladového grafu jednou a množina hran je podmnožinou původní sady hran.
  • Strom bude směrován (tj. Budou směrovány kanály) se zdrojovým uzlem (který iniciuje výpočet) jako kořen.
  • Rozpínací strom je vytvořen následujícím způsobem. Proměnná First_Edge je přidán do každého uzlu. Když uzel přijme zprávu poprvé, inicializuje se First_Edge s okrajem, přes který přijala zprávu. First_Edge poté se nikdy nezmění. Všimněte si, že spanning tree není jedinečný a záleží na pořadí zpráv v systému.
  • Ukončení řeší každý uzel ve třech krocích:
    1. Odesílejte signály na všechny příchozí hrany kromě první hrany. (Každý uzel bude vysílat signály, které snižují deficit na každém příchozím okraji na nulu.)
    2. Počkejte na signály ze všech odchozích hran. (Počet signálů přijatých na každé odchozí hraně by měl snížit každý jejich deficit na nulu.)
    3. Odesílat signály First_Edge. (Jakmile jsou kroky 1 a 2 dokončeny, uzel informuje svého nadřazeného člena v překlenovacím stromu o svém záměru ukončit.)

Viz také

Reference

  1. ^ Ghosh, Sukumar (2010), „9.3.1 Algoritmus Dijkstra – Scholten“, Distribuované systémy: Algoritmický přístup, CRC Press, str. 140–143, ISBN  9781420010848.
  2. ^ Fokkink, Wan (2013), „6.1 Dijkstra – Scholtenův algoritmus“, Distribuované algoritmy: Intuitivní přístup, MIT Press, str. 38–39, ISBN  9780262318952.
  3. ^ Dijkstra, Edsger W .; Scholten, C. S. (1980), "Detekce ukončení pro rozptýlené výpočty" (PDF), Dopisy o zpracování informací, 11 (1): 1–4, doi:10.1016/0020-0190(80)90021-6, PAN  0585394.