Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 69

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 69)

В этомпараграфе мы будем полагать, что каждое ребро имеет уникальный вес, т. е. раз­личные ребра имеют различные веса; хорошо известно, что в таком случае в графесуществует единственное минимальное остовное дерево.Предложение 7.18.ст вует т олько одноЕ сли все веса р еб ер п о п а р н о р а зл и ч н ы , т о сущ е­MST.Д о к а з а т е л ь с т в о . Допустим противное и рассмотрим случай, когдаоба дерева 7) и Т2 (причем 7) ф Т2 ) являются минимальными остовными де­ревьями.

Рассмотрим ребро е наименьшего веса, которое содержится в одном изэтих деревьев, но не содержится в другом; такое ребро существует, ибо Т\ ф Т2 .Допустим, не умаляя общности, что е принадлежит Т\, но не входит в состав 7г.Тогда граф Т2 U {е} содержит цикл, и, поскольку в дереве 7) нет циклов, хотя быодно ребро этого цикла, скажем ребро е', не содержится в 7). Согласно выборуребра е, справедливо неравенство Ые) < со(<?'). Но тогда дерево Т2 U {е} \ \е'}имеет вес, меньший чем Т2 , вопреки тому, что Т2 является MST.□7.3. Произвольные сети263Утверждение 7.18 существенно облегчает распределенное построение мини­мального остовного дерева, так как не оставляет возможности (распределенного)выбора ответа из семейства правильных ответов.

Напротив, каждый узел, кото­рый совершает локальный выбор ребра, принадлежащего хоть какому-нибудьминимальному дереву, вносит тем самым вклад в построение единственного гло­бального MST.В основу всех алгоритмов построения минимального остовного дерева по­ложено понятие фрагмента.

Фрагментом может быть произвольное поддеревоMST. Ребро е называется исходящим ребром фрагмента F, если один из егоконцов принадлежит F, а другой нет. Алгоритмы начинают работу, располагаяфрагментами, состоящими из единственного узла, и последовательно наращива­ют фрагменты, до тех пор пока не будет завершено построение MST, основываясьпри этом на следующем утверждении.Предложение 7.19. Если F является фрагментом и е — ребро наимень­шего веса, исходящее из F, то FU {е} также является фрагментом.Д о к а з а т е л ь с т в о .

Допустим, что AU{e} не является фрагментом MST.Тогда е наряду с некоторыми ребрами MST образует цикл и при этом одно из ре­бер этого цикла, принадлежащее MST (например /), является ребром, исходящимиз фрагмента F. Согласно выбору ребра е справедливо неравенство ы(е) < ы(/);но в таком случае после изъятия ребра / из MST и добавления вместо него ребрае, мы получили бы дерево, вес которого был бы меньше веса MST, т. е. пришлибы к противоречию.□Хорошо известны последовательные алгоритмы построения MST, среди ко­торых можно отметить алгоритмы Прима и Краскала. Алгоритм Прима (см. [55,раздел 24.2]) начинает работу с простейшего фрагмента и на каждом шаге рас­ширяет его, добавляя ребро наименьшего веса, исходящее из построенного к томувремени фрагмента.

Алгоритм Краскала (см. [55, раздел 24.2]) начинает рабо­ту, располагая семейством фрагментов, состоящих из одного узла, и проводитих соединение, добавляя ребра наименьшего веса, исходящие из того или иногофрагмента. Поскольку в алгоритме Краскала разрешается работать независи­мо с несколькими фрагментами, он более подходит для реализации в качествераспределенного алгоритма.7.3.3. Глобальное описание алгоритма GHS.Вначале мы расскажем о глобальной работе алгоритма, т. е. опишем, как алго­ритм обращается с фрагментами. Затем мы приведем локальный алгоритм, опи­сывающий действия, которые должны выполняться в каждом узле сети, чтобыосуществить эти глобальные операции над фрагментами.Всякое вычисление алгоритма GHS складывается из следующих шагов.1. Формируется такое семейство фрагментов, что объединение их содержитвсе узлы сети.2.

Первоначально это семейство состоит из всех узлов сети, каждый из ко­торых рассматривается как граф с одним узлом.264Гл. 7. Алгоритмы избрания лидера3. Узлы всякого фрагмента вступают во взаимодействие с целью выявленияисходящего из фрагмента ребра с наименьшим весом.4. Как только будет определено исходящее из фрагмента ребро с наимень­шим весом, данный фрагмент соединяется с другим фрагментом путем добавленияэтого исходящего ребра, которое строится в результате взаимодействия этих двухфрагментов.5. Алгоритм завершает работу, как только останется только один фрагмент.Для эффективной реализации этих шагов потребуется ввести некоторые обо­значения и операции.1. Имя фрагмента.

Чтобы определить исходящее ребро наименьшего веса,необходимо суметь проверить, выводит ли некоторое ребро за пределы фрагмен­та или оно ведет в узел того же самого фрагмента. Для этого каждый фрагментбудет наделен именем, которое будет известно всем процессам, входящим в этотфрагмент. Процессы будут проверять, является ли ребро внутренним или внеш­ним ребром, сравнивая имена фрагментов, к которым они относятся.2. Соединение старшего и младшего фрагментов. Когда два фрагментасоединяются, в процессах хотя бы одного из этих фрагментов происходит пере­мена имени фрагмента; для этого требуется, чтобы изменение имени произошлов каждой точке по крайней мере одного из указанных фрагментов.

