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

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

Лемма 4.7 Пусть даны S и w и выполняется:

(1) для всех u :Du[w] = dS(u, w) и

(2) если dS(u, w) < ¥ и u ¹ w, то Nbu[w]- первый канал кратчайшего S-пути к w.

Тогда направленный граф Tw = (Vw, Ew), где (u Î Vw Û Du[w]<¥ ) и (ux ÎEw Û (v¹wÙNbu[w]=x)) - дерево с дугами направленными к w.

Доказательство. Во-первых, заметим, что если Du[w] < ¥ для u ¹ w, то Nbu[w] ¹ udef и . Таким образом для каждого узла u Î Vw, u ¹ w существует узел x для которого Nbu[w] = x, и x Î Vw.

Для каждого узла u¹ w в Vw существует единственное ребро в Ew, такое что число узлов в Tw превышает количество ребер на единицу и достаточно показать что Tw не содержит циклов. Так ux ÎEw подразумевает что dS(u, w) =wux+ dS(x, w), существование цикла <uo, u1, .. ., uk> в Tw подразумевает что

dS(uo, w) = wuo u1 + wu1 u2 + … + wuk-1 uou+ dS(uo, w),

т.е., 0 = wuo u1 + wu1 u2 + … + wuk-1 uou

что противоречит предположению, что каждый цикл имеет положительный вес. ‰

Алгоритм Флойда-Уошала теперь может быть просто преобразован в Алгоритм 4.5. Каждый узел инициализирует свои собственные переменные и исполняет N итераций основного цикла. Этот алгоритм не является окончательным решением, и он не дан полностью, потому что мы не описали, как может бать произведено (эффективно) распространение таблиц центрального узла. Пока это можно использовать как гарантированное, поскольку операция "распространить таблицу Dw" выполняется узлом w, а операция "принять таблицу Dw" выполняется другими узлами, и каждый узел имеет доступ к таблице Dw.

Некоторое внимание должно быть уделено операции "выбрать w из V \ S", чтобы узлы выбирали центры в однообразном порядке. Так как все узлы знают V заранее, мы можем запросто предположить, что узлы выбираются в некотором предписанном порядке (на пример, алфавитный порядок имен узлов).

Корректность простого алгоритма доказана в следующей теореме.

Теорема 4.8 Алгоритм 4.5 завершит свою работу в каждом узле после N итераций основного цикла. Когда алгоритм завершит свою работу в узле u Du[v] = d(u, v), и если путь из u в v существует то Nbu[v] первый канал кротчайшего пути из u в v, иначе Nbu[v] = udef.

Доказательство. Завершение и корректность Du[v] по завершении работы следует из корректности алгоритма Флойда-Уошала (теорема 4.6). Утверждение о значении Nbu[v] справедливо потому что Nbu[v] перевычисляется каждый раз когда означивается Du[v] .‰

Усовершенствованный алгоритм. Чтобы сделать распространение в Алгоритме 4.5 эффективным, Toueg заметил, что узел u для каждого Du[w] = ¥ на старте w-централизованного обхода не меняет свои таблицы в течение всего w-централизованного обхода. Если Du[w] = ¥ , то Du[w] + Dw[v] < Du[v] не выполняется для каждого узда v. Следовательно, только узлы, принадлежащие Tw (в начале w-централизованного обхода) нуждаются в получении таблиц w, и операция распространения может стать более эффективной рассылая Dw только через каналы, принадлежащие дереву Tw. Таким образом, w рассылает Dw своим сыновьям в Tw и каждый узел в Tw который принимает таблицу (от своего отца в Tw) пересылает её к своим сыновьям в Tw.

____________________________________________________________________

var Su : множество узлов ;

Du : массив весов;

Nbu : массив узлов ;

begin

Su := Æ ;

forall v Î V do

if v = u

then begin Du[v] := O ; Nbu[v] := udef end

else if v Î Neighu

then begin Du[v] := wuv ; Nbu[v] := v end

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

while Su ¹ V do

begin выбрать w из V \ Su ;

(* Построение дерева Tw *)

forall x Î Neighu do

if Nbu[w] = x then send < ys, w> to x

else send < nys, w > to x ;

num_recu := O ; (* u должен получить |Neighu| сообщений *)

while num_recu < |Neighu| do

begin получить < ys, w > или < nys, w > сообщение ;

num_recu := num_recu + 1

end;

if Du[w] < ¥ then (* участвует в центр. обходе*)

begin if u¹ w

then получить <dtab,w,D> от Nbu[w] ;

forall x Î Neighu do

if < ys, w > было послано от x

then послать < dtab, w, D>) к x; ;

forall v Î V do (* локальный w-центр *)

if Du[w] + D[v] < Du[v] then

begin Du[v] := Du[w] + D[v] :

Nbu[v] := Nbu[w]

end

end;

Su := Su È {w}

end

Алгоритм 4.6 Алгоритм Тoueg (для узла u).

_____________________________________________________________________

В начале w-централизованного раунда узел u с Du[w] < ¥ знает кто его отец (в Tw) , но не знает кто его сыновья. Поэтому каждый узел v должен послать сообщение к каждому своему соседу u, спрашивая u является ли v сыном u в Tw. Полный алгоритм дан как Алгоритм 4.6. Узел может участвовать в пересылке таблицы w когда известно что его соседи являются его сыновьями в Tw. Алгоритм использует три типа сообщений:

(1) <ys,w> сообщение <ys обозначение для "your son"> u посылает к x; в начале w-централизованного обхода если x отец u в Tw.

(2) <nys, w> сообщение <nys обозначение для "not your son"> u посылает x в начале w-централизованного обхода если x не отец u в Tw

(3) <dtab, w, D> сообщение посылается в течение w-централизованного обхода через каждое ребро Tw чтобы переслать значение Dw к каждому узлу который должен использовать это значение.

Полагая сто вес (ребра или пути) вместе с именем узла можно представить W битами, сложность алгоритма показана следующей теоремой.

Теорема 4.9 Алгоритм 4.6 вычисляет для каждых u и v дистанцию от u к v, и, если эта дистанция конечная, первый канал. Алгоритм обменивается 0(N) сообщениями на канал,, 0(N*|E|) сообщений всего, O(N2W) бит на канал, O(N 3W) бит всего, и требуется 0(NW) бит хранения на узел.

Доказательство. Алгоритм 4.6 выведен от Алгоритма 4.5, который корректен.

Каждый канал переносит два ( < ys, w> или < nys, w> ) сообщений (одно в каждом направлении) и не более одного <dtab, w, D > сообщения в w-централизованном обходе, который включает не более 3N сообщений на канал. < ys, w > или < nys, w > сообщение содержит O(W) бит и <dtab, w, D > сообщение содержит O(NW) бит, что и является границей для числа бит на канал. Не более N2 < dtab, w,D> сообщений и 2N - |E| (<ys,w> и <nys,w> ) сообщений обмена, и того всего O(N2 - NW +2N-|E|-W) = O(N3W) бит. Таблицы Du и Nbu хранящиеся в узле u требуют 0(NW) бит.‰