Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 90
Текст из файла (страница 90)
Получение такого маркераозначает, что ни один процесс не выбрал меньший отличительный признак; ноэтого недостаточно, чтобы считаться избранным лидером, поскольку может оказаться так, что существует еще один процесс с тем же отличительным признаком.Чтобы распознать такую ситуацию, каждый маркер снабжен булевой переменнойun, которая при генерации маркера имеет значение true и принимает значениеfalse, если маркер передается процессом с тем же отличительным признаком.
Таким образом, процесс становится лидером, когда он получает свой собственныймаркер и при этом выполняется равенство un = true.Последнее затруднение возникает в случае, когда процесс получает свой собственный маркер, но при этом выполняется равенство un = false; это означает,что процесс имеет минимальный отличительный признак, но при этом существуети другой процесс с тем же отличительным признаком. Все процессы с минимальным отличительным признаком могут получить свой собственный маркер и стать«победителями» алгоритма Ченя—Робертса. Если такое случится, то каждый«победитель» алгоритма Ченя—Робертса переходит в следующий тур и вновьзапускает алгоритм Ченя—Робертса. Чтобы предотвратить очередную «ничью»,каждый процесс начинает новый тур с того, что выбирает новый отличительныйпризнак. Порядковый номер тура также отражен в маркере, и маркеры того илииного уровня пресекают всякую деятельность, относящуюся к турам с меньшимпорядковым номером.Подводя итог, заметим, что получение процессом p своего собственного маркера приводит к тому, что он становится победителем алгоритма Ченя —Робертса,если этот процесс пребывает в состоянии cand.
Если p — единственный победитель, то он становится лидером; в противном случае p запускает алгоритм Че-340Гл. 9. Анонимные сетиvar statep : (sleep, cand, leader, lost)init sleep ;levelp: integerinit 0 ;idp: integer;stopp: boolinit false ;begin if p is initiator thenbegin levelp := 1 ; statep := cand ; idp := rand({1, .
. . , N}) ;send htok, levelp , idp , 1, truei to Nextpend;while not stopp dobegin receive a message ; (* это либо маркер, либо сообщение о готовности*)if it is a token htok, level, id, hops, uni thenif hops = N and statep = cand thenif un then (* считается избранным *)begin statep := leader ; send hreadyi to Nextp ;receive hreadyi ; stopp := trueendelse (* на этом уровне есть и другие победители *)begin levelp := levelp + 1 ; idp := rand({1, . .
. , N}) ;send htok, levelp , idp , 1, truei to Nextpendelse if level > levelp or (level = levelp and id < idp) thenbegin levelp := level ; statep := lost;send htok, level, id, hops + 1, uni to Nextpendelse if level = levelp and id = idp thensend htok, level, id, hops + 1, falsei to Nextpelse skip (* очистить маркер *)else begin send hreadyi to Nextp ; stopp := true endendendАлгоритм 9.4. Алгоритм Айтаи–Роде избрания лидераня—Робертса в следующем туре. Если процесс p получает маркер, порожденныйдругим процессом, то p переходит в состояние lost в том случае, когда этот маркер был порожден в одном из последющих туров или был порожден в том жетуре, но при этом имеет меньший отличительный признак; маркер при этом передается далее по кругу.
Маркер, порожденный в том же туре и несущий такой жеотличительный признак, передается, но переменной un придается значение false.Маркер, порожденный в одном предыдущих туров, или порожденный в том жетуре, но несущий меньший отличительный признак, изымается из обращения (т. е.его передача прекращается); см. алгоритм 9.4. Далее мы покажем, что алгоритмчастично корректен и завершает работу с вероятностью, равной единице.Лемма 9.10. Если хотя бы один процесс порождает маркер в туре l,то либо один процесс будет избран лидером в этом туре и ни один процесс9.3. Вероятностный алгоритм избрания лидера341не порождает маркера в следующем туре l + 1, либо хотя бы один процесспорождает маркер в туре l + 1.Д о к а з а т е л ь с т в о.
Процесс p порождает маркер в (l + 1) -м туре, еслион получает свой собственный маркер (в l-м туре).Допустим, что процесс p порождает маркер в l-м туре, но отличительныйпризнак процесса не является минимальным среди отличительных признаков,которые были задействованы в l-м туре. В таком случае маркер не вернетсяк процессу p; если этот маркер не будет устранен процессом, прошедшим в более высокий тур, он будет доставлен процессу, оперирующему в том же туреи имеющему меньший отличительный признак, где и будет устранен. (Обращаемвнимание на то, что все процессы, которые порождают маркер в l-м туре, совершают это до того, как получат маркер процесса p в l-м туре.) Отсюда следует,что только тот процесс, которому достался минимальный отличительный признакв l-м туре, может быть избран в том же туре или получает право выработать маркер в (l + 1)-м туре.Допустим, что процесс p порождает маркер в l-м туре и отличительный признак этого процесса является минимальным среди отличительных признаков, которые были задействованы в l-м туре.
Если данный маркер не будет устраненкаким-либо процессом, участвующим в более высоком туре (в таком случае хотя бы один процесс порождает маркер в (l + 1) -м туре), то этот маркер будетвозвращен процессу p. Возможны два случая: либо p является единственнымпроцессом, которому достался минимальный отличительный признак в l-м туре, либо имеются еще и другие процессы, обладающие таким же отличительнымпризнаком.
В первом случае маркер возвращается с пометкой un = true и процесс p избирается лидером. Во втором случае, маркер возвращается с пометкойun = false и в (l + 1)-м туре будет порожден какой-нибудь маркер.Теорема 9.11. Алгоритм Айтаи—Роде (алгоритм 9.4) является частично корректным алгоритмом избрания лидера для колец заранее неизвестного размера, завершающим работу с вероятностью, равной единице.Д о к а з а т е л ь с т в о. Частичная корректность алгоритма, означающая, чтов случае завершения работы остается в точности один лидер, доказывается с использованием леммы 9.10.
Предположим, что l — это номер наивысшего тура,в котором вырабатывался маркер; величина l определена, поскольку по предположению рассматривается конечное вычисление. Тот факт, что ни один процессне был избран в младших турах и ни один маркер не был порожден в (l + 1) -мтуре, означает, что в l-м туре в точности один процесс был избран лидером.Остается показать, что алгоритм завершает работу с вероятностью, равнойединице. Если в некотором туре l имеются k > 1 процессов, которые выработалимаркеры в туре l, то существует вероятность Pk > 0 того, что в этом туре в точности одному процессу достанется минимальный отличительный признак, и тогдаалгоритм завершит работу.
Обозначим символом P наименьшее значение P k повсем k; теперь если маркеры были выработаны в l-м туре, то вероятность того,что маркеры будут порождены также и в (l + 1)-м туре, не превосходит величи-342Гл. 9. Анонимные сети343будет показано, вероятность такого повторения отлична от нуля, и это следует изтого, что при выполнении конечных вычислений всякий процесс использует лишьконечный префикс последовательности случайных битов.Теорема 9.12. Не существует алгоритма, оканчивающего вычисленияпо завершении работы процессов и правильно вычисляющего размер кольца с вероятностью r > 0.Д о к а з а т е л ь с т в о. Предположим, что есть вероятностный алгоритм A,проводящий -вычисление CN на кольце размера N, и в вычислении CN каждыйпроцесс p завершает работу с результатом resultp = N.
Выберем произвольныйпроцесс p и предположим, что самая длинная трасса сообщения, полученногоэтим процессом p в вычислении CN , имеет длину K. В вычислении CN каждыйпроцесс выполняет только конечное число шагов; обозначим символом L наибольшее число шагов, выполняемых всяким процессом в вычислении C N .Рассмотрим кольцо большего размера, в котором содержится сегмент из K + 1процессов. Обозначим символом p0 последний процесс этого сегмента, а символом pi — i-й по порядку процесс сегмента, отстоящий от p 0 против хода часовой стрелки.
Рассмотрим набор двоичных последовательностей 0 , приписанныхпроцессам этого кольца и обладающих следующим свойством. Первые L битовпоследовательности 0p0 точно те же, что и первые L битов последовательности.Первые L битов последовательности 0pi , где i 6 K, точно те же, что и первые Lбитов последовательности q , где q — это i-й по порядку процесс, отстоящий от pпротив часовой стрелки в кольце размера N. Если длина сегмента K + 1 задана,то вероятность появления такого набора последовательностей очень мала, онаравна 2− (K +1)L .Существует 0 -вычисление C алгоритма A на кольце большого размера, в ходе которого процесс pi отправляет в точности те же сообщения, имеющие трассыдлины не больше 6 K + 1 − i, что и i-й по порядку процесс, отстоящий противчасовой стрелки от процесса p в малом кольце, в ходе вычисления C N .
Это доказывается точно так же, как делалось при обосновании теоремы 9.8. Как видно изпостроения, для всякого заданного сегмента длины K + 1 процессы этого сегмента с вероятностью, не меньшей 2− (K +1)L , повторят вычисление CN , в результатечего процесс p0 завершит работу с результатом resultp0 = N, а этот результатневерен.Вероятность того, что это произойдет на некотором заданном сегменте, чрезвычайно мала, но, выбрав кольцо достаточно большого размера, мы можем добиться того, что вероятность осуществления этого события в каком-либо сегменте кольца станет сколь угодно большой. Пусть задана вероятность r > 0. Возьмемтакое натуральное число R, чтобы выполнялось неравенство (1 − 2 − (K +1)L) R < r,и рассмотрим кольцо размера R(K + 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
