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

Теперь мы дадим общее описание этого алгоритма, полагая,что в основу сети положена произвольная группа. Расположим пометки начиная с g1 и оканчивая gk (опуская обратные элементы) в произвольном порядкеи определим величины n1 , . . . , nk следующим образом. Прежде всего, величинуn1 положим равной порядку элемента g1 . Далее положим n2 равной порядку g2в группе G/hg1 i; эта величина будет равна наименьшему натуральному числу, длякоторого g1 является делителем n2 · g2 . И для каждого i в качестве ni выбираетсяпорядок элемента gi в группе G/hg1 , . .

. , gi−1 i; это наименьшее число, для которого элемент ni · gi можно представить в виде суммы элементов {g1 , . . . , gi−1 }.Числа ni обладают следующим свойством: произведение всех этих чисел равноN, и каждый элемент g из группы G можно представить единственным образомв виде суммыg=kXi=1s i · gi ,где 0 6 si < ni .Для инициатора:for i = 1 to kdo if ni > 1 then send hinfo, ni − 1i via link giПосле получения сообщения hinfo, si по каналу −gj :if s > 1 then send hinfo, s − 1i via link gj ;for i = j + 1 to kdo if si > 1 then hinfo, si − 1i via link giАлгоритм 11.2. Широковещательная рассылка с униформным восприятиемнаправленияВ алгоритме 11.2 информация отправляется на n 1 − 1 переходов в направлении g1 и достигает всех процессов, отличие которых от инициатора описываетсяэлементом группы, кратным g1 .

Инициатор и все процессы, получающие сообщение по направлению −g1 , отправляют его по направлению g2 на n2 − 1 переходов;таким образом, сообщение достигает всех процессов, отличие которых от инициатора выражается элементом группы, представляющим собой сумму элемента,кратного g1 , и элемента, кратного g2 . В общем случае инициатор и все процессы,получившие сообщение по направлениям начиная с −g 1 и оканчивая −gi−1 , отправляют это сообщение далее по направлению g i на ni − 1 переходов.

Посколькукаждый процесс, отличный от инициатора, получает сообщение в точности одинраз, в алгоритме 11.2 происходит в точности N − 1 обменов сообщениями.11.2. Выборы на кольцах и хордовых кольцах383В случае необходимости можно добавить N − 1 обратных сообщений и превратить этот алгоритм в PIF-алгоритм.В случае необходимости неинициаторы могут запоминать те каналы, по которым к ним было доставлено сообщение; в результате будет образовано остовное дерево сети, корнем которого будет инициатор. Это дерево можно использовать для отправления инициатору уведомляющих сообщений (см.

§ 11.3.2). Глубина остовного дерева, которое строится рассматриваемым алгоритмом, равнаPki=1 (ni − 1); в случае необходимости глубину можно изменить, избрав другойпорядок расположения элементов g1 , . . . , gk в списке пометок L. Мы не будем здесь заниматься исследованием этого вопроса, который связан с временнойсложностью широковещательного распространения информации.11.2. Выборы на кольцах и хордовых кольцахЗадача избрания лидера на кольцах и хордовых кольцах имеет долгую историю (см. § 7.5.2). В § 11.2.1 мы опишем решение, Франклином в работе [90] ,которое было улучшено Аттьей и др. в работе [10] за счет использования хорд,добавленных (униформно) к кольцу.

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

В § 11.2.4 мы продемонстрируем, что дляполучения линейного алгоритма понадобится еще меньше хорд, если структурасети также будет принята в расчет.11.2.1. Алгоритм ФранклинаВ алгоритме Франклина проводится разделение процессов на активные и релейные, а между турами устанавливается преемственность. Перед началом первого тура все процессы считаются активными.

Если в начале тура имеется болееодного активного процесса, то в этом туре в худшем случае половина из них, а влучшем случае все кроме одного станут релейными процессами, и затем начнетсяследующий тур. Тот тур, в котором есть только один активный процесс, является завершающим; этот оставшийся процесс избирается лидером. Таким образом,число туров не превышает величины blog Nc + 1, и, поскольку в каждом туре используется в точности 2N сообщений, сложность алгоритма по числу сообщенийв худшем случае приближенно равна 2N log N.В каждом туре активные процессы обмениваются своими именами с ближайшими активными соседями справа и слева. Если «ближайшим активным соседом» к какому-либо процессу является он сам, то это означает, что этот процесси есть единственный активный процесс; тогда он становится лидером. В противном случае он переходит в следующий тур только в том случае, если его имяпревосходит имена обоих его «активных соседей» справа и слева.

Это условиесоблюдается по меньшей мере для одного процесса (процесса с самым старшимименем), но не более, чем для половины из них (поскольку оно нарушается для384Гл. 11. Восприятие направления и ориентацияstatep := active ;while statep = active dobegin send hname, pi to left ; hname, pi to right ;receive hname, xi from right ; receive hname, yi from left ;if x = p and y = p then statep := elected ;if x > p or y > p then statep := relayendАлгоритм 11.3. Алгоритм Франклина избрания лидера на кольцеобоих соседей всякого «уцелевшего» процесса).

