Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 36
Текст из файла (страница 36)
Завершаемость и частичная корректность нашегоалгоритма следуют из корректности алгоритма Флойда—Уоршалла (теорема 4.6).Отсюда следует и справедливость утверждения о значении переменной Nbu[v],поскольку значение Nba[v] изменяется всякий раз, когда переменной Du\v] присваивается новое значение.□4.2. Задача построения кратчайших путей для всех пар вершин129var Su'■set of nodes ;Du '■аггаУ weights ;Nbu '■array of nodes ;begin Su := 0 ;forall v 6 V doif v = иthen begin Du[v\ := 0 ; Nbu[v] := udef endelse if a € Neighuthen begin Du[v\ := <o„„ ; Nbu[v] := v endelse begin Du[v\ := oo ; Nbu[v] := udef end;while Su ф V dobegin pick w from V \ Su ;(* Построить дерево Tw *)forall x e Neighu doif Nbu[w\ = x then send (ys, w) to x else send (nys, w) to x ;recu '.= 0 ; (* и должен получить \Neighu\ сообщений *)while recu < \Neighu\ dobegin receive (ys, w ) or (nys, w ) message ; recu := recu + 1 end;if Du[w] < oo then (* принять участие в обработке опорной вершины *)begin if и ф w then receive (dtab, w , D ) from Nbu[w\ ;forall x € Neighu doif (ys, w) was received from x then send (dtab, w, D) to x ;forall v e V do(* local ay-pivot *)if £>и[ay] + D[v\ < Du[v] thenbegin Du[v\ := Du[w\ + D[v]\ Nbu[v\ := Nbu[w\ endend;Su := Su U {ay}endendАлгоритм 4.6.
Алгоритм Туэга (для узла и).Улучшенный алгоритм. Чтобы эффективно провести широковещательнуюрассылку в алгоритме 4.5, Туэг обратил внимание на то, что если узел и удовлетворяет условию Du[w] = оо в начале этапа обработки опорной вершины, то поокончании обработки этой вершины таблица маршрутизации этого узла остаетсянеизменной. Если Du[w] = оо, то неравенство Du[w\ + Dw[v\ < Du[v] неверно для каждой вершины v. Следовательно, таблицу маршрутизации вершины данужно доставить только в те узлы, которые принадлежат дереву Тт (в том виде,в котором оно было сформировано к началу этапа обработки опорной вершины),и операцию широковещательной рассылки можно провести эффективно, отправляя таблицу Dw только по тем каналам, которые входят в состав дерева Tw. Такимобразом, узел да отправляет таблицу Dw своим сыновним вершинам в дереве Tw,и каждый узел в дереве Tw, получивший эту таблицу от родительской вершиныв дереве Tw, переправляет ее своим сыновним вершинам в дереве Tw.130Гл.
4. Алгоритмы маршрутизацииВ начале этапа обработки опорной вершины да каждый узел и, для которого выполнено условие Du[w] < оо, осведомлен о том, какая вершина являетсяего родителем в дереве Тш, но не располагает сведениями о том, какие вершиныявляются его сыновними вершинами. Поэтому любой узел v должен отправитьсообщение каждому своему соседу и, сообщив процессу и, является ли v сыновней вершиной для и в дереве Тш. Полное решение задачи представлено в описанииалгоритма 4.6. Всякий узел может принять участие в распространении таблицыопорной вершины да, как только он получит известия о том, какие из соседейявляются его сыновними вершинами в дереве Тш. В алгоритме используются сообщения трех типов.1. Сообщение (ys, да) (ys от «your son») отправляется от узла и к узлу хв начале этапа обработки опорной вершины да, если х является родительскойвершиной для и в дереве Tw.2.
Сообщение (nys, да) (nys от «not your son») отправляется от узла и к узлух в начале этапа обработки опорной вершины да, если х не является родительскойвершиной для и в дереве Tw.3. Сообщение (dtab, да, D) отправляется по ходу обработки опорной вершины да по каждому ребру дерева Тш, чтобы доставить таблицу Dw в каждуювершину, которая должна будет воспользоваться этим значением.Если известно, что для описания веса (ребра или пути) в совокупности с именем вершины достаточно W битов, то для оценки сложности представленногоалгоритма можно обратиться к следующей теореме.Теорема 4.9. Для каждой пары вершин и и v алгоритм 4.6 вычисляетрасстояние между и и v, а в том случае, когда это расстояние конечно,также определяет первый канал в кратчайшем пути.По ходу работы алгоритма по каждому каналу проходит 0(N) сообщенийи 0(N2W) битов информации.
Таким образом, суммарно по ходу работыалгоритма передается 0 (N ■|£|) сообщений и 0(N 3-W) битов информации.Кроме того, в каждом узле используется память, объем которой составляет 0(N ■W) битов.Д о к а з а т е л ь с т в о . Алгоритм 4.6 построен на основе алгоритма 4.5,и это гарантирует его корректность.На каждом этапе обработки опорной вершины да по каждому каналу связипроходят два сообщения вида (ys, да) или (nys, да) (по одному сообщению в каждом направлении) и не более одного сообщения вида (dtab, да, D), и, значит, завремя работы алгоритма по каждому каналу проходит не более ЗА сообщений.Сообщения вида (ys, да) или (nys, да) содержат 0(W ) битов, а сообщение вида(dtab, да, D) содержит 0(NW) битов, и отсюда следует верхняя оценка битовой сложности обмена информацией по каждому каналу связи.
За время работы алгоритма передается не более А2 сообщений вида (dtab, да, D) и 2А • |£|сообщений вида (ys, да) и (nys, да); таким образом, всего по сети передается0(А 2 • N W + 2А • |£| • W) = 0(А 3 W) битов информации. Для хранения таблиц Duи Nbu каждому процессу и требуется 0(NW) битов памяти.□4.2. Задача построения кратчайших путей для всех пар вершин131На протяжении одного этапа обработки опорной вершины да каждому узлуразрешается передавать и получать только те сообщения, которые имеют отношение к текущему этапу, т.
е. такие сообщения, в которых в качестве параметрасодержится имя вершины да. Если в каналах соблюдается очередность сообщений, то первые сообщения, которые получит каждый узел в начале очередногоэтапа обработки опорной вершины, — это сообщения вида (ys, да) и (nys, да),передаваемые по каждому каналу; затем от узла Nbu\w] будет получено сообщение вида (dtab, да, D) (если узел-адресат содержится в множестве вершин Vw).Аккуратное программирование позволяет избавиться от параметра да во всех сообщениях, если в каналах связи соблюдается очередность сообщений. Если жеочередность следования сообщений нарушается, может случиться так, что узелполучит сообщение с параметром да', в то время как он ожидает поступлениясообщения с параметром да, причем опорная вершина да' следует по порядку заопорной вершиной да.
В этом случае параметр да позволяет разобраться с тем,какому этапу обработки опорных вершин соответствует полученное сообщение;далее, воспользовавшись локальной буферизацией сообщений (в рамках каналаили процесса), можно устанавливать правильный порядок обработки сообщений.Туэг провел дальнейшую оптимизацию предложенного алгоритма, опираясь наследующее утверждение. (Вершина и2 считается потомком вершины щ, если « 2принадлежит поддереву с корнем и\.)Лемма 4.10. Пусть и\ ф да, и пусть вершина U2 является потомкомвершины и\ в дереве Тт в начале этапа обработки опорной вершины да.Если на этапе обработки опорной вершины да изменяется расстояниемежду вершиной U2 и некоторой вершиной и, то на этом этапе такжеизменяется расстояние между вершиной и\ и вершиной и.Доказательство.ны Mi в дереве Tw ,Коль скоро Мг является потомком вершины вершиds (u2 , да) = ds (u2 , M i ) + ds (u\, да).(1)Так как и\ <ЕS, мы имеем неравенствоds (u2 , v) ^ ds (u2 , Mi) + ds (u\, v).(2)На этом этапе значение DU2[о] изменяется в узле U2 в том и только том случае,когдаds (u2 , да) + ds (w, v) < ds (u2 , v).(3)Воспользовавшись неравенствами (2) и (3), подставив правую часть равенства (1)вместо ds (u2 , да) и вычтя из обеих частей образовавшегося неравенства ds (u2 , M i ) ,мы получаем соотношениеds {u\, да) + ds (w, v) < ds (u\, v),(4)из которого следует, что на этом этапе в узле и\ также изменяется значениепеременной DUl [о].□132Гл.
4. Алгоритмы маршрутизацииСогласно доказанной лемме, алгоритм 4.6 можно улучшить следующим образом. После того как узел и получает сообщение (dtab, w, D) и получает доступ ктаблице Dw, в нем вначале выполняется локальная обработка опорной вершиныw, а затем таблица Dw отправляется сыновним вершинам узла и в дереве Tw. Приэтом достаточно передать лишь те элементы таблицы D[v], для которых в узлеи в ходе локальной обработки опорной вершины w изменились значения Du[v],Предложенная модификация позволяет получать ациклические таблицы маршрутизации не только в конце каждого этапа обработки опорных вершин (о чемсвидетельствует лемма 4.7), но также на всем протяжении этапа обработки опорных вершин.4.2.3. Другие алгоритмыПриведенное описание алгоритма Туэга является примером того, как распределенный алгоритм решения некоторой задачи получается непосредственноиз последовательного алгоритма решения той же задачи.
Для этого переменныепоследовательного алгоритма разносятся по разным процессам; присваиваниепеременной л: (в последовательном алгоритме) выполняет тот процесс, которомуназначена переменная х. Всякий раз, когда в операторе присваивания используются переменные, назначенные другим процессам, необходимо совершить обмен сообщениями между процессами, чтобы доставить значения этих переменныхи провести синхронизацию действий процессов. Для того чтобы свести обмен сообщениями к минимуму, можно использовать те или иные особенности исходногопоследовательного алгоритма.Алгоритм Туэга достаточно прост для понимания, имеет небольшую сложность и строит оптимальные маршруты; главным недостатком алгоритма является плохая устойчивость («робастность»). Как только изменяется топология сети,все вычисления нужно проводить заново.
Кроме того, у алгоритма есть две особенности, из-за которых он становится менее привлекательным с точки зренияпроектирования распределенных алгоритмов.Во-первых, как уже было упомянуто, согласованный выбор очередной опорной вершины (w ) всеми узлами сети предполагает, что множество участвующихв алгоритме процессов заранее известно. Но поскольку в общем случае множество участников заранее неизвестно, перед тем как запустить алгоритм Туэга,нужно применить вспомогательный распределенный алгоритм (например, алгоритм Финна (алгоритм 6.8)), чтобы вычислить это множество.Во-вторых, в основу алгоритма Туэга положено многократное применениенеравенства треугольника d(u, v) ^ d(u, w) + d(w, v).
Для вычисления правой части этого неравенства (в узле и) требуется информация о d(w , и), а этаинформация в общем случае оказывается удаленной, т. е. ею не обладает нипроцесс и, ни его соседи. Зависимость от удаленных данных вынуждает нас организовать доставку этой информации удаленным вершинам; в алгоритме Туэгаэтим занимается блок широковещательного распространения сообщений.В качестве альтернативы мы можем рассмотреть следующее уравнение, определяющее значения d(u, v), которое можно использовать в алгоритме построения4.2. Задача построения кратчайших путей для всех пар вершин133кратчайших путей:d(u , и)О,minwENeigh,uесли и = и;n uw + d(w, v) иначе.(4.1)Два свойства этого уравнения позволяют конструировать алгоритмы, которыебудут отличаться от алгоритма Туэга.1.
Локальность данных. Для вычисления правой части уравнения (4.1) в узлеи требуется только локально доступная информация (а именно a uw) или информация, которая имеется у соседей (а именно d(w, и)). Необходимость в обменеданными между удаленными вершинами отпадает.2. Независимость от вершин-адресатов. Для вычисления расстояния между вершинами и и и требуется знать только расстояние d(w, v) между v и всемисоседями w вершины и. Поэтому вычисление и анализ всех расстояний до заданной вершины-адресата vq можно проводить независимо от вычислений расстояний до других вершин сети.В оставшейся части этого параграфа мы обсудим два алгоритма, в основукоторых положено уравнение (4.1), а именно алгоритм Мерлина—Сигалла и алгоритм Чанди—Мисры. Несмотря на те преимущества, которые открываютсяв связи с локальностью данных, коммуникационная сложность этих алгоритмов ничуть не лучше, чем сложность алгоритма Туэга.
Это объясняется свойством независимости от вершины-адресата, которым обладает уравнение (4.1);на самом деле использование результатов, которые были получены для другихвершин-адресатов (как это осуществляется в алгоритме Туэга), представляетсяболее выгодным методом, нежели введение локальности данных.Но если уменьшения коммуникационной сложности не происходит, то почему же столь важна локальность данных? Зависимость вычисления от удаленныхданных приводит к тому, что эти данные приходится широковещательно распространять много раз, если они становятся другими вследствие изменений топологической структуры сети из-за отказов и возобновления работы каналов и узлов.А проведение широковещательной рассылки сообщений (если иметь при этомв виду, что в ходе самой рассылки могут происходить и другие топологическиеизменения) — это очень непростая задача, решение которой требует большихзатрат (см., например, [95]).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
