Дајкстра-Солтенов алгоритам

Дајкстра Солтен алгоритам (назван по Едсгер W. Дијкстра и C. С. Сцхолтен) је алгоритам за налажење прекида у дистрибуираном систему. Алгоритам је предложен од стране Дијкстре и Солтена 1980. године.

Прво, размотримо слуцај једноставног процеса графа који је стабло. Дистрибуиран прорачун који је стабло-структурисан није неуобичајен. Такав процес граф може настати када је израчунавање строго подели-и-владај типа. Чвор почиње обрачун и дели проблем у два (или висе, обично више од 2) поприлично једнака дела и дистрибуира те делове другим процесорима. Овај процес се наставља рекурзивно све док проблеми не буду доволно малих димензија да се реше једним процесором.

Алгоритам

Дијкстра-Солтен алгоритам је алгоритам заснован на стаблу које се може описати на следећи начин:

• Иницијатор рачунања је корен стабла.
• По пријему обрачунске поруке:
  • Ако долазећи процес тренутно није у обрачуну: процес се придрузујуе стаблу постајуци дете посаљилаца поруке.(Без знања да је порука послата у том тренутку)
  • Ако је долазећи процес већ у обрачуну: процес одмах шаље поруку потврде пошаљиоцу поруке.
• Када процес нема висе деце и кад је постао неактиван, процес се одваја од стабла тако што шаље поруку потврде свом родитељу.
• Прекид се јавља када иницијатор нема деце и кад је постао неактиван.

Дијкстра-Солтен алгоритам за стабло

• За стабло, лако је открити прекид. Када лист процес утврди да је прекинут, он шаље сигнал својим родитељима. У принципу, процес чека своју децу да пошаљу сигнале, а затим шаље сигнал својим родитељима.
• Програм се прекида када корен прими сигнале од свиг својих потомака.

Дијкстра-Солтен алгоритам за усмерене ациклилне графове

• Алгоритам за стабло може се проширити до ациклицних усмерених графова. Ми смо додали још неки цео дефицит атрибута свакој ивици
• Када примате ивице, дефицит ће означавати разлику између броја примљених порука и броја сигнала послатих у одговору.
• Када чвор жели да се откачи, чека док не прими сигнале од одлазних ивица смањујуци њихове дефиците на нулу.
• Онда шаље доволно сигнала да обезведи да је дефицит нула на свакој долазној ивици.
• Пошто је ациклицни граф, неки чворови неће имати одлазне ивице и ти чворови це бити први који се откачињу након слања доволно сигнала њиховим долазним ивицама. Након тога це се чворови на вишим нивоима откачињати ниво по ниво.

Дијкстра-Солтен алгоритам за цикличне усмерене графове

• Ако се циклуси дозвољени , претходни алгориам не ради. То је зато, што не може бити који чвор са нула одлазних ивица. Дакле , потенцијално не постоји чвор који може да се укине без консултација са осталим чворовима.
• Дијкста-Солтен алгоритам решава овај проблем имолицитним стварањем разапињућег стабла графа. Разапињуће стабло је стабло које укључује сваки чвор основног графа једном и скуп ивица је подскуп оригиналног скупа ивица.
• Стабло це бити усмерено (тј. гране це бити усмерене) са изворним чвором (који иницира обрачун) као корен.
• Разапињуће стабло се креира на следећи нацин. Промењива прва_ивица се додаје сваком чвору. Када чвор прими поруку, по први пут, она инцијализује прва_ивица са извице кроз коју је примила поруку. Прва_ивица се никад не мења после. Имајте на уму да, разапињуће стабло није јединствено и зависи од реда порука у систему.
• Откачивање обрадјује сваки чвор у три корака:
  1. Шаље сигнале свим долазним ивицама осим прве ивице (Сваки чвор саље сигнале што смањује дефицит свакој долазној ивици на нулу).
  2. Чека сигнале свих одлазних ивица. (Број примљених сигнала сваке од одлазећих ивица треба да смањи сваки од њихових дефицита на нулу).
  3. Пошаљи сигнале на прва_ивица. (Када кораци 1 и 2 буду комплетни, чвор обавештава свог родитеља у разапињућем стаблу о намери откачивања.)

Види још

• Хуангов алгоритам