Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 72
Текст из файла (страница 72)
Если обход завершится (будет принято решение), тоинициатор этого обхода будет считаться избранным; из самого описания алгоритма следует, что это случится в точности для одного обхода. В этом разделемы опишем данный алгоритм для случая, когда в каналах поддерживается очередность, но если добавить совсем немного информации, которая будет переноситься маркерами и обрабатываться процессами, то указанный алгоритм можнобудет использовать и в том случае, когда очередность сообщений в каналах негарантируется (см. [118]).Чтобы справиться с той ситуацией, когда есть несколько инициаторов, алгоритм оперирует на разных уровнях , подобно тому как алгоритм Петерсона/Долева—Клейва—Роде разбивает свое вычисление на туры. Если запущеныпо крайней мере два обхода, то один из маркеров рано или поздно достигнеттого процесса, в котором уже успел побывать другой. Если сложится такая ситуация, то обход, который проводится при помощи вновь прибывшего маркера,будет прерван.
Цель работы нашего алгоритма теперь состоит в том, чтобы привести две маркера вместе в один процесс, где они будут подавлены, и после этогоначнется новый обход. Этот прием напоминает аналогичный прием в алгоритмеПатерсона/Долева—Клейва—Роде, когда не более чем один из двух отличительных признаков имеет возможность уцелеть и перейти в другой тур. Вместо туровв алгоритме Корача—Каттена—Морана используются уровни; две маркера даютначало новому обходу только в том случае, если они находятся на одном и том жеуровне, и при этом уровень вновь запущенного обхода будет на единицу больше.Если какой-либо маркер встречается с другим маркером более высокого уровняили достигает узла, который уже посетил маркер более высокого уровня, то этотГл. 7.
Алгоритмы избрания лидера274прибывший маркер просто подавляется без всякого влияния на маркер болеевысокого уровня.var letip'■ in teg e rin it —1 ;catp, waitp : Vin it udef ;lastp: Neighpin it u def ;b egin if p is initiator thenbegin levp := levp + 1 ; lastp := travip, levp) ;catP := p ; send (annex, p, levp) to lastpend;w h ile . . . (* Условие завершения, см. описание *) dob egin receive token (q, l) ;if token is annexing th en t := A e ls e t := C ;if / > levp th en (* Вариант I *)b egin levp := l ; catp := q ; waitp := udef ; lastp := trav(q, l) ;send (annex, q, l) to lastpendelse if / = levp and waitp ф udef th en (* Вариант II *)b egin waitp := udef ; levp := levp + 1 ; lastp := travip, levp) ; catP := p ;send (annex, p, levp) to lastpendelse if / = levp and lastp = udef th en (* Вариант III *)waitpqelse if / = levp and t = A and q = catp th e n (* Вариант IV *)b egin lastp := trav(q, l) ;if lastp = decideth en p объявляет себя лидером e ls e send (an n ex, q, l) to lastpendelse if / = levp and ((t = A and q > catp) or t = C) th en (* Вариант V *)b egin send (ch ase, q, l) to lastp ; lastp := udef en delse if / = levp th en waitp := q (* Вариант VI *)endendАлгоритм 7.13.
Алгоритм Кррача—Каттена—МоранаМы будем рассматривать алгоритм 7.13. Чтобы привести маркеры одногои того же уровня совместно в один процесс, каждому маркеру предписывается один из трех режимов: захват, погоня или ожидание. Всякий маркер будемпредставлять в виде пары (q, I), где q — это инициатор данного маркера, а I — этоего уровень. Переменная levp будет обозначать уровень, на котором пребываетпроцесс р , а переменная catp представляет инициатора того последнего маркера,который был захвачен процессом р, но уцелел и был переправлен эти процессомдалее (это и есть текущий активный обход процесса р). Переменная w aitpпринимает значение udef, если ни один из маркеров не пребывает в режимеожидания в процессе р, и значение этой переменной равно q, если некоторыймаркер (q, levp) пребывает в режиме ожидания в процессе р.
Переменная la stp7.4. Алгоритм Корача—Каттена—Морана275предназначена для маркеров, пребывающих в режиме погони: она указывает натого соседа, которому процесс р переправил захваченный им маркер уровня levp,если только догоняющий маркер уже не был отправлен вслед за ним в погоню;в таком случае lastp = udef. Наш алгоритм взаимодействует с алгоритмом обхода за счет обращения к функции trav: эта функция либо указывает того соседа,которому нужно переправить маркер, либо заявляет о принятии решения, еслиданный обход завершился.Маркер (q, I) инициируется в режиме захвата, и в этом режиме он подчиняется алгоритму обхода (как и в случае IV для алгоритма 7.13), до тех пор покане сложится одна из следующих ситуаций.1. Алгоритм обхода завершен, и в таком случае процесс q становится лидером (см.
вариант IV в описании алгоритма 7.13).2. Маркер достиг такого узла р, для которого выполняется неравенство levp >> /; в этом случае наш маркер подавляется. (Этот вариант подразумевается в алгоритме 7.13; все условия в этом алгоритме требуют выполнения соотношения/ > levp или / = levp).3. Маркер достиг такого узла, в котором его уже ожидает другой маркеруровня /; тогда оба маркера подавляются, и из этого узла начинается новыйобход (см. вариант II в описании алгоритма 7.13).4.
Маркер достиг узла уровня /, который посетил последним некоторый маркер с отличительным признаком catp > q (см. вариант VI) или маркер в режимепогони (см. вариант III); тогда наш маркер переходит в режим ожидания и остается в этом узле.5. Маркер достиг узла уровня I, в котором в последний раз побывал некоторый маркер в режиме захвата с отличительным признаком catp < q; тогданаш маркер переходит в режим погони и переправляется по тому же каналу, покоторому был отправлен предыдущий маркер (см. вариант V).Маркер (q, I) в режиме погони переправляется в каждом узле по тому каналу,по которому был отправлен самый последний из посетивших этот узел маркеров,если только не складывается одна из следующих ситуаций.1.
Маркер достиг процесса уровня levp > /; тогда наш маркер подавляется.2. Маркер достиг процесса, в котором хранится маркер уровня /, пребывающий в режиме ожидания’, тогда оба маркера изымаются и в этом процессеначинается новый обход (см. вариант II).3. Маркер достиг процесса уровня /, и при этом последний из посетившихэтот процесс маркеров пребывал в режиме погони’, тогда наш маркер переходитв режим ожидания (см. вариант III).Маркер в режиме ожидания остается в том процессе, которого он достиг, до техпор пока не сложится одна из следующих ситуаций.1. Маркер более высокого уровня достигнет того же самого процесса; тогдаожидающий маркер будет подавлен (см.
вариант I).2. Маркер того же самого уровня достиг того же самого процесса; тогда обамаркера изымаются, и в данном процессе начинается новый обход более высокогоуровня (см. вариант II).276Гл. 7. Алгоритмы избрания лидераВ алгоритме 7.13 все переменные и переносимые маркерами данные, касающиесяалгоритма обхода, не принимались во внимание. Отметим, что если процесс рполучает маркер, уровень которого превосходит levp, то этот маркер пребываетв режиме захвата и его инициатором является процесс, отличный от р. Если жеобход завершается в узле р, то р становится лидером и отправляет сообщениявсем процессам, призывая их прекратить работу.Корректность и сложность. Для доказательства корректности алгоритмаКорача—Каттена—Морана будет показано, что число маркеров, порожденныхна каждом уровне, сокращается, до тех пор пока на некотором уровне не будетвыпущен только один маркер, инициатор которого и становится лидером.Лемма 7.22.
Если на уровне I было порождено 6 > 1 маркеров , то науровне I + 1 будет порождено не менее одного и не более 6 / 2 маркеров.Д о к а з а т е л ь с т в о . Поскольку при порождении одного маркера уровня / + 1 подавляются два маркера уровня /, всего на уровне / + 1 может бытьвыпущено не более 6 / 2 маркеров.Предположим, что найдется такой уровень /, что на уровне / было порождено6 > 1 маркеров, а на уровне / + 1 ни одного. Обозначим символом q процессс наибольшим отличительным признаком, который породил маркер на уровне I.Маркер (q, I) не завершает обход, так как он достигает некоторого процесса р,который уже отправил другой маркер уровня /. Когда это произойдет впервые,маркер (q, /) станет преследователем или, если процесс р уже отправил какой-топреследующий маркер, перейдет в режим ожидания.
В любом случае это означает, что в сети есть преследующий маркер уровня /.Рассмотрим маркер (г, /) с наименьшим отличительным признаком, за которым был отправлен в погоню один из преследующих маркеров. Сам маркер (г, /)не может быть преследователем, поскольку преследователи гонятся за маркерами с меньшим отличительным признаком.
Поэтому мы можем предполагать, чтомаркер (г, /) переходит в режим ожидания, как только он достигнет процесса р',который уже отправил какой-либо другой маркер уровня /. Пусть р" — последний из процессов на пути, по которому следует маркер (г, /), причем этот процессполучил после отправления (г, /) маркер, пребывавший в режиме захвата, который перешел затем в разряд преследователей маркера г.
Этот преследующиймаркер либо настигнет маркер (г, /) в узле р', либо прервет погоню, если обнаружит какой-нибудь маркер, пребывающий в режиме ожидания, ранее чем будетдостигнут узел р '. В обоих случаях, вопреки предположению, будет выработанмаркер уровня / + 1 .□Теорема 7.23. Алгоритм Корача— Каттена—Морана (алгоритм 7.13)является алгоритмом избрания лидера.Д о к а з а т е л ь с т в о . Допустим, что хотя бы один процесс запустил этоталгоритм. Согласно предыдущей лемме число маркеров, порожденных на каждом уровне, уменьшается, и поэтому найдется уровень, например уровень /, накотором будет порожден всего лишь один маркер, скажем (q, /). Ни один из мар7.4.
Алгоритм Корача—Каттена—Морана277керов уровня /' < / не завершил обход, и поэтому ни один из них не привел ктому, что некоторый процесс был избран лидером. Единственный маркер уровня/ сталкивается только с такими процессами, уровень которых уступает / или длякоторых выполняется равенство c a t = q (если этот маркер достигает процесса,который он уже посетил ранее). В обоих случаях процессы переправляют егодалее. Следовательно, обход завершится, и процесс q будет избран лидером.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
