Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 70
Текст из файла (страница 70)
Если F является фрагментом и e — ребро наименьшего веса, исходящее из F, то F ∪ {e} также является фрагментом.Минимальное остовное дерево. Рассмотрим взвешенный граф G = (V, E)и для обозначения веса ребра e будем использовать запись (e). Вес остовногодерева T в графе G полагается равным сумме весов всех N − 1 ребер, входящих в состав T, и при этом T называется минимальным остовным деревомили сокращенно MST (иногда его называют также остовным деревом минимального веса), если ни одно остовное дерево не имеет вес, меньший чем T.
В этомпараграфе мы будем полагать, что каждое ребро имеет уникальный вес, т. е. различные ребра имеют различные веса; хорошо известно, что в таком случае в графесуществует единственное минимальное остовное дерево.Д о к а з а т е л ь с т в о. Допустим, что F ∪{e} не является фрагментом MST.Тогда e наряду с некоторыми ребрами MST образует цикл и при этом одно из ребер этого цикла, принадлежащее MST (например f), является ребром, исходящимиз фрагмента F. Согласно выбору ребра e справедливо неравенство (e) < (f);но в таком случае после изъятия ребра f из MST и добавления вместо него ребраe, мы получили бы дерево, вес которого был бы меньше веса MST, т. е.
пришлибы к противоречию.Хорошо известны последовательные алгоритмы построения MST, среди которых можно отметить алгоритмы Прима и Краскала. Алгоритм Прима (см. [55,раздел 24.2]) начинает работу с простейшего фрагмента и на каждом шаге расширяет его, добавляя ребро наименьшего веса, исходящее из построенного к томувремени фрагмента. Алгоритм Краскала (см. [55, раздел 24.2]) начинает работу, располагая семейством фрагментов, состоящих из одного узла, и проводитих соединение, добавляя ребра наименьшего веса, исходящие из того или иногофрагмента.
Поскольку в алгоритме Краскала разрешается работать независимо с несколькими фрагментами, он более подходит для реализации в качествераспределенного алгоритма.Предложение 7.18. Если все веса ребер попарно различны, то существует только одно MST.7.3.3. Глобальное описание алгоритма GHS.Д о к а з а т е л ь с т в о. Допустим противное и рассмотрим случай, когдаоба дерева T1 и T2 (причем T1 6= T2) являются минимальными остовными деревьями. Рассмотрим ребро e наименьшего веса, которое содержится в одном изэтих деревьев, но не содержится в другом; такое ребро существует, ибо T 1 6= T2 .Допустим, не умаляя общности, что e принадлежит T 1 , но не входит в состав T2 .Тогда граф T2 ∪ {e} содержит цикл, и, поскольку в дереве T1 нет циклов, хотя быодно ребро этого цикла, скажем ребро e0 , не содержится в T1 . Согласно выборуребра e, справедливо неравенство (e) < (e0). Но тогда дерево T2 ∪ {e} \ {e0 }имеет вес, меньший чем T2 , вопреки тому, что T2 является MST.Вначале мы расскажем о глобальной работе алгоритма, т.
е. опишем, как алгоритм обращается с фрагментами. Затем мы приведем локальный алгоритм, описывающий действия, которые должны выполняться в каждом узле сети, чтобыосуществить эти глобальные операции над фрагментами.Всякое вычисление алгоритма GHS складывается из следующих шагов.1. Формируется такое семейство фрагментов, что объединение их содержитвсе узлы сети.2.
Первоначально это семейство состоит из всех узлов сети, каждый из которых рассматривается как граф с одним узлом.264Гл. 7. Алгоритмы избрания лидера3. Узлы всякого фрагмента вступают во взаимодействие с целью выявленияисходящего из фрагмента ребра с наименьшим весом.4. Как только будет определено исходящее из фрагмента ребро с наименьшим весом, данный фрагмент соединяется с другим фрагментом путем добавленияэтого исходящего ребра, которое строится в результате взаимодействия этих двухфрагментов.5. Алгоритм завершает работу, как только останется только один фрагмент.Для эффективной реализации этих шагов потребуется ввести некоторые обозначения и операции.1. Имя фрагмента. Чтобы определить исходящее ребро наименьшего веса,необходимо суметь проверить, выводит ли некоторое ребро за пределы фрагмента или оно ведет в узел того же самого фрагмента.
Для этого каждый фрагментбудет наделен именем, которое будет известно всем процессам, входящим в этотфрагмент. Процессы будут проверять, является ли ребро внутренним или внешним ребром, сравнивая имена фрагментов, к которым они относятся.2. Соединение старшего и младшего фрагментов. Когда два фрагментасоединяются, в процессах хотя бы одного из этих фрагментов происходит перемена имени фрагмента; для этого требуется, чтобы изменение имени произошлов каждой точке по крайней мере одного из указанных фрагментов.
Чтобы осуществить это изменение эффективно, в основу стратегии соединения фрагментовположен следующий принцип: младший из двух фрагментов присоединяетсяк старшему из них и принимает имя старшего фрагмента.3. Ранги фрагментов. После небольшого размышления становится ясно,что решение о том, какой из фрагментов старше, нельзя основывать на количестве узлов в этих фрагментах. В таком случае размер фрагмента пришлосьбы уточнять в каждом процессе обоих фрагментов-компонент и, таким образом, нарушать взятое обязательство проводить уточнения только в младшем издвух фрагментов.
Вместо этого каждому фрагменту сопоставляется ранг, который первоначально полагается равным 0 для любого фрагмента, состоящего изодного узла. Некоторый фрагмент F1 может соединиться с фрагментом F2 более высокого ранга, после чего новый фрагмент F1 ∪ F2 будет иметь такой жеранг, как и фрагмент F2 . Этот новый фрагмент унаследует имя фрагмента F2 ,и поэтому в узлах фрагмента F2 не потребуется проводить никаких уточнений.Неизбежно также и соединение двух фрагментов одного и того же ранга; в этомслучае новый фрагмент будет носить новое имя и его ранг будет на единицупревосходить ранг соединенных фрагментов.
Именем образовавшегося фрагмента будет вес того ребра, которое соединило два исходных фрагмента; указанноеребро назовем стержнем нового фрагмента. Те два узла, которые соединеныребром-стержнем, будут называться стержневыми узлами.Лемма 7.20. Если соблюдать указанные выше правила соединения фрагментов, то суммарно во всех процессах перемена имени или ранга случится не более N log N раз.Д о к а з а т е л ь с т в о. Ранг всякого процесса не понижается, и лишь в томслучае, когда он повышается, процесс вынужден переменить имя своего фрагмен-7.3. Произвольные сети265та.
Фрагмент ранга L содержит не менее 2L процессов, и поэтому максимальновозможный ранг равен log N. Отсюда следует, что в каждом отдельном процессеранг содержащего его фрагмента повышается не более log N раз. Значит, общеечисло перемен имени и ранга фрагмента ограничено величиной N log N.Краткое изложение стратегии соединения. Для обозначения фрагмента Fс именем FN и рангом L будем использовать запись F = (FN, L). Обозначимсимволом eF исходящее из фрагмента F ребро наименьшего веса.Правило A. Если eF ведет в такой фрагмент F 0 = (FN0 , L0), для которогоL < L0 , то фрагмент F присоединяется к F 0 и образовавшийся при этом новыйфрагмент сохраняет имя FN 0 и ранг L0 .
Эти новые значения отправляются всемпроцессам, входящим в состав F.Правило B. Если eF ведет в такой фрагмент F 0 = (FN0 , L0), для которогоL = L0 и eF0 = eF , то эти два фрагмента соединяются и образуют один новыйфрагмент, который будет носить имя (eF) и иметь ранг L + 1. Эти новые значенияотправляются всем процессам, входящим в состав F и F 0 .Правило C. Во всех остальных случаях (т. е. когда либо L > L 0 , либо L == L0 и eF0 6= eF) фрагмент F должен ожидать, когда откроется возможностьприменения правила A или B.7.3.4. Подробное описание алгоритма GHSСтатус узлов и связей. Как отмечено в описании алгоритма 7.10, в узле pзадействовано несколько локальных переменных, среди которых есть переменные статуса каналов stachp [q] для каждого канала связи pq. Канал может иметьодин из следующих трех статусов: branch, если известно, что соответствующееребро входит в MST, reject, если известно, что это ребро не входит в MST,и basic, если данное ребро еще не было использовано.
Обмен сообщениями вофрагменте с целью выявления исходящего ребра наименьшего веса проводитсяпо ребрам типа branch. Для всякого процесса p рассматриваемого фрагмента запись fatherp будет обозначать то ребро, которое ведет к стержню данногофрагмента. Состоянием statep узла p может быть либо find, если процесс p привлечен к проводимому во фрагменте поиску исходящего ребра наименьшего веса,либо found в противном случае.
Описание алгоритма GHS состоит из трех частей 7.10/7.11/7.12. Иногда обработка сообщений может быть отложена, до техпор пока не будет выполнено некоторое локальное условие. В таком случае мыбудем подразумевать, что анализируемое сообщение сохраняется в памяти. Впоследствии оно извлекается из памяти и обрабатывается так, как будто оно былотолько что получено. Если процесс получает сообщение, пребывая все еще в состоянии sleep, то перед тем как приступить к обработке этого сообщения, нашалгоритм проходит в этой точке этап инициализации (выполняя действие (1)).Поиск исходящего ребра наименьшего веса.
Все узлы фрагмента участвуют совместно в поиске исходящего из этого фрагмента ребра наименьшего веса,и как только такое ребро будет обнаружено, по нему отправляется сообщение266Гл. 7. Алгоритмы избрания лидераvar statep: (sleep, find, found) ;stachp [q]: (basic, branch, reject) для каждого q ∈ Neighp ;namep , bestwtp: real;levelp: integer;testchp , bestchp , fatherp : Neighp ;recp: integer;(1) Первым действием каждого процесса является инициализация данного алгоритма:begin пусть pq — это канал связи процесса p, имеющий наименьший вес ;stachp [q] := branch ; levelp := 0 ;statep := found ; recp := 0 ;send hconnect, 0i to qend(2) После получения сообщения hconnect, Li от q:begin if L < levelp then (* Соединить по правилу A *)begin stachp [q] := branch ;send hinitiate, levelp , namep , statep i to qendelse if stachp [q] = basicthen (* Правило C *) обработать это сообщение позднееelse (* Правило B *) send hinitiate, levelp + 1, (pq), findi to qend(3) После получения сообщения hinitiate, L, F, Si от q:begin levelp := L ; namep := F ; statep := S ; fatherp := q ;bestchp := udef ; bestwtp := ∞ ;forall r ∈ Neighp : stachp [r] = branch ∧ r 6= q dosend hinitiate, L, F, Si to r ;if statep = find then begin recp := 0 ; test endend7.3.
Произвольные сети267(4) procedure test:begin if ∃q ∈ Neighp : stachp [q] = basic thenbegin testchp := q with stachp [q] = basic and (pq) minimal ;send htest, levelp , namep i to testchpendelse begin testchp := udef ; report endend(5) После получения сообщения htest, L, F i от q:begin if L > levelp then (* С ответом придется подождать! *)обработать это сообщение позднееelse if F = namep then (* внутреннее ребро *)begin if stachp [q] = basic then stachp [q] := reject ;if q 6= testchpthen send hrejecti to qelse testendelse send haccepti to qend(6) После получения сообщения haccepti от q:begin testchp := udef ;if (pq) < bestwtpthen begin bestwtp := (pq) ; bestchp := q end;reportend(7) После получения сообщения hrejecti от q:begin if stachp [q] = basic then stachp [q] := reject;testendАлгоритм 7.10.
Алгоритм Галладжера—Хамблета—Спиры (Часть 1).Алгоритм 7.11. Алгоритм Галладжера—Хамблета—Спиры (Часть 2).hconnect, Li, где L — ранг данного фрагмента. Если фрагмент состоит из единственного узла, как это случается после инициализации такого узла, то нужноеребро — это просто инцидентное данному узлу ребро наименьшего веса (см. действие (1)), и сообщение hconnect, 0i отправляется по этому ребру.Теперь рассмотрим случай, когда новый фрагмент образовался за счет соединения двух фрагментов ребром e = pq. Если оба соединенных фрагментаимели одинаковый ранг L, то оба процесса p и q должны были отправить сообщение hconnect, Li по ребру e и должны были получить в ответ сообщениеhconnect, Li, и при этом ребро e должно иметь статус branch(см. действие (2)).Ребро pq становится стержнем нового фрагмента, и процессы p и q обмениваются сообщениями hinitiate, L + 1, N, Si, придавая вновь образованному фрагментуновый ранг и новое имя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
