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

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

В течение w-центализованного обхода узлу разрешено принимать и обрабатывать сообщения только данного обхода, т.е., те которые переносят параметр w. Если каналы удовлетворяют дисциплине FIFO тогда сообщения <ys,w> и <nys, w> прибывают первыми, по одному через каждый канал, и затем сообщение < dtab, w, D > от Nbu[ w] (если узел в Vw). Таким образом возможно, аккуратно программируя, опустить параметр w во всех сообщениях если каналы удовлетворяют дисциплине FIFO. Если каналы не удовлетворяют дисциплине FIFO возможно что сообщение с параметром w' придет пока узел ожидает сообщения для обхода w, тогда как w' становится центром после w. В этом случае параметр используется чтобы различить сообщения для каждого централизованного обхода, и локальная буферизация ( в канале и узле) должна использоваться для отсрочки выполнения w'-сообщения.

Toueg дал дальнейшую оптимизацию алгоритма, полагаясь на следующий результат. (Узел u2 потомок u1 если u2 принадлежит поддереву u1)

Лемма 4.10 Пусть u1¹ w, и пусть u2 потомок u1 в Tw, в начале w-централизованного обхода, если u2 изменит своё расстояние до v во время w-централизованного обхода, тогда и u1 изменит своё расстояние до v в этом же обходе.

Доказательство. Так как u2 потомок u1 в Tw :

dS(u2, w) = dS (u2, u1) + dS (u1, w). (1)

Так как u1 Î S:

dS(u2, v) £ dS (u2, u1) + dS (u1,v). (2)

Узел u2 изменит Du2 [v] в данном обходе тогда и только тогда когда

dS(u2, w) + dS (w, v) < dS (u2, v). (3)

Применяя (2), и затем (1), и вычитая dS(u2, u1), мы получим

dS(u1, w) + dS (w, v) < dS (u1, v) (4)

значит u1 изменит Du1 [v] в этом обходе.‰

В соответствии с этой леммой, Алгоритм 4.6 может быть модифицирован следующим образом. После получения таблицы Dw, (сообщение <dtab, w,D>) узел u вначале выполняет локальные w-централизованные операции, и затем рассылает таблицы своим сыновьям в Tw. Когда пересылка таблицы закончилась достаточно переслать те ссылки D[v] для которых Du[v] изменилась в течение локальной w-централизованной операции. С этой модификацией таблицы маршрутизации не содержат циклов не только между централизованными обходами (как сказано в Лемме 4.7), но также в течение централизованных обходов.

4.2.3 Обсуждение и Дополнительные Алгоритмы

Представление алгоритм Toueg предоставило пример как распределенный алгоритм может быть получен непосредственным образом из последовательного алгоритма. Переменные последовательного алгоритма распределены по процессам, и любое означивание переменной x (в последовательном алгоритме) выполняется процессом владеющим x. Всякий раз когда ознaчивающее выражение содержит ссылки на переменные из других процессов, связь между процессами потребуется для передачи значения и синхронизации процессов. Специфические свойства последовательного алгоритма могут быть использованы для минимизации числа соединений.

Алгоритм Toueg прост для понимания, имеет низкую сложность, и маршрутизирует через оптимальные пути; его главный недостаток в его плохая живучесть. Когда топология сети изменилась все вычисления должны произвестись заново.

Во-первых, как ранее говорилось, однообразный выбор всеми узлами следующего центрального узла (w) требует чтобы множество участвующих узлов было известно заранее. Так как это в основном не известно априори, исполнение расширенного распределенного алгоритма вычисления этого множества (на пример алгоритм Финна, Алгоритм 6.9) должно предшествовать исполнению алгоритма Toueg.

Во-вторых, алгоритм Toueg основан на повторяющимися применениями уникальности треугольника d(u, v) £ d(u, w) + d(w, v). Оценивание правой стороны ( u) требует информацию о d(w, v), и эта информация в часто удалена, т.е., не доступна ни в u ни в любой из его соседей. Зависимость от удаленных данных делает необходимым транспортирование информации к удаленным узлам, которые могут быть исследованы в алгоритме Toueg (часть распространения).

Как альтернатива, определенное ниже равенство для d(u, v) может использоваться в алгоритмах для проблем кротчайших путей:

ì 0 если u=v

d(u,v)= í (4.1)

