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

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

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

Алгоритм Петерсона/Долева— Клейва— РодеРассмотрим алгоритм избрания лидера в однонаправленном кольце (алго­ритм 7.7). Процесс р является активным в некотором туре, если в начале тураон хранит активный отличительный признак cip. В противном случае р являетсяпассивным и просто ретранслирует все сообщения, которые он получает.

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

7. Алгоритмы избрания лидеранить как с t i p , так и с активным признаком, полученным в сообщении типа(two) . Процесс р отправляет сообщение (two, аспр), чтобы предоставить такуювозможность следующему по порядку активному процессу. Исключительнымявляется тот случай, когда выполняется равенство аспр = cip; тогда данный от­личительный признак остается единственным активным признаком и сообщение(small, аспр) оповещает об этом все процессы.Теорема 7.7. Алгоритм 7.7 решает задачу о выборах для однонаправ­ленных колец с использованием O(NlogN) обменов сообщениями.Д о к а з а т е л ь с т в о . Будем говорить, что процесс участвует в г-м туре,если основной цикл этого процесса выполняется г-й раз. Туры не синхронизиро­ваны глобально; возможна ситуация, при которой один из процессов опережаетна несколько туров другой процесс, расположенный в иной части кольца.

Ноколь скоро каждый процесс отправляет и получает в каждом туре ровно два со­общения и в каналах поддерживается очередность посланий, получатель всякогосообщения будет участвовать в том же туре, в котором находился его отпра­витель. В первом туре все инициаторы активны и каждый активный процессхранит индивидуальный «текущий отличительный признак».Утверждение 7.8. Если в начале i-го тура имеется k > 1 активных про­цессов и все «.текущие отличительные признаки» ci, хранимые этими про­цессами, попарно различны , то в следующий тур перейдет не менее одно­го и не более k/2 процессов. По окончании Нго тура текущие отличитель­ные признаки активных процессов будут вновь попарно различны, и срединих будет находиться самый младший признак.Д о к а з а т е л ь с т в о . После обмена сообщениями вида (one, q), которыеретранслируются пассивными процессами, каждый активный процесс получиттекущий отличительный признак своего ближайшего активного соседа, распо­ложенного против хода часовой стрелки, и этот признак будет во всяком случаене совпадать с его собственным отличительным признаком.

Следовательно, каж­дый активный процесс продолжит этот тур, и произойдет обмен сообщениямивида (two, q), благодаря чему каждый активный процесс получит также текущийотличительный признак второго по близости активного соседа, расположенно­го против хода часовой стрелки. Все активные процессы теперь хранят разныезначения асп, а это означает, что процессы, выдержавшие этот тур, будут в кон­це его хранить разные отличительные признаки. Этот тур выдержит по крайнеймере тот отличительный признак, который был наименьшим в начале тура, и,значит, хотя бы один процесс перейдет в следующий тур. А поскольку отличи­тельный признак, который расположен вслед за локальным минимумом, не будетлокальным минимумом, число процессов, перешедших в следующий тур, не будетпревосходить k/2.□Из утверждения 7.8 следует, что наступит и такой тур (его номер не будетпревосходить величины [logA/J + 1).

в начале которого будет ровно один актив­ный участник, а именно самый младший среди отличительных признаков всехинициаторов.7.2. Кольцевые сети253Утверждение 7.9. Если в начале тура есть только один активный про­цесс р с текущим отличительным признаком cip, то по окончании этоготура алгоритм завершит свою работу, и при этом для каждого процессаq будет выполнено равенство winq = cip.Д о к а з а т е л ь с т в о . Сообщение (one, cip), отправленное процессом р,будет ретранслировано всеми процессами и в конце концов будет получено самимпроцессом р. Процесс р убедится в том, что выполняется равенство аспр = cip,и отправит сообщение (small, аспр) по кольцу, вынудив тем самым каждый про­цесс q выйти из основного цикла, присвоив при этом переменной winq значениеаспр.□Рассматриваемый нами алгоритм завершает свое выполнение в каждом изпроцессов, и при этом все процессы будут согласованно оповещены об отличи­тельном признаке лидера (этот признак является значением переменной winq).Процесс с указанным признаком будет пребывать в состоянии leader, а всеостальные процессы — в состоянии lost.Потребуется самое большее |_log A^J + 1 туров, в каждом из которых происхо­дит обмен ровно 2N сообщениями; это и служит обоснованием оценки сложности2N log jV+0(N) по числу обменов сообщениями.

Доказательство теоремы 7.7 за­вершено.□Долеву, Клейву и Роде удалось улучшить их алгоритм так, что верхняя оценкасложности была уменьшена до 1.5Л/ logЛ7, после чего Петерсон сумел построитьалгоритм, в котором используется всего лишь 1,447V log TVобменов сообщениями.Но и эта оценка была впоследствии уменьшена Долевым, Клейвом и Роде до1.356/VlogiV.

В течение 10 лет верхняя оценка 1.3567V log jV для задачи о выборахна кольцах оставалась самой точной, но и она была уменьшена до 1.271 TVlog TVХайемом и Пржитикой в работе [104].7.2.3. Результат о нижних оценкахВ этом параграфе дается обоснование нижней оценке сложности задачи о вы­борах на однонаправленных кольцах. Так как выборы можно провести по хо­ду одного-единственного выполнения децентрализованного волнового алгоритма,в качестве следствия будет получена и нижняя оценка сложности децентрализо­ванных волновых алгоритмов на кольцах.Этот результат был получен Пачлом, Корачем и Ротемом в работе [156]в рамках следующих допущений.1.Оценка установлена для алгоритмов, вычисляющих самый младший от­личительный признак. Если лидер известен, то самый младший отличительныйпризнак можно вычислить с использованием N обменов сообщениями, а еслисамый младший отличительный признак известен хотя бы одному процессу, топроцесс с этим признаком может быть избран лидером также с использованиемN обменов сообщениями.

Следовательно, сложность задачи о выборах и слож­ность задачи вычисления самого младшего отличительного признака отстоят другот друга самое большее на N обменов сообщениями.254Гл. 7. Алгоритмы избрания лидера2. Рассматриваемое кольцо однонаправленное.3. Процессы не осведомлены о размерах кольца.4. Предполагается, что в каналах поддерживается очередность сообщений.Это допущение не ослабляет результат, поскольку сложность алгоритмов безсоблюдения очередности сообщений не может быть лучше, чем сложность алго­ритмов, требующих поддержания очередности сообщений.5.

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

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

В рам­ках этих допущений каждое вычисление, начинающееся с заданной конфигура­ции, содержит одно и то же множество событий.В этом параграфе записи s = (si, . . . , S / Д , t, и т. п. будут использоваться дляобозначения наборов попарно различных отличительных признаков. Множествовсех таких наборов обозначим D, т. е.D = {(si, . . .

, sk) : si € V и i ф j =^> s,- ф s,}.Длину набора s обозначим len(s), а конкатенацию наборов s и t обозначим st.Циклическим сдвигом набора s назовем такой набор s's", что s = s"s'; ясно,что этот набор имеет вид s,-, . . . , sa/, Si , • • •, s,-_i. Запись CS(s) будет обозначатьмножество циклических сдвигов набора s. Нетрудно видеть, что размер множе­ства CS(s) равен длине набора s.Будем говорить, что кольцо помечено набором (si, .

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

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