Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 90
Текст из файла (страница 90)
В первом случае маркер возвращается с пометкой un = true и процесс р избирается лидером. Во втором случае, маркер возвращается с пометкойun = false и в (/ + 1 )-м туре будет порожден какой-нибудь маркер.□Теорема 9.11. Алгоритм Айтаи—Роде (алгоритм 9.4) является частично корректным алгоритмом избрания лидера для колец заранее неизвестного размера, завершающим работу с вероятностью, равной единице.Д о к а з а т е л ь с т в о . Частичная корректность алгоритма, означающая, чтов случае завершения работы остается в точности один лидер, доказывается с использованием леммы 9.10.
Предположим, что I — это номер наивысшего тура,в котором вырабатывался маркер; величина I определена, поскольку по предположению рассматривается конечное вычисление. Тот факт, что ни один процессне был избран в младших турах и ни один маркер не был порожден в (I + 1 )-мтуре, означает, что в l-м туре в точности один процесс был избран лидером.Остается показать, что алгоритм завершает работу с вероятностью, равнойединице.
Если в некотором туре I имеются k > 1 процессов, которые выработалимаркеры в туре I, то существует вероятность /Д > 0 того, что в этом туре в точности одному процессу достанется минимальный отличительный признак, и тогдаалгоритм завершит работу.
Обозначим символом Р наименьшее значение Pk повсем k\ теперь если маркеры были выработаны в l-м туре, то вероятность того,что маркеры будут порождены также и в (/ + 1 )-м туре, не превосходит величи-342Гл. 9. Анонимные сетины 1 —Р. Следовательно, вероятность того, что алгоритм не завершит работупосле / туров, ограничена сверху величиной (1 —Р)1, которая стремится к нулю,если устремить / к бесконечности.□Вероятностный анализ (проведенный в работе [111]) позволил выяснить, чтоожидаемое число туров ограничено величиной eN(N—1). Ожидаемое число сообщений, отправленных в одном туре, ограничено величиной 0(N log N) (это можноустановить, рассуждая подобно тому, как это делалось в теореме 7.6), и отсюда следует, что ожидаемая сложность алгоритма по числу обменов ссобщениямисоставляет величину 0(NlogN).Произвольные сети.
Воспользовавшись почти теми же самыми идеями, можно построить алгоритм проведения выборов в произвольных сетях. В основу этогоалгоритма положен алгоритм 7.9, а не алгоритм Ченя—Робертса. Процесс «одерживает победу» в очередном туре этого алгоритма, если он инициировал алгоритмэха и все соседние процессы откликнулись эхом. Как и в алгоритме Айтаи—Роде,этого условия еще не достаточно, чтобы стать лидером, так как может оказаться,что выборы были затеяны несколькими процессами с одинаковыми отличительными признаками. Чтобы обнаружить это, размер дерева, построенного алгоритмом эха, вычисляется так, как это делается в алгоритме 9.1. Если есть несколькоинициаторов с одинаковыми отличительными признаками, то каждый вызов эхаприводит к построению дерева, в котором содержится только часть процессов.Когда процесс завершает выполнение алгоритма эха (получив отклик от каждого из соседей), ему становится известен размер дерева, которое при этом былопостроено.
Если этот размер равен N, то процесс становится лидером, а иначеалгоритм эха запускается в следующем туре.Полученный в результате алгоритм является частично корректным, и его работа завершается с вероятностью, равной единице. Полное описание этого алгоритма можно найти в статье [190]. Другие алгоритмы проведения выборов можноотыскать в работах [171] и [140].9.4. Вычисление размера сетиРазнообразные результаты, представленные в этой главе, свидетельствуюто том, насколько важно знание размера сети.
В этом параграфе мы рассмотримзадачу вычисления размера сети. Размер кольца может быть вычислен только припомощи алгоритма, оканчивающего работу по завершении обмена сообщениями,и при этом вероятность неправильного ответа будет отлична от нуля.9.4.1. Отрицательные результатыВ этот параграф включены два результата, касающиеся невозможности вычисления размера кольца. Обоснование этих результатов опирается на ту жеидею, которая использовалась для доказательства теоремы 9.8, а именно на идеюо возможности повторения заданного (предположительно правильного) вычисления в различных частях большого кольца. Для вероятностных алгоритмов, как9.4.
Вычисление размера сети343будет показано, вероятность такого повторения отлична от нуля, и это следует изтого, что при выполнении конечных вычислений всякий процесс использует лишьконечный префикс последовательности случайных битов.Теорема 9.12. Не существует алгоритма , оканчивающего вычисленияпо завершении работы процессов и правильно вычисляющего размер кольца с вероятностью г > 0 .Д о к а з а т е л ь с т в о . Предположим, что есть вероятностный алгоритм А,проводящий p-вычисление Сдг на кольце размера N, и в вычислении Сдг каждыйпроцесс р завершает работу с результатом resultp = N. Выберем произвольныйпроцесс р и предположим, что самая длинная трасса сообщения, полученногоэтим процессом р в вычислении Сдг, имеет длину К.
В вычислении Сдг каждыйпроцесс выполняет только конечное число шагов; обозначим символом L наибольшее число шагов, выполняемых всяким процессом в вычислении Сдг.Рассмотрим кольцо большего размера, в котором содержится сегмент из К + 1процессов. Обозначим символом ро последний процесс этого сегмента, а символом pi — i -й по порядку процесс сегмента, отстоящий от ро против хода часовой стрелки. Рассмотрим набор двоичных последовательностей р', приписанныхпроцессам этого кольца и обладающих следующим свойством.
Первые L битовпоследовательности р'ро точно те же, что и первые L битов последовательности.Первые L битов последовательности р'р., где / ^ К, точно те же, что и первые Lбитов последовательности рч, где q — это /-й по порядку процесс, отстоящий от рпротив часовой стрелки в кольце размера N. Если длина сегмента К + 1 задана,то вероятность появления такого набора последовательностей очень мала, онаравна 2 _ ^+ P l .Существует р'-вычисление С алгоритма А на кольце большого размера, в ходе которого процесс pi отправляет в точности те же сообщения, имеющие трассыдлины не больше ^ К + 1 —г, что и г-й по порядку процесс, отстоящий противчасовой стрелки от процесса р в малом кольце, в ходе вычисления Сдт.
Это доказывается точно так же, как делалось при обосновании теоремы 9.8. Как видно изпостроения, для всякого заданного сегмента длины К+ 1 процессы этого сегмента с вероятностью, не меньшейповторят вычисление Сц, в результатечего процесс ро завершит работу с результатом result Ро = N, а этот результатневерен.Вероятность того, что это произойдет на некотором заданном сегменте, чрезвычайно мала, но, выбрав кольцо достаточно большого размера, мы можем добиться того, что вероятность осуществления этого события в каком-либо сегменте кольца станет сколь угодно большой. Пусть задана вероятность г > 0. Возьмемтакое натуральное число R, чтобы выполнялось неравенство (1 —2 _ ^ +1^ )^ < г,и рассмотрим кольцо размера ЩК+ 1).
В этом кольце есть R непересекаюгцихсясегментов длины К + 1 , и для каждого из этих сегментов вероятность того, чтопоследний процесс не может завершить вычисление с неправильным ответом, непревосходит 1 —2 ~ ^ + 1)L. Тогда вероятность того, что ни один из процессов незавершит вычисление с неправильным ответом, будет меньше г.□344Гл. 9.
Анонимные сетиНа самом деле, применяя те же самые рассуждения, можно установить, чтоникакую функцию, отличную от константы, нельзя правильно вычислить с вероятностью г > 0 при помощи алгоритма, оканчивающего работу по завершенииобмена сообщениями. А вот другой результат того же рода нельзя обобщить наслучай произвольной функции, отличной от константы.
Утверждается, что не существует алгоритмов типа Лас-Вегас, оканчивающих работу по завершении обмена сообщениями, и поэтому самое большее, на что можно рассчитывать, — этопостроение алгоритмов типа Монте-Карло, оканчивающих работу по завершенииобмена сообщениями.Теорема 9.13. Не существует алгоритмов, оканчивающих работу позавершении обмена сообщениями и вычисляющих размер кольца с вероятностью, равной единице.Д о к а з а т е л ь с т в о . Предположим, что есть вероятностный алгоритм А,имеющий p-вычисление См на кольце размера N, который оканчивает работупо завершении обмена сообщениями с результатом resultp = N для некоторогопроцесса р. Каждый процесс совершает только конечное число шагов по ходувычисления См- Обозначим символом L наибольшее число шагов, которое совершает всякий процесс в вычислении См- Занумеруем процессы в кольце размераN натуральными числами от 0 до N — 1.Рассмотрим теперь кольцо размера 2N, в котором все процессы занумерованы натуральными числами, начиная с 0 и оканчивая 2 N — 1 , а также такоесемейство р' двоичных последовательностей, что для каждого / < N первые Lбитов последовательностей p'q.
и p'qi+N, приписанных процессам qt и qi+M большого кольца, в точности повторяют первые L битов последовательности pPi, приписанной процессу pi малого кольца. Устройство р'-вычисления алгоритма А накольце размера 2N таково. Каждый шаг процесса pi в вычислении См повторяется параллельно процессом qi и его антиподом qt+м- Поскольку последняяконфигурация вычисления См является заключительной, таковой же является изпоследняя конфигурация вычисления C2 N, и в этой конфигурации есть по крайней мере два процесса q, вычисливших результат resultq = N, который в этомслучае является неправильным.Вероятность появления такого семейства последовательностей р' равна 2~2NL.Это положительная величина, и она показывает, что алгоритм А не может правильно вычислить размеры колец с вероятностью, большей чем 1 —2~2NL.□Различие вероятностей вычисления правильных результатов алгоритмами, оканчивающими работу по завершении работы процессов и по завершении обменовсообщениями, можно объяснить так.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
