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

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

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

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

Вычисление размера сети345выбор был совершен везде в заданном кольце. И хотя этого события нельзя со­всем исключить, вероятность того, что оно произойдет, ограничена, и на самомделе она убывает по мере увеличения размеров кольца.9.4.2. Алгоритм вычисления размера кольцаВ этом параграфе представлен алгоритм типа Монте-Карло, вычисляющийразмер кольца и оканчивающий работу по завершении обмена сообщениями. Какбудет показано, по окончании работы алгоритма для всех процессов р будет вы­полняться равенство estp = N с вероятностью, которую можно сделать скольугодно близкой к единице за счет выбора параметра R. Этот алгоритм сходенс алгоритмом, предложенным Айтаи и Роде [111], но немного упрощен.Процесс р вычисляет локальную оценку размера кольца, estp, и при этомгарантируется, что в любой момент времени эта оценка консервативна, т.

е.,estp < N. Вначале estp = 2. Всякий раз, когда процесс р получет информа­цию, свидетельствующую о том, что оценка estp не равна размеру кольца, рувеличивает свою оценку.Чтобы быть уверенным в правильности своей оценки, процесс р порождаетмаркер и отправляет его на расстояние estp переходов по кольцу. Если оценкаоказыватся правильной, р получает обратно свой маркер, и если это происходит,р удовлетворяется результатом (временно) и не предпринимает дальнейших дей­ствий. Процесс р получает подобный маркер в случае, когда размер кольца N вдействительности превосходит оценку estp, но процесс, отстоящий от р на (estp)переходов против часовой стрелки, выработал ту же самую оценку и отправилсвой маркер.Такую ситуацию (в которой процесс р получает не принадлжащий ему маркер)можно распознать с большой вероятностью; каждый процесс выбирает случай­ным образом метку из множества {1, .

. . , R} и присоединяет ее к своему маркеру.Метка процесса, выбранная процессом р, остается неизменной, до тех пор покане увеличится оценка размера сети. Если процесс р получает маркер, выпущен­ный другим процессом, то с вероятностью 1 — 1/R присоединенная к нему меткаотличается от метки процесса р, а если процесс получает свой собственный мар­кер, то его метка наверняка совпадает с меткой процесса.Процесс р увеличивает локальную оцнку размера сети в двух случаях.1.

Получен маркер, содержащий оцнку est, удовлетворяющую неравен­ству est > estp. Так как алгоритм обеспечивает консервативность всех оценок,получение такого маркера означает, что N > estp.2. Получен маркер, содержащий оценку est = estp, причем этот маркерсовершил est переходов, но присоединенная к нему пометка отличаетсяот пометки процесса р. Этот маркер был выпущен процессом, отстоящим от рна (est) переходов против часовой стрелки, и этот процесс имеет пометку, отлич­ную от пометки процесса р.

Следовательно, (est) -й по порядку сосед процесса ротличен от самого р, а это означает, что N ф est.Маркер, несущий оценку est < estp, изымается (т. е. его распространение пре­рывается); см. алгоритм 9.5.Гл. 9. Анонимные сети346cons Rvar estp1ЫР: integer: integer;: integer;; (* Опрделяет вероятность правильного результата *)begin estp := 2 ; lblp := rand({l, . . .

, t?});send (test, estp, lblp, 1) to Nextp ;while true dobegin receive (test, est, Ibl, h) ;if est > estp then (* Оценка процесса p должна быть увеличена*)if est = h then (* est также слишком мала *)begin estp := est + 1 ; lblp := rand({l, . . . , R } ) ;send (test, estp, lblp, 1) to Nextpendelse (* отправляет маркер далее и увеличивает estp *)begin send (test, est, 1Ы, h + 1) to Nextp ; estp := e s t ;lblp := rand({l, ..., R}); send (test, estp, lblp, 1) to Nextpendelse if est = estp thenif h < est then send (test, est, 1Ы, h + 1) to Nextpelse (* Этот маркер совершил est перходов *)if Ibl ф lblp thenbegin estp := est + 1 ; lblp := rand({ 1, .

. . , R}) ;send (test, estp, lblp, 1) to Nextpendelse skip (* Возможно, что вернулся маркер процесса р *)else (* est < estp *) skipendendАлгоритм 9.5. Вероятностное вычисление размера кольцаЛемма 9.14. Приведенный алгоритм оканчивает работу по заверше­нии обмена 0(N 3) сообщениями. В заключительной конфигурации все пе­ременные estp равны, и их общее значение ограничено величиной N, т. е.для любой пары процессов р и q выполняется соотношение estp = estq ^ N.Д о к а з а т е л ь с т в о . Решающий этап обоснования завершаемости алго­ритма— это демонстрация того, что оценки действительно остаются консерва­тивными.

