Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 91
Текст из файла (страница 91)
В этом кольце есть R непересекающихсясегментов длины K + 1, и для каждого из этих сегментов вероятность того, чтопоследний процесс не может завершить вычисление с неправильным ответом, непревосходит 1 − 2− (K +1)L . Тогда вероятность того, что ни один из процессов незавершит вычисление с неправильным ответом, будет меньше r.9.4. Вычисление размера сетиРазнообразные результаты, представленные в этой главе, свидетельствуюто том, насколько важно знание размера сети. В этом параграфе мы рассмотримзадачу вычисления размера сети.
Размер кольца может быть вычислен только припомощи алгоритма, оканчивающего работу по завершении обмена сообщениями,и при этом вероятность неправильного ответа будет отлична от нуля.9.4.1. Отрицательные результатыВ этот параграф включены два результата, касающиеся невозможности вычисления размера кольца. Обоснование этих результатов опирается на ту жеидею, которая использовалась для доказательства теоремы 9.8, а именно на идеюо возможности повторения заданного (предположительно правильного) вычисления в различных частях большого кольца. Для вероятностных алгоритмов, какПроизвольные сети.
Воспользовавшись почти теми же самыми идеями, можно построить алгоритм проведения выборов в произвольных сетях. В основу этогоалгоритма положен алгоритм 7.9, а не алгоритм Ченя —Робертса. Процесс «одерживает победу» в очередном туре этого алгоритма, если он инициировал алгоритмэха и все соседние процессы откликнулись эхом. Как и в алгоритме Айтаи —Роде,этого условия еще не достаточно, чтобы стать лидером, так как может оказаться,что выборы были затеяны несколькими процессами с одинаковыми отличительными признаками. Чтобы обнаружить это, размер дерева, построенного алгоритмом эха, вычисляется так, как это делается в алгоритме 9.1.
Если есть несколькоинициаторов с одинаковыми отличительными признаками, то каждый вызов эхаприводит к построению дерева, в котором содержится только часть процессов.Когда процесс завершает выполнение алгоритма эха (получив отклик от каждого из соседей), ему становится известен размер дерева, которое при этом былопостроено. Если этот размер равен N, то процесс становится лидером, а иначеалгоритм эха запускается в следующем туре.Полученный в результате алгоритм является частично корректным, и его работа завершается с вероятностью, равной единице. Полное описание этого алгоритма можно найти в статье [190] .
Другие алгоритмы проведения выборов можноотыскать в работах [171] и [140] .ны 1 − P. Следовательно, вероятность того, что алгоритм не завершит работупосле l туров, ограничена сверху величиной (1 − P) l , которая стремится к нулю,если устремить l к бесконечности.Вероятностный анализ (проведенный в работе [111]) позволил выяснить, чтоожидаемое число туров ограничено величиной eN(N − 1). Ожидаемое число сообщений, отправленных в одном туре, ограничено величиной O(N log N) (это можноустановить, рассуждая подобно тому, как это делалось в теореме 7.6), и отсюда следует, что ожидаемая сложность алгоритма по числу обменов ссобщениямисоставляет величину O(N log N).9.4. Вычисление размера сети344Гл.
9. Анонимные сети9.4. Вычисление размера сетиНа самом деле, применяя те же самые рассуждения, можно установить, чтоникакую функцию, отличную от константы, нельзя правильно вычислить с вероятностью r > 0 при помощи алгоритма, оканчивающего работу по завершенииобмена сообщениями. А вот другой результат того же рода нельзя обобщить наслучай произвольной функции, отличной от константы. Утверждается, что не существует алгоритмов типа Лас-Вегас, оканчивающих работу по завершении обмена сообщениями, и поэтому самое большее, на что можно рассчитывать, — этопостроение алгоритмов типа Монте-Карло, оканчивающих работу по завершенииобмена сообщениями.Теорема 9.13.
Не существует алгоритмов, оканчивающих работу позавершении обмена сообщениями и вычисляющих размер кольца с вероятностью, равной единице.Д о к а з а т е л ь с т в о. Предположим, что есть вероятностный алгоритм A,имеющий -вычисление CN на кольце размера N, который оканчивает работупо завершении обмена сообщениями с результатом result p = N для некоторогопроцесса p.
Каждый процесс совершает только конечное число шагов по ходувычисления CN . Обозначим символом L наибольшее число шагов, которое совершает всякий процесс в вычислении CN . Занумеруем процессы в кольце размераN натуральными числами от 0 до N − 1.Рассмотрим теперь кольцо размера 2N, в котором все процессы занумерованы натуральными числами, начиная с 0 и оканчивая 2N − 1, а также такоесемейство 0 двоичных последовательностей, что для каждого i < N первые Lбитов последовательностей 0qi и 0qi+N , приписанных процессам qi и qi+N большого кольца, в точности повторяют первые L битов последовательности pi , приписанной процессу pi малого кольца.
Устройство 0 -вычисления алгоритма A накольце размера 2N таково. Каждый шаг процесса p i в вычислении CN повторяется параллельно процессом qi и его антиподом qi+N . Поскольку последняяконфигурация вычисления CN является заключительной, таковой же является изпоследняя конфигурация вычисления C2N , и в этой конфигурации есть по крайней мере два процесса q, вычисливших результат result q = N, который в этомслучае является неправильным.Вероятность появления такого семейства последовательностей 0 равна 2−2NL .Это положительная величина, и она показывает, что алгоритм A не может правильно вычислить размеры колец с вероятностью, большей чем 1 − 2 −2NL .Различие вероятностей вычисления правильных результатов алгоритмами, оканчивающими работу по завершении работы процессов и по завершении обменовсообщениями, можно объяснить так.
Алгоритм, оканчивающий вычисление позавершении работы процессов, выдает неверный результат, если где-то в кольце был совершен неудачный случайный выбор. При увеличении размеров кольцавероятность того, что это произойдет, возрастает. В алгоритме, оканчивающемработу по завершении обменов сообщениями, процессы, совершившие неудачный выбор, всегда имеют возможность оправиться от их неверного ответа засчет получения информации от других процессов.
Следовательно, алгоритм, завершающий работу неявно, выдает неверный ответ, если неудачный случайный345выбор был совершен везде в заданном кольце. И хотя этого события нельзя совсем исключить, вероятность того, что оно произойдет, ограничена, и на самомделе она убывает по мере увеличения размеров кольца.9.4.2. Алгоритм вычисления размера кольцаВ этом параграфе представлен алгоритм типа Монте-Карло, вычисляющийразмер кольца и оканчивающий работу по завершении обмена сообщениями. Какбудет показано, по окончании работы алгоритма для всех процессов p будет выполняться равенство estp = N с вероятностью, которую можно сделать скольугодно близкой к единице за счет выбора параметра R. Этот алгоритм сходенс алгоритмом, предложенным Айтаи и Роде [111] , но немного упрощен.Процесс p вычисляет локальную оценку размера кольца, est p , и при этомгарантируется, что в любой момент времени эта оценка консервативна, т.
е.,estp 6 N. Вначале estp = 2. Всякий раз, когда процесс p получет информацию, свидетельствующую о том, что оценка estp не равна размеру кольца, pувеличивает свою оценку.Чтобы быть уверенным в правильности своей оценки, процесс p порождаетмаркер и отправляет его на расстояние estp переходов по кольцу. Если оценкаоказыватся правильной, p получает обратно свой маркер, и если это происходит,p удовлетворяется результатом (временно) и не предпринимает дальнейших действий. Процесс p получает подобный маркер в случае, когда размер кольца N вдействительности превосходит оценку estp , но процесс, отстоящий от p на (estp)переходов против часовой стрелки, выработал ту же самую оценку и отправилсвой маркер.Такую ситуацию (в которой процесс p получает не принадлжащий ему маркер)можно распознать с большой вероятностью; каждый процесс выбирает случайным образом метку из множества {1, .
. . , R} и присоединяет ее к своему маркеру.Метка процесса, выбранная процессом p, остается неизменной, до тех пор покане увеличится оценка размера сети. Если процесс p получает маркер, выпущенный другим процессом, то с вероятностью 1 − 1/R присоединенная к нему меткаотличается от метки процесса p, а если процесс получает свой собственный маркер, то его метка наверняка совпадает с меткой процесса.Процесс p увеличивает локальную оцнку размера сети в двух случаях.1. Получен маркер, содержащий оцнку est, удовлетворяющую неравенству est > estp . Так как алгоритм обеспечивает консервативность всех оценок,получение такого маркера означает, что N > est p .2.
Получен маркер, содержащий оценку est = estp , причем этот маркерсовершил est переходов, но присоединенная к нему пометка отличаетсяот пометки процесса p. Этот маркер был выпущен процессом, отстоящим от pна (est) переходов против часовой стрелки, и этот процесс имеет пометку, отличную от пометки процесса p. Следовательно, (est) -й по порядку сосед процесса pотличен от самого p, а это означает, что N 6= est.Маркер, несущий оценку est < estp , изымается (т. е. его распространение прерывается); см.
алгоритм 9.5.346cons Rvar estplblpГл. 9. Анонимные сети: integer: integer;: integer;;(* Опрделяет вероятность правильного результата *)begin estp := 2 ; lblp := rand({1, . . . , R});send htest, estp , lblp , 1i to Nextp ;while true dobegin receive htest, est, lbl, hi ;if est > estp then (* Оценка процесса p должна быть увеличена*)if est = h then (* est также слишком мала *)begin estp := est + 1 ; lblp := rand({1, .
. . , R}) ;send htest, estp , lblp , 1i to Nextpendelse (* отправляет маркер далее и увеличивает estp *)begin send htest, est, lbl, h + 1i to Nextp ; estp := est ;lblp := rand({1, . . . , R}); send htest, estp , lblp , 1i to Nextpendelse if est = estp thenif h < est then send htest, est, lbl, h + 1i to Nextpelse (* Этот маркер совершил est перходов *)if lbl 6= lblp thenbegin estp := est + 1 ; lblp := rand({1, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
