Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 69
Текст из файла (страница 69)
Произвольные сети@ u @@@pHHGH@u AuAA259@@ u @ u @uu Ap1p2Au Au AA Auu@@@@HHHHHHG0 @ @G1G2Рис. 7.8. Вычисление, приводящее к двум лидерам7.3.1. Эффект угасания и быстрый алгоритмАлгоритм избрания лидера можно получить из произвольного волнового алгоритма при помощи конструкции, которая носит название угасание.
В полученномтаким образом алгоритме каждый инициатор запускает отдельную волну. Чтобыотличаться от сообщений других волн, сообщения, движущиеся по волне, запущенной процессом p, должны быть помечены отличительным признаком процесса p. Данный алгоритм гарантирует, что независимо от количества запущенныхволн только одна волна приведет к решению, а именно та волна, которую запустил инициатор с самым младшим отличительным признаком.
Все остальныеволны будут прерваны еще до того, как будет принято решение.Алгоритм избрания лидера Ex(A), соответствующий волновому алгоритму A,устроен так. Всякий процесс в каждый момент времени активен по отношению неболее чем к одной волне; эта волна называется его текущей активной волной,обозначается caw и имеет первоначальное значение udef.
Инициаторы выборов поступают так, как будто каждый из них запускает свою волну и придаетпеременной caw свой отличительный признак в качестве значения. Если сообщение некоторой волны, например волны, запущенной процессом q, достигаетпроцесса p, то p проводит следующий анализ этого сообщения. Если q > caw p ,то сообщение просто игнорируется, что немедленно приводит к тому, что волна, запущенная процессом q, угасает. Если q = caw p , то указанное сообщениеобрабатывается так, как это предписано волновым алгоритмом. Если q < caw pили cawp имеет значение udef, то p присоединяется к волне, запущенной процессом q, устанавливая в своих переменных первоначальные значения, а такжевыполняя присваивание cawp := q. Когда волна, запущенная процессом q, приводит к осуществлению события решения (в большинстве алгоритмов решениевсегда принимает сам процесс q), процесс q будет считаться избранным.
Еслиже волновой алгоритм устроен так, что процесс, принимающий решение, не обязан быть инициатором, то процесс, осуществивший решение, оповещает об этоминициатора, используя остовное дерево, определенное в лемме 6.3. Для этогопотребуется не более N − 1 обменов сообщениями; в последующих теоремах мыне уделяем этому внимания.Теорема 7.17. Если A является централизованным волновым алгоритмом, использующим M обменов сообщениями в каждой волне, то алгоритм260Гл. 7. Алгоритмы избрания лидераvar cawp:Pinit udef ; (* Текущая активная волна *)recp: integer init 0 ;(* Число полученных сообщений htok, cawp i *)fatherp:Pinit udef ; (* Родоначальник волны cawp *)lrecp: integer init 0 ;(* Число полученных сообщений hldri. *)winp:Pinit udef ; (* Отличительный признак лидера *)begin if p is initiator thenbegin cawp := p; forall q ∈ Neighp do send htok, pi to q end;while lrecp < #Neighp dobegin receive msg from q ;if msg = hldr, ri thenbegin if lrecp = 0 thenforall q ∈ Neighp do send hldr, ri to q ;lrecp := lrecp + 1 ; winp := rendelse (* сообщение htok, ri *)begin if r < cawp then (* Алгоритм повторной инициализации *)begin cawp := r ; recp := 0 ; fatherp := q ;forall s ∈ Neighp , s 6= q do send htok, ri to send;if r = cawp thenbegin recp := recp + 1 ;if recp = #Neighp thenif cawp = pthen forall s ∈ Neighp do send hldr, pi to selse send htok, cawp i to fatherpend (* Если r > cawp , то сообщение игнорируется *)endend; if winp = p then statep := leader else statep := lostend7.3.
Произвольные сети261лах этой волны) процессом p0 , или же само решение принималось бы процессомp0 (лемма 6.4). А так как p0 никогда не отправляет сообщений и не выполняетникаких внутренних действий в пределах волны, несущей отличительный признакпроцесса p, такое решение не может состояться, и процесс p не будет избран.Запускается не более N волн, и в каждой волне проводится не более M обменов сообщениями. Поэтому общая сложность будет составлять самое большее NM.Гораздо более тонкий вопрос — оценить сложность алгоритма Ex(A) по времени.
Во многих случаях эта сложность будет иметь такой же порядок, что и сложность по времени алгоритма A, но иногда при неудачном стечении обстоятельствможет случиться так, что инициатор с самым младшим отличительным признаком запускает свою волну слишком поздно. В общем случае можно показать, чтовременна́я сложность будет составлять O(Nt), где t — сложность по времени базового волнового алгоритма, потому что спустя t единиц времени, после того какинициатор p запустил свою волну, либо запущенная им волна должна привестик решению, либо будет запущена другая волна.Если принцип угасания применить к кольцевому алгоритму, то будет получен алгоритм Ченя—Робертса (см. упражнение 7.9).
Алгоритм 7.9 представляет собой алгоритм избрания лидера, полученный на основе алгоритма эха. Дляупрощения описания предполагается, что неравенство udef > q выполняется длявсех q ∈ P . Просматривая текст описания алгоритма, читатель должен обратитьвнимание на то, что после получения сообщения htok, ri, для которого выполняется неравенство r < cawp , оператор ветвления if с условием r = cawp такжевыполняется, ввиду более раннего присваивания значения переменной caw p . Когда процесс p будет избран (т. е. получит htok, pi от каждого своего соседа), онразошлет сообщение hldr, pi всем процессам, уведомляя их о том, что он сталлидером, и вынуждая их завершить выполнение алгоритма.Алгоритм 7.9.
Угасание в сочетании с алгоритмом эха7.3.2. Алгоритм Галладжера—Хамблета—СпирыEx(A) проводит выборы лидера с использованием не более NM обменов сообщениями.Д о к а з а т е л ь с т в о. Допустим, что p0 — инициатор, обладающий самыммладшим отличительным признаком. К волне, запущенной процессом p 0 , немедленно начнут присоединяться все процессы по мере получения сообщений этойволны, и каждый процесс продолжит эту волну, поскольку нет волны, несущейболее младший отличительный признак, ради которой этот процесс стал бы гаситьволну, запущенную p0 . Следовательно, волна, запущенная p0 , будет двигаться досамого конца, решение будет принято, и процесс p 0 станет лидером.Если процесс p не является инициатором, то и волна, несущая отличительный признак p, никогда не зародится, и, следовательно, процессу p не быватьлидером.
Если же процесс p, отличный от p0 , является инициатором, то волна,несущая отличительный признак p, будет запущена, но в этой волне принятиюрешения предшествовало бы событие отправления сообщения (все еще в преде-Как мы сейчас покажем, задача о выборах в произвольной сети тесно связанас задачей построения остовного дерева децентрализованным алгоритмом.
Будемиспользовать запись CE для обозначения сложности по числу обменов сообщениями задачи о выборах, а запись CT — для обозначения сложности построенияостовного дерева. Из теоремы 7.2 следует, что C E 6 CT + O(N), а если в нашемраспоряжении есть лидер, то остовное дерево можно построить с использованием 2|E| обменов сообщениями при помощи алгоритма эха; поэтому справедливонеравенство CT 6 CE + 2|E|. Нижняя оценка величины CE (см. теорему 7.15)свидетельствует о том, что обе задачи имеют сложность одного и того же порядка, а именно для решения обеих задач требуется использовать по меньшей мереΩ (N log N + E) обменов сообщениями.В этом параграфе представлен алгоритм Галладжера —Хамблета—Спиры (GHS),предназначенный для построения (минимального) остовного дерева с использованием 2|E| + 5N log N обменов сообщениями.
Отсюда видно, что порядок роста262Гл. 7. Алгоритмы избрания лидераобеих величин CE и CT составляет Θ (N log N + E). Указанный алгоритм былопубликован в [96] . Этот алгоритм можно легко модифицировать (о чем будетупомянуто в конце этого параграфа) и так настроить для проведения выборов лидера по ходу построения, чтобы отпала необходимость в проведении отдельныхвыборов согласно описанию, приведенному выше.Алгоритм GHS опирается на следующие допущения.1. Каждому ребру приписан уникальный вес (e). Здесь предполагается, чтовес (e) — это действительное число, но в качестве весов могут выступать и целыечисла.Если уникальные веса ребер не заданы a priori, то каждому ребру можноприписать вес, основываясь на отличительных признаках тех узлов, которые соединены этим ребром.
Таким образом, для вычисления весов ребер необходимо,чтобы узлы были осведомлены об отличительных признаках своих соседей; дляэтого потребуется 2|E| дополнительных сообщений на этапе инициализации алгоритма.2. Все узлы пребывают первоначально в состоянии оцепенения и пробуждаются перед началом выполнения алгоритма. Некоторые узлы пробуждаютсясамопроизвольно (если выполнение алгоритма запускается в силу особенностейустройства этих узлов), другие могут получить сообщение по ходу работы алгоритма, еще пребывая в оцепенении. В последнем случае узел, получивший сообщение, вначале выполняет процедуру локальной инициализации, а затем приступает к обработке этого сообщения.7.3. Произвольные сети263Утверждение 7.18 существенно облегчает распределенное построение минимального остовного дерева, так как не оставляет возможности (распределенного)выбора ответа из семейства правильных ответов.
Напротив, каждый узел, который совершает локальный выбор ребра, принадлежащего хоть какому-нибудьминимальному дереву, вносит тем самым вклад в построение единственного глобального MST.В основу всех алгоритмов построения минимального остовного дерева положено понятие фрагмента. Фрагментом может быть произвольное поддеревоMST. Ребро e называется исходящим ребром фрагмента F, если один из егоконцов принадлежит F, а другой нет. Алгоритмы начинают работу, располагаяфрагментами, состоящими из единственного узла, и последовательно наращивают фрагменты, до тех пор пока не будет завершено построение MST, основываясьпри этом на следующем утверждении.Предложение 7.19.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
