Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 72
Текст из файла (страница 72)
действие (2)).Сообщение htest, level1 , name1 i должно ожидать обработки, если level1 > level2(см. действие (5)). Во всех тех случаях, когда фрагмент F 1 ожидает фрагмент F2 ,выполняется одно из следующих условий:1) level1 > level2 ;2) level1 = level2 ∧ (eF1) > (eF2 );3) level1 = level2 ∧ (eF1 ) = (eF2 ) и F2 все еще пребывает в поиске исходящего из этого фрагмента ребра наименьшего веса. (Коль скоро e F1является ребром, исходящим из F2 , неравенство (eF2 ) > (eF1 ) выполняться не будет.)Таким образом, взаимная блокировка по замкнутому циклу невозможна.Каждое ребро может быть отвергнуто не более одного раза, и для этого требуется два сообщения; поэтому суммарное число отвергающих сообщений и тестовых сообщений, приводящих к отвержению, ограничено величиной 2|E|.
Каковбы ни был ранг фрагмента, узел получает не более одного инициирующего и одного допускающего сообщения и отправляет не более одной сводки (report), неболее одного сообщения о перемене корня или о соединении и не более одного тестового сообщения, не приводящего к отвержению ребра. Если ранг равеннулю, то не происходит отправлений допускающих сообщений и получения сводок или тестов. Каждый узел, обладающий самым высоким рангом, отправляеттолько сводку и получает только одно инициирующее сообщение.
Таким образом,общее число обменов сообщениями ограничено величиной 2|E| + 5N log N.7.3.5. Обсуждение GHS-алгоритма и его модификацийАлгоритм Галладжера—Хамблета—Спиры, использующий только локальныесведения и обладающий оптимальной сложностью по числу обменов сообщениями, является одним из самых изощренных волновых алгоритмов. Этот алгоритмможно без труда обобщить так, чтобы он проводил избрание лидера, используя всего лишь два дополнительных сообщения.
Данный алгоритм завершается в двух точках, каковыми являются стержневые точки последнего фрагмента(т. е. остовного дерева всей сети). Вместо выполнения команды останова алгоритма стержневые узлы сообщают друг другу свои отличительные признаки, и узелс наименьшим признаком становится лидером.272Гл. 7. Алгоритмы избрания лидераБыл опубликован целый ряд модификаций рассмотренного алгоритма. Алгоритму GHS требуется время Ω (N 2), если некоторые узлы запустили алгоритмслишком поздно.
Если использовать дополнительную процедуру побудки (длякоторой требуется не более 2|E| дополнительных сообщений) временн а́я сложность данного алгоритма станет равна 5N log N (см. упражнение 7.11). Авербахв работе [16] показал, что временна́я сложность алгоритма может быть понижена до O(N), и при этом сложность по числу обменов сообщениями остаетсяоптимальной, т. е.
равной O(|E| + N log N).Афек и др. в работе [1] приспособили данный алгоритм для вычисления остовного леса, обладающего тем свойством, что√ диаметр каждого дерева и общеечисло деревьев оцениваются величиной O( N). Их алгоритм разбивает сеть накластеры, как это описано в лемме 4.47, и вычисляет остовное дерево и центрдля каждого кластера.Можно задаться следующим вопросом: а не удастся ли построить произвольное остовное дерево более эффективно, чем это делается в случае минимальных остовных деревьев? Но из теоремы 7.15 следует, что нижняя оценкаΩ (N log N + |E|) сохраняется также и для произвольных деревьев. Йохансен и др.в работе [113] предложили алгоритм построения произвольного вычислительногодерева для разреженных сетей с использованием 3N log N + 2|E| + O(N) обменовсообщениями, уменьшив, таким образом, постоянный сомножитель в алгоритмеGHS.
Бар-Илан и Церник [22] разработали алгоритм построения случайногоостовного дерева, в котором всевозможные остовные деревья выбираются с равной вероятностью. Это рандомизованный алгоритм, для которого математическоеожидание числа используемых обменов сообщениями располагается в интервалеот O(N log N + |E|) до O(N3) в зависимости от топологии сети.Хотя для произвольных сетей сложность построения произвольного и минимального дерева одинакова, для клик это уже не так.
Корач, Моран и Закс [120]показали, что для построения минимального остовного дерева во взвешеннойклике требуется совершить Ω (N 2) обменов сообщениями. Этот результат свидетельствует о том, что учет топологии не позволяет уменьшить сложность поискаминимального остовного дерева ниже того уровня, который установлен в теореме 7.15. В следующем параграфе мы покажем, что произвольное остовное дерево в клике можно построить с использованием O(N log N) обменов сообщениями(см. также работу [119]).7.4. Алгоритм Корача—Каттена—МоранаБыло получено много результатов, касающихся задачи о выборах, и не толькодля случая кольцевых и произвольных сетей, но и для сетей других специальных топологий, таких как клики и т.
п. В отдельных случаях наилучшие известные алгоритмы достигают сложности O(N log N) по числу обменов сообщениями,а иногда их сложность соответствует нижней оценке Ω (N log N). Корач, Каттени Моран в работе [118] показали, что между задачей о выборах и задачей обходасети существует тесная взаимосвязь. Их основным результатом является общий7.4. Алгоритм Корача—Каттена—Морана273метод построения эффективного алгоритма избрания лидера для произвольногокласса сетей на основе всякого алгоритма обхода сетей из того же класса.Этот метод позволяет строить алгоритмы избрания лидера сложности O(N log N)для многих классов сетей. Поскольку наилучший возможный алгоритм обходаимеет сложность O(x) (линейную сложность), более эффективных алгоритмовизбрания при помощи этого метода построить нельзя.
Напротив, как мы увидимв гл. 11, для сетей с заданной ориентацией существуют и более качественныеалгоритмы избрания лидера. К тому же у алгоритма Корача —Каттена—Моранасложность по времени и сложность по числу обменов сообщениями одинаковы,тогда как известны примеры других алгоритмов избрания лидера, имеющих такуюже сложность по числу обменов сообщениями, но меньшую сложность по времени.
Интерес к данному методу обусловлен общностью этого метода и той взаимосвязью, благодаря которой алгоритм обхода используется в качестве отдельного«модуля» при решении задачи более высокого уровня — избрания лидера.7.4.1. Модульная конструкцияВ основу алгоритма Корача—Каттена—Морана положены идеи двух методов:метода угасания (см. § 7.3.1) и алгоритма Петерсона /Долева—Клейва—Роде(см. § 7.2.2).
Сходство с методом угасания проявляется в том, что инициаторывыборов приступают к обходу сети, используя маркеры, помеченные их отличительными признаками. Если обход завершится (будет принято решение), тоинициатор этого обхода будет считаться избранным; из самого описания алгоритма следует, что это случится в точности для одного обхода. В этом разделемы опишем данный алгоритм для случая, когда в каналах поддерживается очередность, но если добавить совсем немного информации, которая будет переноситься маркерами и обрабатываться процессами, то указанный алгоритм можнобудет использовать и в том случае, когда очередность сообщений в каналах негарантируется (см. [118]).Чтобы справиться с той ситуацией, когда есть несколько инициаторов, алгоритм оперирует на разных уровнях, подобно тому как алгоритм Петерсона/Долева—Клейва—Роде разбивает свое вычисление на туры.
Если запущеныпо крайней мере два обхода, то один из маркеров рано или поздно достигнеттого процесса, в котором уже успел побывать другой. Если сложится такая ситуация, то обход, который проводится при помощи вновь прибывшего маркера,будет прерван. Цель работы нашего алгоритма теперь состоит в том, чтобы привести две маркера вместе в один процесс, где они будут подавлены, и после этогоначнется новый обход. Этот прием напоминает аналогичный прием в алгоритмеПатерсона/Долева—Клейва—Роде, когда не более чем один из двух отличительных признаков имеет возможность уцелеть и перейти в другой тур. Вместо туровв алгоритме Корача–Каттена–Морана используются уровни; две маркера даютначало новому обходу только в том случае, если они находятся на одном и том жеуровне, и при этом уровень вновь запущенного обхода будет на единицу больше.Если какой-либо маркер встречается с другим маркером более высокого уровняили достигает узла, который уже посетил маркер более высокого уровня, то этот274Гл.
7. Алгоритмы избрания лидераприбывший маркер просто подавляется без всякого влияния на маркер болеевысокого уровня.var levp: integerinit −1 ;catp , waitp : Pinit udef ;lastp: Neighpinit udef ;begin if p is initiator thenbegin levp := levp + 1 ; lastp := trav(p, levp) ;catp := p ; send hannex, p, levp i to lastpend;while . .
. (* Условие завершения, см. описание *) dobegin receive token (q, l) ;if token is annexing then t := A else t := C ;if l > levp then (* Вариант I *)begin levp := l ; catp := q ; waitp := udef ; lastp := trav(q, l) ;send hannex, q, li to lastpendelse if l = levp and waitp 6= udef then (* Вариант II *)begin waitp := udef ; levp := levp + 1 ; lastp := trav(p, levp) ; catp := p ;send hannex, p, levp i to lastpendelse if l = levp and lastp = udef then (* Вариант III *)waitp := qelse if l = levp and t = A and q = catp then (* Вариант IV *)begin lastp := trav(q, l) ;if lastp = decidethen p объявляет себя лидером else send hannex, q, li to lastpendelse if l = levp and ((t = A and q > catp) or t = C) then (* Вариант V *)begin send hchase, q, li to lastp ; lastp := udef endelse if l = levp then waitp := q (* Вариант VI *)endendАлгоритм 7.13.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
