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

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

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

Эффект угасания и быстрый алгоритмАлгоритм избрания лидера можно получить из произвольного волнового алго­ритма при помощи конструкции, которая носит название угасание. В полученномтаким образом алгоритме каждый инициатор запускает отдельную волну. Чтобыотличаться от сообщений других волн, сообщения, движущиеся по волне, запу­щенной процессом р, должны быть помечены отличительным признаком процес­са р. Данный алгоритм гарантирует, что независимо от количества запущенныхволн только одна волна приведет к решению, а именно та волна, которую за­пустил инициатор с самым младшим отличительным признаком.

Все остальныеволны будут прерваны еще до того, как будет принято решение.Алгоритм избрания лидера Ех(А), соответствующий волновому алгоритму А,устроен так. Всякий процесс в каждый момент времени активен по отношению неболее чем к одной волне; эта волна называется его текущей активной волной,обозначается caw и имеет первоначальное значение udef. Инициаторы выбо­ров поступают так, как будто каждый из них запускает свою волну и придаетпеременной caw свой отличительный признак в качестве значения. Если сооб­щение некоторой волны, например волны, запущенной процессом q, достигаетпроцесса р, то р проводит следующий анализ этого сообщения.

Если q > cawp,то сообщение просто игнорируется, что немедленно приводит к тому, что вол­на, запущенная процессом q, угасает. Если q = cawp, то указанное сообщениеобрабатывается так, как это предписано волновым алгоритмом. Если q < cawpили cawp имеет значение udef, то р присоединяется к волне, запущенной про­цессом q, устанавливая в своих переменных первоначальные значения, а такжевыполняя присваивание cawp := q. Когда волна, запущенная процессом q, при­водит к осуществлению события решения (в большинстве алгоритмов решениевсегда принимает сам процесс q), процесс q будет считаться избранным. Еслиже волновой алгоритм устроен так, что процесс, принимающий решение, не обя­зан быть инициатором, то процесс, осуществивший решение, оповещает об этоминициатора, используя остовное дерево, определенное в лемме 6.3.

Для этогопотребуется не более N — 1 обменов сообщениями; в последующих теоремах мыне уделяем этому внимания.Теорема 7.17. Если А является централизованным волновым алгорит­мом, использующим М обменов сообщениями в каждой волне, то алгоритм260Гл. 7. Алгоритмы избрания лидераТекущая активная волна *)init udef ;VЧислополученных сообщений (tok, cawp) *)init0 ;integerrecpРодоначальник волны cawp *)init udefVfatherpЧисло полученных сообщений (ldr).

