Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 71
Текст из файла (страница 71)
(6 )).Обработка сообщения (test, L, F) процессом р откладывается, если L >> levelp. Причина этого заключается в том, что узлы р и q могут на самом делепринадлежать одному и тому же фрагменту, но сообщение (initiate, L + 1, N, S)еще не достигло узла р. Тогда узел р мог бы ошибочно отправить узлу q сообщение (accept).Гл. 7.
Алгоритмы избрания лидера270Соединение фрагментов. Как только будет определено исходящее из фрагмента F = ( n a m e , l e v e l ) ребро наименьшего веса, по нему отправляется сообщение (connect, l e v e l ) , которое будет получено узлом, принадлежащим фрагменту F' = ( п а т е ' , l e v e l ' ) . Обозначим символом р процесс, отправивший указанное сообщение, а символом q процесс, который принял это сообщение. Узелq ранее уже отправлял сообщение (accept) процессу р в ответ на сообщение(test, l e v e l , п а т е ) , поскольку поиск наилучшего исходящего ребра во фрагменте, к которому относится узел р , был завершен.
Ожидание, проходящее передответом на тестовое сообщение (см. действие (5)), позволяет заключить, чтоle v e l'>level.Согласно правилам соединения, которые обсуждались ранее, на запрос (connect,будет отправлено ответное сообщение (initiate, L + 1, N , S ) в двух случаях.Вариант А. Если l e v e l ' > l e v e l , то фрагмент, содержащий узел р , поглощается; все узлы этого фрагмента оповещаются о новом имени и новом рангефрагмента посредством сообщения (initiate, l e v e l ' , n a m e ' , S ) , которое распространяется по всем узлам фрагмента F . Весь поглощаемый фрагмент F становится поддеревом, присоединенным к узлу q, в остовном дереве фрагмента F ' , иесли узел q привлечен к поиску наилучшего ребра, исходящего из фрагмента F ' ,то все процессы, относящиеся к фрагменту F , должны принять участие в этомпоиске.
Поэтому процесс q включает свое состояние ( f i n d v u m f o u n d ) в сообщение(initiate, l e v e l ' , n a m e ' , S ) .Вариант В. Если два фрагмента имеют одинаковый ранг и наилучшим ребром, исходящим из фрагмента F', также является pq, то образуется новый фрагмент, ранг которого повышается на единицу, а его именем становится вес ребраp q (см. действие (2)). Такой случай возможен, если два ранга равны и сообщение о соединении получено по ребру, имеющему статус b r a n c h . Следует обратитьвнимание на то, что ребро приобретает статус b r a n c h , если по нему отправляетсясообщение о соединении.Во всех остальных случаях фрагмент F должен пребывать в ожидании того,что либо q отправит сообщение (connect, L ) , либо ранг фрагмента, содержащего q, повысится настолько, чтобы стал осуществим вариант А.Корректность и сложность.
Из подробного описания алгоритма должнобыть ясно, что ребро, по которому из фрагмента отправляется сообщение (connect,действительно является исходящим из фрагмента ребром наименьшего веса. Отсюда, а также из утверждения 7.19 следует, что MST будет построено правильно,если каждый фрагмент действительно отправляет такое сообщение и соединяетсяс другим фрагментом, несмотря на ожидание, предусмотренное данным алгоритмом. Наиболее сложное сообщение включает в себя информацию о весе одногоребра, информацию о значении одного ранга (не более logIV битов) и некотороефиксированное число битов для оповещения о типе сообщения и состоянии узла.le ve l)L ),Теорема 7.21.
А л г о р и т м Г а л л а д ж е р а — Х а м б л е т а — С п и р ы ( а л г о р и т м 7.10/7.11/7.12) в ы ч и с л я е т м и н и м а л ь н о е о с т о в н о е д е р е в о , и с п о л ь з у я п р и э т о м н еб о л е е b N \ o g N + 2|£| о б м е н о в с о о б щ е н и я м и .7.3. Произвольные сети271Д о к а з а т е л ь с т в о . Потенциальная возможность для взаимной блокировки возникает в тех ситуациях, когда узлы или фрагменты должны пребыватьв ожидании того, что определенные условия будут выполнены в другом узле илив другом фрагменте.
Ожидание в стержневых узлах, связанное с сообщениями(report, со), не приводит к блокировке, потому что каждый стержневой узел раноили поздно получит сводки от всех своих преемников (если только весь фрагмент целиком не пребывает в ожидании другого фрагмента), после чего указанноесообщение будет обработано.Рассмотрим случай, когда сообщение, отправленное из фрагмента F\ = (leveli, name\достигает какого-то узла фрагмента= (level2 , патв 2 )• Сообщение (connect, level\)должно ожидать обработки, если level\ > leveh и никакое сообщение (connect, /ете/2 )не было отправлено по тому же самому ребру из фрагмента F2 (см.
действие (2 )).Сообщение (test, level\, name 1 ) должно ожидать обработки, если level\ > level2(см. действие (5)). Во всех тех случаях, когда фрагмент F \ ожидает фрагмент F 2 ,выполняется одно из следующих условий:1)le v e l\>level? ,A Ц е/Д > to(e/?2);= l e v e l 2 A сДе/Д = to(e/?2) и /д все еще пребывает в поиске исходящего из этого фрагмента ребра наименьшего веса. (Коль скороявляется ребром, исходящим из F2 , неравенство ы(ер2) > со(в/Д выполняться не будет.)Таким образом, взаимная блокировка по замкнутому циклу невозможна.Каждое ребро может быть отвергнуто не более одного раза, и для этого требуется два сообщения; поэтому суммарное число отвергающих сообщений и тестовых сообщений, приводящих к отвержению, ограничено величиной 2\Е\. Каковбы ни был ранг фрагмента, узел получает не более одного инициирующего и одного допускающего сообщения и отправляет не более одной сводки (report), неболее одного сообщения о перемене корня или о соединении и не более одного тестового сообщения, не приводящего к отвержению ребра.
Если ранг равеннулю, то не происходит отправлений допускающих сообщений и получения сводок или тестов. Каждый узел, обладающий самым высоким рангом, отправляеттолько сводку и получает только одно инициирующее сообщение. Таким образом,общее число обменов сообщениями ограничено величиной 2|£| + 5AMogA.□2)3)le v e l\ = le v e l2le v e l\7.3.5. Обсуждение GHS-алгоритма и его модификацийАлгоритм Галладжера—Хамблета—Спиры, использующий только локальныесведения и обладающий оптимальной сложностью по числу обменов сообщениями, является одним из самых изощренных волновых алгоритмов. Этот алгоритмможно без труда обобщить так, чтобы он проводил избрание лидера, используя всего лишь два дополнительных сообщения. Данный алгоритм завершается в двух точках, каковыми являются стержневые точки последнего фрагмента(т.
е. остовного дерева всей сети). Вместо выполнения команды останова алгоритма стержневые узлы сообщают друг другу свои отличительные признаки, и узелс наименьшим признаком становится лидером.272Гл. 7. Алгоритмы избрания лидераБыл опубликован целый ряд модификаций рассмотренного алгоритма. Алгоритму GHS требуется время Q(A2), если некоторые узлы запустили алгоритмслишком поздно. Если использовать дополнительную процедуру побудки (длякоторой требуется не более 2\Е\ дополнительных сообщений) временная сложность данного алгоритма станет равна 5/V log А (см.
упражнение 7.11). Авербахв работе [16] показал, что временная сложность алгоритма может быть понижена до 0(N), и при этом сложность по числу обменов сообщениями остаетсяоптимальной, т. е. равной 0(\Е\ + AlogA).Афек и др. в работе [ 1] приспособили данный алгоритм для вычисления остовного леса, обладающего тем свойством, что диаметр каждого дерева и общеечисло деревьев оцениваются величиной 0{\/М).
Их алгоритм разбивает сеть накластеры, как это описано в лемме 4.47, и вычисляет остовное дерево и центрдля каждого кластера.Можно задаться следующим вопросом: а не удастся ли построить произвольное остовное дерево более эффективно, чем это делается в случае минимальных остовных деревьев? Но из теоремы 7.15 следует, что нижняя оценкаf2(AlogА+1£|) сохраняется также и для произвольных деревьев.
Йохансен и др.в работе [ИЗ] предложили алгоритм построения произвольного вычислительногодерева для разреженных сетей с использованием 3AlogA + 2|£] + О(А) обменовсообщениями, уменьшив, таким образом, постоянный сомножитель в алгоритмеGHS. Бар-Илан и Церник [22] разработали алгоритм построения случайногоостовного дерева, в котором всевозможные остовные деревья выбираются с равной вероятностью. Это рандомизованный алгоритм, для которого математическоеожидание числа используемых обменов сообщениями располагается в интервалеот 0(A logA + |£|) до 0(А 3) в зависимости от топологии сети.Хотя для произвольных сетей сложность построения произвольного и минимального дерева одинакова, для клик это уже не так. Корач, Моран и Закс [120]показали, что для построения минимального остовного дерева во взвешеннойклике требуется совершить fi(A2) обменов сообщениями.
Этот результат свидетельствует о том, что учет топологии не позволяет уменьшить сложность поискаминимального остовного дерева ниже того уровня, который установлен в теореме 7.15. В следующем параграфе мы покажем, что произвольное остовное дерево в клике можно построить с использованием O(AlogA) обменов сообщениями(см.
также работу [119]).7.4. Алгоритм Корача—Каттена—МоранаБыло получено много результатов, касающихся задачи о выборах, и не толькодля случая кольцевых и произвольных сетей, но и для сетей других специальных топологий, таких как клики и т. п. В отдельных случаях наилучшие известные алгоритмы достигают сложности О (A log А) по числу обменов сообщениями,а иногда их сложность соответствует нижней оценке G(AlogA).
Корач, Каттени Моран в работе [118] показали, что между задачей о выборах и задачей обходасети существует тесная взаимосвязь. Их основным результатом является общий7.4. Алгоритм. Корача—Каттена—Морана273метод построения эффективного алгоритма избрания лидера для произвольногокласса сетей на основе всякого алгоритма обхода сетей из того же класса.Этот метод позволяет строить алгоритмы избрания лидера сложности 0(N log N)для многих классов сетей. Поскольку наилучший возможный алгоритм обходаимеет сложность 0(х) (линейную сложность), более эффективных алгоритмовизбрания при помощи этого метода построить нельзя. Напротив, как мы увидимв гл. 1 1 , для сетей с заданной ориентацией существуют и более качественныеалгоритмы избрания лидера. К тому же у алгоритма Корача—Каттена—Моранасложность по времени и сложность по числу обменов сообщениями одинаковы,тогда как известны примеры других алгоритмов избрания лидера, имеющих такуюже сложность по числу обменов сообщениями, но меньшую сложность по времени.
Интерес к данному методу обусловлен общностью этого метода и той взаимосвязью, благодаря которой алгоритм обхода используется в качестве отдельного«модуля» при решении задачи более высокого уровня — избрания лидера.7.4.1. Модульная конструкцияВ основу алгоритма Корача—Каттена—Морана положены идеи двух методов:метода угасания (см. § 7.3.1) и алгоритма Петерсона/Долева—Клейва—Роде(см. §7.2.2). Сходство с методом угасания проявляется в том, что инициаторывыборов приступают к обходу сети, используя маркеры, помеченные их отличительными признаками.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
