Dajkstra-Soltenov algoritam
Dajkstra Solten algoritam (nazvan po Edsger W. Dijkstra i C. S. Scholten) je algoritam za nalaženje prekida u distribuiranom sistemu. Algoritam je predložen od strane Dijkstre i Soltena 1980. godine.[1]
Prvo, razmotrimo slucaj jednostavnog procesa grafa koji je stablo. Distribuiran proračun koji je stablo-strukturisan nije neuobičajen. Takav proces graf može nastati kada je izračunavanje strogo podeli-i-vladaj tipa. Čvor počinje obračun i deli problem u dva (ili vise, obično više od 2) poprilično jednaka dela i distribuira te delove drugim procesorima. Ovaj proces se nastavlja rekurzivno sve dok problemi ne budu dovolno malih dimenzija da se reše jednim procesorom.
Algoritam
Dijkstra-Solten algoritam je algoritam zasnovan na stablu koje se može opisati na sledeći način:
- Inicijator računanja je koren stabla.
- Po prijemu obračunske poruke:
- Ako dolazeći proces trenutno nije u obračunu: proces se pridruzujue stablu postajuci dete posaljilaca poruke.(Bez znanja da je poruka poslata u tom trenutku)
- Ako je dolazeći proces već u obračunu: proces odmah šalje poruku potvrde pošaljiocu poruke.
- Kada proces nema vise dece i kad je postao neaktivan, proces se odvaja od stabla tako što šalje poruku potvrde svom roditelju.
- Prekid se javlja kada inicijator nema dece i kad je postao neaktivan.
Dijkstra-Solten algoritam za stablo
- Za stablo, lako je otkriti prekid. Kada list proces utvrdi da je prekinut, on šalje signal svojim roditeljima. U principu, proces čeka svoju decu da pošalju signale, a zatim šalje signal svojim roditeljima.
- Program se prekida kada koren primi signale od svig svojih potomaka.
Dijkstra-Solten algoritam za usmerene aciklilne grafove
- Algoritam za stablo može se proširiti do aciklicnih usmerenih grafova. Mi smo dodali još neki ceo deficit atributa svakoj ivici
- Kada primate ivice, deficit će označavati razliku između broja primljenih poruka i broja signala poslatih u odgovoru.
- Kada čvor želi da se otkači, čeka dok ne primi signale od odlaznih ivica smanjujuci njihove deficite na nulu.
- Onda šalje dovolno signala da obezvedi da je deficit nula na svakoj dolaznoj ivici.
- Pošto je aciklicni graf, neki čvorovi neće imati odlazne ivice i ti čvorovi ce biti prvi koji se otkačinju nakon slanja dovolno signala njihovim dolaznim ivicama. Nakon toga ce se čvorovi na višim nivoima otkačinjati nivo po nivo.
Dijkstra-Solten algoritam za ciklične usmerene grafove
- Ako se ciklusi dozvoljeni , prethodni algoriam ne radi. To je zato, što ne može biti koji čvor sa nula odlaznih ivica. Dakle , potencijalno ne postoji čvor koji može da se ukine bez konsultacija sa ostalim čvorovima.
- Dijksta-Solten algoritam rešava ovaj problem imolicitnim stvaranjem razapinjućeg stabla grafa. Razapinjuće stablo je stablo koje uključuje svaki čvor osnovnog grafa jednom i skup ivica je podskup originalnog skupa ivica.
- Stablo ce biti usmereno (tj. grane ce biti usmerene) sa izvornim čvorom (koji inicira obračun) kao koren.
- Razapinjuće stablo se kreira na sledeći nacin. Promenjiva prva_ivica se dodaje svakom čvoru. Kada čvor primi poruku, po prvi put, ona incijalizuje prva_ivica sa izvice kroz koju je primila poruku. Prva_ivica se nikad ne menja posle. Imajte na umu da, razapinjuće stablo nije jedinstveno i zavisi od reda poruka u sistemu.
- Otkačivanje obradjuje svaki čvor u tri koraka:
- Šalje signale svim dolaznim ivicama osim prve ivice (Svaki čvor salje signale što smanjuje deficit svakoj dolaznoj ivici na nulu).
- Čeka signale svih odlaznih ivica. (Broj primljenih signala svake od odlazećih ivica treba da smanji svaki od njihovih deficita na nulu).
- Pošalji signale na prva_ivica. (Kada koraci 1 i 2 budu kompletni, čvor obaveštava svog roditelja u razapinjućem stablu o nameri otkačivanja.)
Vidi još
- Huangov algoritam
Reference
- ^ EW Dijkstra, CS Scholten (1980). „Termination detection for diffusing computations” (PDF). Information Processing Letters.