Активный процесс, ближайшийактивный сосед которого имеет более старшее имя, становится релейным процессом. Если релейный процесс получает сообщение от одного из своих сосседей,то он просто передает его другому соседу; в алгоритме 11.3 это не указано.11.2.2. Усовершенствование АттьиЧисло сообщений, отправляемых активными процессами в алгоритме, линейно относительно размеров кольца, и в алгоритме 11.4 релейными процессамиуничтожается как можно больше сообщений.Так как число активных процессов после каждого тура сокращается вдвое,сумма по всем log N турам числа активных процессов, участвующих в выборах, ограничена величиной 2N.

Поскольку всякий активный процесс отправляетдва сообщения на каждом туре, число сообщений, отправляемых активными процессами, линейно и равно 4N. Однако сообщениям приходится преодолевать всебольшее и большее расстояние, ввиду того что после i-го тура между двуми соседними активными процессами расположено не менее 2 i релейных. Таким образом, ретрансляция сообщений пассивными процессами вносит решающий вкладв сложность по числу сообщений.В кольцевых сетях это неизбежно; даже если активный процесс осведомлено том, насколько он отдален от своего активного соседа, сообщение должно бытьотправлено по кольцу, ибо это кратчайший путь. В алгоритме Аттьи сохраненапринципиальная схема алгоритма Франклина, но при этом предполагается, чтоактивные процессы располагают сведениями о расстоянии, отделяющем их отближайших активных соседей, и им разрешается использовать хорды, а такжесжатие путей, для того чтобы быстро доставить сообщение hname, pi.

Хорды неприменяются, для того чтобы изменить основные правила соревнования, заложенные в алгоритме.Теперь мы перейдем к рассмотрению хордового кольца с восприятием направления. В начале каждого тура активный процесс осведомлен об относительном местоположении ближайшего активного напарника как слева, так и справа,и он отправляет им свое имя, но используя при этом хорды. Предполагается,что сжатие осуществляется при помощи базовых операций Send(message, g)и Receive(message, g).

Первая из операций отправляет сообщение message по11.2. Выборы на кольцах и хордовых кольцах385пути, для которого SUML = g, а вторая операция обеспечивает прием такогосообщения. Одной из возможных реализаций этих операций является жаднаямаршрутизация, при которой сообщение всегда отправляется по самой большой хорде, не дающей «перелета» (см.

алгоритм 11.5). Конечно, можно применятьи более изощренный способ выбора дуг, но это может повлиять на сложность получившегося в результате алгоритма избрания лидера лишь незначительно.statep := active ; Leftp := −1 ; Rightp := +1 ;while statep = active dobegin Send(hname, pi, Left) ; Send(hname, pi, Right) ;Receive(hname, xi, Right) ; Receive(hname, yi, Left) ;if p > x and p > y thenbegin Send(hpos, 0i, Left) ; Send(hpos, 0i, Right);Receive(hpos, ri, Right) ; Right := Right + r ;Receive(hpos, li, Left) ; Left := Left + l ;if Leftp = 0 then statep := electedendelsebegin (* ретранслировать сообщение hpos, ·i *)Receive(hpos, ri, Right) ; Send(hpos, r + Righti, Left);Receive(hpos, li, Left) ; Send(hpos, l + Lefti, Right)endendАлгоритм 11.4.

Алгоритм Аттьи избрания лидера на хордовом кольцеПервоначально относительные координаты левого и правого активного соседазадаются числами −1 и +1 соответственно. После завершения тура уцелевшиеактивные процессы определяют относительные координаты ближайших активныхпроцессов, отправляя сообщение hpos, .i по цепочке процессов, которые сталирелейными именно после этого тура. Лидерство устанавливается в конце тоготура, в котором уцелеет единственный процесс, за счет того что этот процессобнаружит, что он является своим собственным соседом (Left = 0).Новый алгоритм отличается от алгоритма Франклина только тем, как осуществляют взаимосвязь активные процессы; суммарное количество активных процессов по всем турам остается, как и прежде, равным 2N. Теперь число сообщений, отправляемых активными процессами в каждом раунде, возросло до 4,и общее число операций Send на протяжении работы алгоритма достигло величины 8N.Вначале мы обсудим особый случай, когда сеть является кликой; алгоритмдля этого случая был предложен еще ранее в работе Луи и др.

в работе [134] .Так как сеть является вполне связной, операция Send доставляет сообщениенепосредственно, на это затрачивается одна передача, и общая сложность почислу сообщений будет ограничена 8N сообщениями. И это вновь благоприятно для нас, поскольку Корач и др. в работе [119] установили нижнюю оценкуΩ (N log N) для задачи о выборах на кликах без восприятия направления.386Гл. 11. Восприятие направления и ориентация11.2. Выборы на кольцах и хордовых кольцахСледствие 11.8.