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.

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:
  1. Šalje signale svim dolaznim ivicama osim prve ivice (Svaki čvor salje signale što smanjuje deficit svakoj dolaznoj ivici na nulu).
  2. Čeka signale svih odlaznih ivica. (Broj primljenih signala svake od odlazećih ivica treba da smanji svaki od njihovih deficita na nulu).
  3. 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