Заметим, что значение переменной estp никогда не убывает, а значениепеременной 1ЫР изменятся только тогда, когда увеличивается значение estp. От­сюда следует, что, пока циркулирует маркер (test, est, Ibl, h), выпущенный про­цессом р, и выполняется равенство est = estp, будет выполняться и равенство1ЫР = Ibl. Воспользовавшись этим, можно провести индуктивное обоснованиетого, что все вычисленные оценки консервативны.Так как оценки, заложенные в маркеры, вычислены самими процессами, до­статочно рассмотреть вычисление оценок, осуществляемое процессами.

Здесьможно выделить три случая.9.4. Вычисление размера сети3471. Процесс р может увеличить значение estp до est после получения маркерас оценкой est. А так как эта оценка была вычислена ранее, по предположниюиндукции можно считать, что она консервативна.2. Процесс р может увеличить значение estp до est + 1 после получениямаркера с оценкой est, если счетчик переходов маркера также показывает est.В таком случае, est консервативна по индуктивному предположению и, кроме тоговерно соотношение N ф est, поскольку процесс, выпустивший данный маркер,отличен от процесса р и отстоит от него на est переходов.3. Наконец, процесс р можт увеличить estp до est+ 1 после получения марке­ра с оценкой est = h = estp, если его пометка 1Ы Ф 1ЫР.

Процесс, выпустившийэтот маркер, отстоит на est переходов от р. А так как Ibl Ф 1ЫР, этот процессбудет отличен от р. И вновь отсюда следует, что N ф est, а консервативностьоценки est влечет неравенство N > est.Каждый процесс порождает менее N различных маркеров, оценки которых про­бегают числа от 2 до А, и при этом маркер с оценкой е совершает не более епереходов. Отсюда следует, что число обменов сообщениями огранично величи­ной О (А3). Если процесс р увеличивает значение estp, например до величины е, тор отправляет процессу Nextp маркер, содержащий значение е.

После полученияэтого маркера переменная estfjextp будет иметь значение, не уступающее е, и по­этому в заключительной конфигурации выполняется неравенство est^extp ^ estp.Оно выполняется для всех процессов р, и отсюда следует, что все оценки будутравны. А ранее мы показали, что они ограничены величиной N.□Теорема 9.15. Алгоритм 9.5 всегда завершает работу, и после завер­шения работы для всех процессов р с вероятностью, не меньшей 1—{N—2){\/R)n/2,выполняется равенство estp = N.Д о к а з а т е л ь с т в о . Согласно лемме 9.14 работа алгоритма завершает­ся такой конфигураций, в которой все оценки равны.

Обозначим общее значениеэтих оценок символом е и предположим, что е < N. Обозначим процессы сим­волами, начиная с ро и оканчивая рм-\, в порядке их обхода по кольцу противхода часовой стрелки.Процесс pi выбирает пометку lblPi. Он порождает маркер (test, е, lblPi, h),когда значение estPi будет равно е. Этот маркер совершит е переходов и до­стигнет процесса pi+e, который является е-м против хода часовой стрелки сосе­дом процесса рр процесс Pi+e, получив этот маркер, не станет увеличивать своюоценку. Это означает, что равенство lblPl = lblPl+3 соблюдается для всех г. Пусть/ = НОД(А, е). Тогда, учитывая равенства lblPl = lblPt+a, приходим к выводуо том, что всякий раз, когда номера i и / отличаются на величину, кратную /,пометки, выбранные процессами р^ и pj совпадают, т.

е.Ж/ - о=*> 1ЫР1 = 1ЫРГВсе процессы, начиная с ро и оканчиваярм-\, оказываются разбитыми на / групппо А // процессов в каждой так, что все процессы из одной и той же группы имеютодинаковые пометки.348Гл. 9. Анонимные сетиНо поскольку пометки были выбраны случайным образом из множества {1,вероятность того, что все процессы из одной группы выбрали одну и ту же по­метку, будет равна (1 /R)N^ ~ X, а вероятность того, что это произойдет для всехгрупп, будет равна всего лишь (1= (1 /^ )^ ^ .

Для всех возможныхзначений е, величина / не превосходит N / 2, и, суммируя вероятности завершенияработы со всеми возможными неправильными ответами (от 2 до N — 1 ), мы при­ходим к заключению о том, что вероятность правильного ответа будет не меньше1 - ( N - 2 ) ( l / R f / 2.□9.5.

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

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