Чтобы осу­ществить это изменение эффективно, в основу стратегии соединения фрагментовположен следующий принцип: младший из двух фрагментов присоединяетсяк старшему из них и принимает имя старшего фрагмента.3. Ранги фрагментов. После небольшого размышления становится ясно,что решение о том, какой из фрагментов старше, нельзя основывать на коли­честве узлов в этих фрагментах. В таком случае размер фрагмента пришлосьбы уточнять в каждом процессе обоих фрагментов-компонент и, таким обра­зом, нарушать взятое обязательство проводить уточнения только в младшем издвух фрагментов. Вместо этого каждому фрагменту сопоставляется ранг , кото­рый первоначально полагается равным 0 для любого фрагмента, состоящего изодного узла. Некоторый фрагмент F\ может соединиться с фрагментом F2 бо­лее высокого ранга, после чего новый фрагмент F\ U F2 будет иметь такой жеранг, как и фрагмент F2 .

Этот новый фрагмент унаследует имя фрагмента F2 ,и поэтому в узлах фрагментане потребуется проводить никаких уточнений.Неизбежно также и соединение двух фрагментов одного и того же ранга; в этомслучае новый фрагмент будет носить новое имя и его ранг будет на единицупревосходить ранг соединенных фрагментов. Именем образовавшегося фрагмен­та будет вес того ребра, которое соединило два исходных фрагмента; указанноеребро назовем стержнем нового фрагмента.

Те два узла, которые соединеныребром-стержнем, будут называться стержневыми узлами.Лемма 7.20. Если соблюдать указанные выше правила соединения фраг­ментов, то суммарно во всех процессах перемена имени или ранга случит­ся не более A log Л/ раз.Д о к а з а т е л ь с т в о . Ранг всякого процесса не понижается, и лишь в томслучае, когда он повышается, процесс вынужден переменить имя своего фрагмен-7.3. Произвольные сети265та. Фрагмент ранга L содержит не менее 2L процессов, и поэтому максимальновозможный ранг равен log N .

Отсюда следует, что в каждом отдельном процессеранг содержащего его фрагмента повышается не более log N раз. Значит, общеечисло перемен имени и ранга фрагмента ограничено величиной N log N .□Краткое изложение стратегии соединения. Для обозначения фрагмента Fс именем F N и рангом L будем использовать запись F = (F N , L). Обозначимсимволом ер исходящее из фрагмента F ребро наименьшего веса.Правило А. Если ер ведет в такой фрагмент F' = (FN', L'), для которогоL < L', то фрагмент F присоединяется к А' и образовавшийся при этом новыйфрагмент сохраняет имя FN' и ранг L '.

Эти новые значения отправляются всемпроцессам, входящим в состав F.Правило В. Если ер ведет в такой фрагмент F' = (FN', L'), для которогоL = L' и ер> = ер, то эти два фрагмента соединяются и образуют один новыйфрагмент, который будет носить имя со(е^) и иметь ранг L + 1. Эти новые значенияотправляются всем процессам, входящим в состав F и F'.Правило С. Во всех остальных случаях (т. е. когда либо L > V , либо L == L' и ер/ ^ ер) фрагмент F должен ожидать, когда откроется возможностьприменения правила А или В.7.3.4. Подробное описание алгоритма GHSСтатус узлов и связей.

Как отмечено в описании алгоритма 7.10, в узле рзадействовано несколько локальных переменных, среди которых есть перемен­ные статуса каналов stachp[q] для каждого канала связи pq. Канал может иметьодин из следующих трех статусов: branch, если известно, что соответствующееребро входит в MST, reject, если известно, что это ребро не входит в MST,и basic, если данное ребро еще не было использовано. Обмен сообщениями вофрагменте с целью выявления исходящего ребра наименьшего веса проводитсяпо ребрам типа branch. Для всякого процесса р рассматриваемого фрагмен­та запись fatherр будет обозначать то ребро, которое ведет к стержню данногофрагмента. Состоянием statep узла р может быть либо find, если процесс р при­влечен к проводимому во фрагменте поиску исходящего ребра наименьшего веса,либо found в противном случае.

Описание алгоритма GHS состоит из трех ча­стей 7.10/7.11/7.12. Иногда обработка сообщений может быть отложена, до техпор пока не будет выполнено некоторое локальное условие. В таком случае мыбудем подразумевать, что анализируемое сообщение сохраняется в памяти. Впо­следствии оно извлекается из памяти и обрабатывается так, как будто оно былотолько что получено. Если процесс получает сообщение, пребывая все еще в со­стоянии sleep, то перед тем как приступить к обработке этого сообщения, нашалгоритм проходит в этой точке этап инициализации (выполняя действие ( 1 )).Поиск исходящего ребра наименьшего веса.

Характеристики

Список файлов книги