*)integer init 0 ;IrecpОтличительный признак лидера *)initudefVwiripbegin if p is initiator thenbegin cawp := p; forall q € Neighp do send (tok, p) to q end;while lrecP Ч ff Neighp dobegin receive rnsg from q ;if msg = (ldr, r) thenbegin if lrecp = 0 thenforall q € Neighp do send (ldr, r) to q ;lrecp := lrecp + 1 ; winp := rendelse (* сообщение (tok, r) *)begin if r < cawp then (* Алгоритм повторной инициализацииbegin cawp := r ; recp := 0 ; fatherp := q ;forall s € Neighp, s Ф q do send (tok, r) to send;if r = cawp thenbegin recp := recP+ 1 ;if recp = jfNeighp thenif cawp = pthen forall s € Neighp do send (ldr, p) to selse send (tok, cawp) to fatherpend (* Если r > cawp, то сообщение игнорируется *)endend; if winp = p then statep := leader else statep := lostendvar cawpАлгоритм 7.9.

Угасание в сочетании с алгоритмом эхаЕх{А) проводит выборы лидера с использованием не более NM обменов со­общениями.Д о к а з а т е л ь с т в о . Допустим, что ро — инициатор, обладающий самыммладшим отличительным признаком. К волне, запущенной процессом р о, немед­ленно начнут присоединяться все процессы по мере получения сообщений этойволны, и каждый процесс продолжит эту волну, поскольку нет волны, несущейболее младший отличительный признак, ради которой этот процесс стал бы гаситьволну, запущенную ро.

Следовательно, волна, запущенная ро, будет двигаться досамого конца, решение будет принято, и процесс р о станет лидером.Если процесс р не является инициатором, то и волна, несущая отличитель­ный признак р, никогда не зародится, и, следовательно, процессу р не быватьлидером. Если же процесс р, отличный от ро, является инициатором, то волна,несущая отличительный признак р, будет запущена, но в этой волне принятиюрешения предшествовало бы событие отправления сообщения (все еще в преде-7.3. Произвольные сети261лах этой волны) процессом ро, или же само решение принималось бы процессомро (лемма 6.4). А так как ро никогда не отправляет сообщений и не выполняетникаких внутренних действий в пределах волны, несущей отличительный признакпроцесса р, такое решение не может состояться, и процесс р не будет избран.Запускается не более N волн, и в каждой волне проводится не более М об­менов сообщениями.

Поэтому общая сложность будет составлять самое боль­шее NM.□Гораздо более тонкий вопрос — оценить сложность алгоритма Ех(А) по време­ни. Во многих случаях эта сложность будет иметь такой же порядок, что и слож­ность по времени алгоритма А, но иногда при неудачном стечении обстоятельствможет случиться так, что инициатор с самым младшим отличительным призна­ком запускает свою волну слишком поздно. В общем случае можно показать, чтовременная сложность будет составлять O(Nt), где t — сложность по времени ба­зового волнового алгоритма, потому что спустя t единиц времени, после того какинициатор р запустил свою волну, либо запущенная им волна должна привестик решению, либо будет запущена другая волна.Если принцип угасания применить к кольцевому алгоритму, то будет полу­чен алгоритм Ченя—Робертса (см. упражнение 7.9).

Алгоритм 7.9 представля­ет собой алгоритм избрания лидера, полученный на основе алгоритма эха. Дляупрощения описания предполагается, что неравенство udef > q выполняется длявсех q <ЕV. Просматривая текст описания алгоритма, читатель должен обратитьвнимание на то, что после получения сообщения (tok, г), для которого выпол­няется неравенство г < cawp, оператор ветвления if с условием г = cawp такжевыполняется, ввиду более раннего присваивания значения переменной cawp. Ко­гда процесс р будет избран (т. е. получит (tok, р) от каждого своего соседа), онразошлет сообщение (ldr, р) всем процессам, уведомляя их о том, что он сталлидером, и вынуждая их завершить выполнение алгоритма.7.3.2.

Алгоритм Галладжера—Хамблета—СпирыКак мы сейчас покажем, задача о выборах в произвольной сети тесно связанас задачей построения остовного дерева децентрализованным алгоритмом. Будемиспользовать запись Се для обозначения сложности по числу обменов сообще­ниями задачи о выборах, а запись Ст — для обозначения сложности построенияостовного дерева. Из теоремы 7.2 следует, что Cg ^ Cj + 0(N), а если в нашемраспоряжении есть лидер, то остовное дерево можно построить с использовани­ем 2 |£| обменов сообщениями при помощи алгоритма эха; поэтому справедливонеравенство Ст ^ Се + 2|£|.

Нижняя оценка величины Се ( с м . теорему 7.15)свидетельствует о том, что обе задачи имеют сложность одного и того же поряд­ка, а именно для решения обеих задач требуется использовать по меньшей мереCl(N log N + Е) обменов сообщениями.В этом параграфе представлен алгоритм Галладжера—Хамблета—Спиры (GHS),предназначенный для построения (минимального) остовного дерева с использо­ванием 2\Е\ 4 - 5A4ogjV обменов сообщениями. Отсюда видно, что порядок ростаГл. 7.

Алгоритмы избрания лидера262обеих величин C g и Ср составляет 0(yVlog/V + Е). Указанный алгоритм былопубликован в [96]. Этот алгоритм можно легко модифицировать (о чем будетупомянуто в конце этого параграфа) и так настроить для проведения выборов ли­дера по ходу построения, чтобы отпала необходимость в проведении отдельныхвыборов согласно описанию, приведенному выше.Алгоритм GHS опирается на следующие допущения.1. Каждому ребру приписан уникальный вес со(е). Здесь предполагается, чтовес со(е) — это действительное число, но в качестве весов могут выступать и целыечисла.Если уникальные веса ребер не заданы a priori, то каждому ребру можноприписать вес, основываясь на отличительных признаках тех узлов, которые со­единены этим ребром. Таким образом, для вычисления весов ребер необходимо,чтобы узлы были осведомлены об отличительных признаках своих соседей; дляэтого потребуется 2\Е\ дополнительных сообщений на этапе инициализации ал­горитма.2.

Все узлы пребывают первоначально в состоянии оцепенения и пробуж­даются перед началом выполнения алгоритма. Некоторые узлы пробуждаютсясамопроизвольно (если выполнение алгоритма запускается в силу особенностейустройства этих узлов), другие могут получить сообщение по ходу работы алго­ритма, еще пребывая в оцепенении.

В последнем случае узел, получивший сооб­щение, вначале выполняет процедуру локальной инициализации, а затем присту­пает к обработке этого сообщения.Минимальное остовное дерево. Рассмотрим взвешенный граф G = ( V , Е )и для обозначения веса ребра е будем использовать запись со(е). Вес остовногодерева Т в графе G полагается равным сумме весов всех N — 1 ребер, входя­щих в состав Т, и при этом Т называется м и н и м а л ь н ы м о с т о в н ы м д е р е в о мили сокращенно MST (иногда его называют также остовным деревом минималь­ного веса), если ни одно остовное дерево не имеет вес, меньший чем Т.

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

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