î wuw+d(w,v) иначе

Два свойства этого равенства делают алгоритмы основанные на этом отличными от алгоритма Toueg.

(1) Локальность данных. Во время оценивания правой стороны равенством (4.1), узлу u необходима только информация доступная локально (именно, wuw) или в соседях (именно, d(w, v)). Транспортирование данных между удаленными вершинами избегается.

(2) Независимость пункта назначения. Расстояния до v (именно, d(w, v) где w сосед u) только нуждаются в вычислении расстояния от u в v. Таким образом, вычисление всех расстояний до фиксированного пункта назначения vo может происходить независимо от вычисления расстояния до других узлов, и также, может бать сделано обособленно.

В завершение этой части обсуждены два алгоритма основанные на равенстве, а именно алгоритмы Мерлина-Сигалла и Чанди-Мизра. Не смотря на преимущества от локальности данных, сложность соединений этих алгоритмов не лучше алгоритма Toueg. Это из-за независимости пункта назначения введенного равенством(4.1); очевидно, использование результатов для других пунктов назначения (как сделано в алгоритме Toueg) более выгодный прием чем локальность данных.

Если это не ведет к уменьшению сложности соединений, тогда каково значение локальности данных? Уверенность в удаленных данных требует повторных распространений если данные могли измениться из-за топологических изменений сети. Доведение до конца этих распространений (с возможными новыми топологическими изменениями в течение распространения) вызывает нетривиальные проблемы с дорогими решениями (см., на пример, [Gaf87]). Более того, алгоритмы основанные на равенстве 4.1 могут быть более легко адаптированы к топологическим изменениям. Оно служит примером в части 4.3, где подробно разобран такой алгоритм.

Алгоритм Мерлина-Сигалла. Алгоритм предложенный Мерлином и Сигаллом [MS79] вычисляет таблицы маршрутизации для каждого пункта назначения абсолютно обособленно; вычисления для различных пунктов назначения не оказывают влияния друг на друга. Для пункта назначения v, алгоритм начинает работу с дерева Tv с корнем в v, и повторно перевычисляет это дерево с тем чтобы оно стало оптимальным деревом стока для v.

Для пункта назначения v, каждый узел u содержит оценку расстояния до v (Du[v]) и соседа через которого пакет для u пересылается (Nbu[v]), который также является отцом u в Tv. В период перевычисления каждый узел u посылает свою оценку расстояния, Du[v], к всем соседям исключая Nbu[v] (в < mydist, v, Du[v]> сообщении). Если узел u получает от соседа w сообщение <mydist,v,d> и если d+wuv < Du[v], u изменит Nbu[v] на w и Du[v] на d + wuv. Период перевычисления контролируется узлом v и требует обмена двумя сообщениями в W бит на каждый канал.

В [MS79] показано что после i периодов перевычислений все кротчайшие пути в более чем i шагов будут корректно вычислены, так что после N раундов все кротчайшие пути будут вычислены. Кротчайшие пути в каждый пункт назначения вычисляются выполнением алгоритма независимо для каждого пункта назначения.

Теорема 4.11 Алгоритм Мерлина и Сигалла вычисляет таблицы маршрутизации кротчайших путей с обменом 0(N2) сообщениями на канал, 0(N2 W) битами на канал, 0(N2 |E|) сообщениями всего, и 0(N2|E|W) битами всего.

Алгоритм может также адаптироваться к изменениям топологии и весов каналов. Важное свойство алгоритма в том что в течение периода перевычислений таблицы маршрутизации не содержат циклов.

Алгоритм Чанди—Мизра. Алгоритм предложенный Чанди и Мизра [CM82] вычисляет все кротчайшие вычисляет до одного пункта назначения используя парадигму диффузивных вычислений (распределенные вычисления которые инициируются одним узлом, и другие узлы присоединяются только после получения сообщения).

Вычисление, для всех узлов, расстояния до узла vo (и привилегированного исходящего канала), каждый узел u начинает с Du[vo] = ¥ и ждет получения сообщений. Узел vo посылает <mydist,vo,0> сообщение всем соседям. Когда же узел u получает сообщение <maydist,vo,d> от соседа w, где d + wuw < Du[vo], u заносит значение d+wuv в Du[vo] и посылает сообщение < mydist, vo, D Du[vo]> всем соседям; смотри Алгоритм 4.7.