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

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

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

Инициатор отправляет сообщениена Восток, и сообщение совершает п — 1 переходов в восточном направлении.Инициатор, а также каждая вершина, в которую поступает сообщение с Запада,отправляет сообщение на Север, и сообщение совершит в точности п — 1 шаговв этом направлении.Легко видеть, что такая стратегия срабатывает и при этом происходит в точ­ности N —1 обменов сообщениями; если добавить к ним N — 1 подтверждающихсообщений, то алгоритм будет проводить широковещательную рассылку сооб­щений с обратной связью (PIF). Если бы мы отправили сообщение на один шагдальше на Восток, то его следующим адресатом стал бы сам инициатор, что из­лишне. Если бы мы отправили сообщение на один шаг дальше на Север, его382Гл. 11.

Восприятие направления и ориентацияполучил бы процесс, который сам же и отправил его на Север, а это тоже из­лишне.Этот пример показывает, каким образом униформное восприятие направлениядает информацию о структуре всей сети в целом и как эта информация исполь­зуется в алгоритме. Теперь мы дадим общее описание этого алгоритма, полагая,что в основу сети положена произвольная группа. Расположим пометки начи­ная с gi и оканчивая gk (опуская обратные элементы) в произвольном порядкеи определим величины т , .

. . , rik следующим образом. Прежде всего, величинуп\ положим равной порядку элемента g \ . Далее положим П2 равной порядку g 2в группе G/(g 1); эта величина будет равна наименьшему натуральному числу, длякоторого gi является делителем n<i-g2 - И для каждого i в качестве /г,- выбираетсяпорядок элемента gi в группе G/(g\, • • •, gi-\)', это наименьшее число, для кото­рого элемент щ ■gi можно представить в виде суммы элементов {gi, . . . , g ; - i }.Числа щ обладают следующим свойством: произведение всех этих чисел равно1V, и каждый элемент g из группы G можно представить единственным образомв виде суммыkДля инициатора:for i = 1 to kdo if щ > 1 then send (info,m —1) via linkgiПосле получения сообщения (info, s ) по каналу —gp.if s > 1 then send (info, s —1) via link g j ;for i = j + 1 to kdo if S i > 1 then (info, S; —1) via link g iАлгоритм 11.2. Широковещательная рассылка с униформным восприятиемнаправленияВ алгоритме 11.2 информация отправляется на п\ — 1 переходов в направле­нии gi и достигает всех процессов, отличие которых от инициатора описываетсяэлементом группы, кратным g\.

Инициатор и все процессы, получающие сообще­ние по направлению —gi, отправляют его по направлению g 2 на П2 ~ 1 переходов;таким образом, сообщение достигает всех процессов, отличие которых от ини­циатора выражается элементом группы, представляющим собой сумму элемента,кратного gi, и элемента, кратного g 2 . В общем случае инициатор и все процессы,получившие сообщение по направлениям начиная с —gi и оканчивая —g,-_i, от­правляют это сообщение далее по направлению gi на щ —1 переходов.

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

Глу­бина остовного дерева, которое строится рассматриваемым алгоритмом, равна~ 1 ); в случае необходимости глубину можно изменить, избрав другойпорядок расположения элементов g i , ■■■, g k в списке пометок L . Мы не бу­дем здесь заниматься исследованием этого вопроса, который связан с временнойсложностью широковещательного распространения информации.11.2.

Выборы на кольцах и хордовых кольцахЗадача избрания лидера на кольцах и хордовых кольцах имеет долгую ис­торию (см. §7.5.2). В § 11.2.1 мы опишем решение, Франклином в работе [90],которое было улучшено Аттьей и др. в работе [10] за счет использования хорд,добавленных (униформно) к кольцу. В их алгоритме большую роль играет спо­собность сжимать пути, и, как будет показано в §§11.2.2 и 11.2.3, линейнойсложности можно достичь, добавив к кольцу совсем немного хорд. В этом алго­ритме, однако, используется одна лишь способность сжимать пути, не затраги­вающая особенностей структуры сети. В § 11.2.4 мы продемонстрируем, что дляполучения линейного алгоритма понадобится еще меньше хорд, если структурасети также будет принята в расчет.11.2.1.

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

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

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

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

Поскольку всякий активный процесс отправляетдва сообщения на каждом туре, число сообщений, отправляемых активными про­цессами, линейно и равно AN. Однако сообщениям приходится преодолевать всебольшее и большее расстояние, ввиду того что после /-го тура между двуми со­седними активными процессами расположено не менее 2' релейных. Таким обра­зом, ретрансляция сообщений пассивными процессами вносит решающий вкладв сложность по числу сообщений.В кольцевых сетях это неизбежно; даже если активный процесс осведомлено том, насколько он отдален от своего активного соседа, сообщение должно бытьотправлено по кольцу, ибо это кратчайший путь. В алгоритме Аттьи сохраненапринципиальная схема алгоритма Франклина, но при этом предполагается, чтоактивные процессы располагают сведениями о расстоянии, отделяющем их отближайших активных соседей, и им разрешается использовать хорды, а такжесжатие путей, для того чтобы быстро доставить сообщение (паше, р).

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

Первая из операций отправляет сообщение message по11.2. Выборы на кольцах и хордовых кольцах385пути, для которого SUMc = g, а вторая операция обеспечивает прием такогосообщения. Одной из возможных реализаций этих операций является жаднаямаршрутизация , при которой сообщение всегда отправляется по самой боль­шой хорде, не дающей «перелета» (см. алгоритм 11.5). Конечно, можно применятьи более изощренный способ выбора дуг, но это может повлиять на сложность по­лучившегося в результате алгоритма избрания лидера лишь незначительно.stateP := active ; Leftp := —1 ; Rightp := +1 ;while statep = active dobegin Send({name, p), Left) ; Send((name, p), Right) ;Receive{(name, x), Right) ; Receive))name, y), Left) ;if p ^ x and p > у thenbegin Send){pos, 0), Left) ; Send))pos, 0), Right)',Receive){pos, r), Right) ; Right := Right + r ;Receive){pos, /), Left) ; Left := Left + / ;if Leftp = 0 then statep := electedendelsebegin (* ретранслировать сообщение (pos, •) *)Receive({pos, r), Right) ; Send))pos, r + Right), Left)',Receive({pos, /), Left) ; Send))pos, / + Left), Right)endendАлгоритм 11.4.

АлгоритмАттьи избрания лидера на хордовом кольцеПервоначально относительные координаты левого и правого активного соседазадаются числами —1 и +1 соответственно. После завершения тура уцелевшиеактивные процессы определяют относительные координаты ближайших активныхпроцессов, отправляя сообщение (pos, .) по цепочке процессов, которые сталирелейными именно после этого тура. Лидерство устанавливается в конце тоготура, в котором уцелеет единственный процесс, за счет того что этот процессобнаружит, что он является своим собственным соседом {Left = 0).Новый алгоритм отличается от алгоритма Франклина только тем, как осу­ществляют взаимосвязь активные процессы; суммарное количество активных про­цессов по всем турам остается, как и прежде, равным 2N.

Теперь число сооб­щений, отправляемых активными процессами в каждом раунде, возросло до 4,и общее число операций Send, на протяжении работы алгоритма достигло вели­чины 8 N.Вначале мы обсудим особый случай, когда сеть является кликой; алгоритмдля этого случая был предложен еще ранее в работе Луи и др. в работе [134].Так как сеть является вполне связной, операция Send доставляет сообщениенепосредственно, на это затрачивается одна передача, и общая сложность почислу сообщений будет ограничена 8 N сообщениями.

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

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