Быстрый поиск

Реферат: Распределенные алгоритмы

Инициализация:

begin forall w Î Neighu , v Î V do ndisu[w, v] := N ,

forall v Î V do

begin Du[v] := N ;

Nbu[v] := udef

end ;

Du[u]:= 0 ; Nbu[u] := local ;

forall w Î Neighu do послать < mydist, u, 0> к w

end

процедура Recompute (v):

begin if v = u

then begin Du[v]:= 0 ; Nbu[v] := local end

else begin (* оценка расстояния до v *)

d := 1 + min{ ndisu[w, v] : w Î Neighu} ;

if d < N then

begin Du[v] := d ;

Nbu[v] := w with 1 + ndisu[w, v] = d

end

else begin Du[v] := N ; Nbu[v] := udef end

end;

if Du[v] изменилась then

forall x Î Neighu do послать < mydist, v, Du[v]> к x

end

Алгоритм 4.8 Алгоритм Netchange (часть I, для узла u).

Алгоритм требует чтобы узел имел оценки расстояний до v своих соседей. Их они получают от этих узлов послав им сообщение <mydist,.,.> следующим образом. Если узел u вычисляет значение d как оценку своего расстояния до v (Du[v] = d), то эта информация посылается всем соседям в сообщении < mydist ,v,d>. На получение сообщения <mydist, v, d> от соседа w, u означивает ndisu[w, v] значением d. В результате изменения ndisu[w, v] оценка u расстояния d(u, v) может измениться и следовательно оценка перевычисляется каждый раз при изменении таблицы ndisu . Если оценка на самом деле изменилась то, на d' например, происходит соединение с соседями используя сообщение <mydist, v, d'>.

Алгоритм реагирует на отказы и восстановления каналов изменением локальных таблиц, и посылая сообщение <mydist, ., .> если оценка расстояния изменилась. Мы предположим что уведомление которое узлы получают о падении или подъеме канала (предположение N3) представлено в виде сообщений < fail,. > и <repair, . >. Канал между узлами u1 и u2 смоделирован двумя очередями, Q u1 u2 для сообщений от u1 к u1 и Q u2 u1 для сообщений из u2 в u1. Когда канал отказывает эти очереди удаляются из конфигурации (фактически вызывается потеря всех сообщений в обоих очередях) и узлы на обоих концах канала получают сообщение < fail, . > . Если канал между u1 и u1 отказывает, u1 получает сообщение < fail, u2 > и u2 получает сообщение < fail, u1 > . Когда канал восстанавливается (или добавляется новый канал в сети) две пустые очереди добавляются в конфигурацию и два узлы соединяются через канал получая сообщение < repair, . > . Если канал между u1 и u2 поднялся u1 получает сообщение< repair, u2 > и u2 получает сообщение < repair, u1 > .

Обработка сообщения <mydist,v,d> от соседа w:

{ <mydist,v,d> через очередь Qwv}

begin получить <mydist,v,d> от w;

ndisu[w,v] := d ; Recompute (v)

end

Произошел отказ канала uw:

begin получить < fail, w> ; Neighu := Neighu \ {w} ,

forall v Î V do Recompute (v)

end

Произошло восстановление канала uw:

begin получить < repair, w> , Neighu := Neighu È {w} ;

forall v Î V do

begin ndisu[w, v] := N;

послать < mydist, v, Du{[v]> to w

end

Алгоритм 4.9 АЛГОРИТМ NETCHANGE (часть 2, для узла и).

Реакция алгоритма на отказы и восстановления выглядит следующим образом. Когда канал между u и w отказывает, w удаляется из Neighu и наоборот. Оценка расстояния перевычисляется для каждого пункта назначения и, конечно, рассылается всем существующим соседям если оно изменилось. Это случай если лучший маршрут был через отказавший канал и нет другого соседа w' с ndisu[w', v]= ndisu[w, v]. Когда канал восстановлен(или добавлен новый канал) то w добавляется в Neighu, но u имеет теперь неоцененное расстояние d(w, v) (и наоборот). Новый сосед w немедленно информирует относительно Du[v] для всех пунктов назначения v (посылая сообщения<mydist,v, Du[v]> ). До тех пор пока u получает подобное сообщения от w, u использует N как оценку для d(w,v), т.е., он устанавливает ndisu[w, v] в N.

P(u, w, V)º

up(u, w) Û w Î Neighu (1)

Ù up(u, w) Ù Qwu содержит сообщение <mydist,v,d> Þ

последнее такое сообщение удовлетворят d = Du[v] (2)

Ù up(u, w) Ù Qwu не содержит сообщение <mydist,v,d> Þ

ndisu[w, v] =Dw [v] (3)

L(u, v) º

u = v Þ (Du[v] = 0 Ù Nbu[v] = local) (4)

Ù (u ¹ v)Ù $w Î Neighu : ndisu[w, v] < N - 1)Þ

( Du[v] = 1 + min ndisu[w, v] = 1 + ndisu[Nbu[v], v]) (5)

w Î Neigh u

Ù (u ¹ v Ù "w Î Neighu : ndisu[w, v]³ N—1) Þ

(Du[v] = N Ù Nbu[v] = udef) (6)

Рисунок 4.10 Инварианты P(u, w, v) и L(u, v).

Инварианты алгоритма Netchange. Мы докажем что утверждения являются инвариантами; утверждения даны на Рисунке 4.10. Утверждение P(u, w, v) констатирует что если u закончил обработку сообщения <mydist, v, .> от w то оценка u расстояния d(w,v) эквивалентна оценке w расстояния d(w, v). Пусть предикат up(u, w) истинен тогда и только тогда когда (двунаправленный) канал между u и w существует и действует. Утверждение L(u, v) констатирует что оценка u расстояния d(u, v) всегда согласована с локальными данными u, и Nbu[v] таким образом означен.

Выполнение алгоритма заканчивается когда нет больше сообщений в любом канале. Эти конфигурации не терминальны для всей системы так как вычисления в системе могут продолжится позже, начавшись отказом или восстановлением канала (на которые алгоритм должен среагировать). Мы пошлем сообщение конфигурационной стабильности, и определим предикат stable как

stable = "u, w : up(u, w) Þ Qwu не содержит сообщений <mydist,., .>.

Это предполагает что переменные Neighu корректно отражают существующие рабочие коммуникационные каналы, т.е., что (1) существует изначально. Для доказательства инвариантности утверждений мы должны рассмотреть три типа переходов.

(1) Получение сообщения <mydist, .,.> . Первое выполнение результирующего кодового фрагмента, как принято, выполняется автоматически и рассматривается отдельным переходом. Обратите внимание что в данном переходе принимается сообщение и возможно множество сообщений отправляется

(2) Отказ канала и обработка сообщения < fail. . > узлами на обоих концах канала.

(3) Восстановление канала и обработка сообщения <repair. . > двумя соединенными узлами.

Лемма 4.14 Для всех uo, wo, и vo, P(uo, wo, vo) –– инвариант.

Доказательство. Изначально, т.e., после выполнения инициализационной процедуры каждым узлом, (1) содержится предположением. Если изначально мы имеем Øup(uo, wo), (2) и (3) тривиально содержатся. Если изначально мы имеем up(uo, wo), тогда ndisuo[wo, vo] = N. Если wo = vo то Dwo[wo] = 0 но сообщение < mydist, vo, 0> в Qw0u0, таким образом (2) и (3) истинны. Если wo ¹ vo то Dw0[vo]=N и нет сообщений в очереди, что также говорит что (2) и (3) содержаться. Мы рассмотрим три типа констатированных переходов упомянутых выше.