Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 86
Текст из файла (страница 86)
Примеры доказательстватакого рода представлены в теоремах 9.12 и 9.13.9.1.2. Классификация вероятностных алгоритмовВероятностные алгоритмы в зависимости от гарантируемой степени корректности подразделяются на следующие типы: алгоритмы типа Л а с - В е г а с , алгоритмы типа М о н т е - К а р л о и алгоритмы типа Ш е р в у д . Вероятностные алгоритмы могут быть корректными (т. е., частично корректными и завершающимися),или только корректными с определенной вероятностью, как это было определенов §9.1.1.Алгоритмы типа Шервуд. Корректные вероятностные алгоритмы называются а л г о р и т м а м и т и п а Ш е р в у д (см. [36]). Если нас интересует только разрешимость задачи (а не сложность ее решения), алгоритмы типа Шервуд представляютнезначительный интерес, поскольку справедливо следующее утверждение.Теорема 9.1.
Е с л и с у щ е с т в у е т к о р р е к т н ы й в е р о я т н о с т н ы й а л г о р и т м ,в к о т о р о м д о с т и г а е т с я п о с т у с л о в и е ф, т о с у щ е с т в у е т и к о р р е к т н ы йн е д е т е р м и н и р о в а н н ы й а л г о р и т м , в к о т о р о м д о с т и г а е т с я п о с т у с л о в и е ф.Д о к а з а т е л ь с т в о .
Предположим, что Р А — корректный вероятностный алгоритм. Алгоритм Р А является р-корректным для к а ж д о г о р и, в частности, для такого р, в котором каждому процессу приписывается последовательность, состоящая из одних нулей; обозначим такое приписывание символом р<0).Рассмотрим алгоритм D A , который действует так же, как действует Р А в томслучае, когда исход всякого подбрасывания монеты равен нулю (т. е. всякое обращение к случайному биту заменяется в программе числом 0). Такой алгоритмявляется детерминированным, и при этом он остается корректным, поскольку Р Аявляется р(0 )-корректным.□Гл. 9. Анонимные сети328Из этого результата не следует, что алгоритмы типа Шервуд бесполезны; ихсложность в среднем может свидетельствовать об их преимуществе по сравнению со сложностью (в худшем случае) наилучших детерминированных алгоритмов.
Рассморим в качестве примера алгоритм избрания Ченя—Робертса (алгоритм 7.3), который в худшем случае имеет сложность по числу сообщений,составляющую величину 0 (Л/2), но при этом его сложность в среднем оценивается величиной Q(N logN). В рандомизованном варианте этого алгоритма каждыйпроцесс дополняет свое имя случайно выбранной битовой строкой; эта случайновыбранная часть наиболее существенна для проведения сравнений. Независимоот распределения исходных отличительных признаков, математическое ожиданиесложности модифицированного алгоритма равно сложности в среднем исходногоалгоритма, т. е.
составляет 0(A4ogiV) сообщений.В этой книге мы не будем касаться алгоритмов типа Шервуд.Алгоритмы типа Лас-Вегас и Монте-Карло. Как следует из теоремы 9.1,самое большее, чего можно достичь при решении задачи, для которой не существует детерминированного решения, — это построить вероятностный алгоритм,который будет корректен с вероятностью Р (0 ^ Р ^ 1). Обычно каждое вычисление удовлетворяет либо требованию завершаемости, либо требованию частичной корректности.Определение 9.2. Алгоритмом типа Лас-Вегас называется вероятностныйалгоритм, который1 ) завершается с положительной вероятностью и при этом2 ) является частично корректным.Алгоритмом типа Монте-Карло называется вероятностный алгоритм, который12) завершается и при этом) является частично корректным с положительной вероятностью.Вероятность завершения алгоритма типа Лас-Вегас чаще всего равна единице; бесконечные вычисления действительно возможны, но они случаются толькотогда, когда неудачный набор случайных битов выбирается бесконечно часто.
Напрактике это означает, что алгоритмы типа Лас-Вегас всегда завершаются, хотяпри этом можно оценить лишь среднее число совершенных шагов, но нельзяуказать верхней оценки числа шагов алгоритма. Примером алгоритма типа ЛасВегас служит алгоритм избрания Айтаи и Роде (алгоритм 9.4).Вероятность вычисления неверного результата алгоритмом Монте-Карло (еслитолько это не алгоритм типа Шервуд) обычно меньше единицы. В конечном ошибочном вычислении используется лишь конечное число случайных битов, и поэтому вероятность такого вычисления положительна.
Обычно удается установитьверхнюю оценку числа шагов, совершаемых алгоритмом типа Монте-Карло. Примером алгоритма типа Монте-Карло служит алгоритм Айтаи и Роде вычисленияразмеров кольца (алгоритм 9.5).9.1. Основные понятия329При некоторых дополнительных ограничениях на основе алгоритма типа ЛасВегас можно построить алгоритм типа Монте-Карло и наоборот; см. упражнения 9.1 и 9.2.Свод характеристик и параметров.
В этой главе все алгоритмы можноклассифицировать согласно следующим четырем критериям; мы коротко отметим, алгоритмы какого типа представляются более привлекательными.1. И з в е с т н ы й и л и н е и з в е с т н ы й р а з м е р с е т и . Алгоритмы, не опирающиеся на осведомленность о числе N, более предпочтительны, поскольку они являются более общими.2. З а в е р ш е н и е п о п р и е м у с о о б щ е н и й и л и п о р а б о т е п р о ц е с с о в . Алгоритмы, завершающиеся по признаку окончания работы процессов, более предпочтительны, поскольку их завершение явно выражено и процессы могут использоватьвычисленный результат.3. Д е т е р м и н и р о в а н н ы й и л и в е р о я т н о с т н ы й .
Детерминированные алгоритмы более предпочтительны, поскольку в них не используется генератор случайных чисел и, кроме того, свойства корректности, которым удовлетворяют такие алгоритмы, являются более сильными, нежели те, которым удовлетворяюталгоритмы типа Лас-Вегас и Монте-Карло.4. Т ип Л а с - В е г а с и л и М о н т е - К а р л о . Алгоритмы типа Лас-Вегас обычно представляются более привлекательными, поскольку завершение с некоторойвероятностью этих алгоритмов в практических ситуациях почти не отличимо отобычного завершения.9.1.3.
Задачи, рассматриваемые в этой главеНаша цель состоит не в том, чтобы дать полное изложение теории вычислений на анонимных сетях, включая многочисленные результаты, которые былиполучены для этих сетей. Мы хотим лишь исследовать вычислительные возможности указанных сетей применительно к задачам избрания и вычисления функций,включая вычисление размера сети.Эти задачи относятся к числу фундаментальных. Если можно избрать лидера, анонимная сеть будет обладать точно такими же вычислительными возможностями, как и сеть с именами, поскольку процессы можно именовать припомощи централизованного алгоритма, как это показано далее. В §9.5.3 будетпоказано, что лидер может быть избран при помощи вероятностного алгоритма,если известен размер сети, и это указывает на важность задачи о вычисленииразмера сети.
Так как размер сети может быть легко вычислен централизованным алгоритмом (как это будет показано далее), задачи избрания и вычисленияразмера сети эквивалентны. Будет показано, что размер сети нельзя вычислитьвероятностно, а задача о выборах неразрешима, если размер сети неизвестен.Централизованные вычисления. Размер сети может быть легко вычисленпри помощи одного-единственного вычисления алгоритма эха, если в распоряжении имеется единственный стартовый процесс ( le a d e r ) . Каждое сообщение,Гл.
9. Анонимные сети330отправляемое назад по остовному дереву, несет информацию о числе процессовв поддереве, корнем которого является процесс-отправитель; см. алгоритм 9.1.in teg e r init 0 ; (* Счетчик числа полученных сообщений *)init u d e f ;in teg e r init 1 ; (* Размер поддерева с корнем р *)var recpРfa th e rpsizepДля инициатора:b egin fо rail q € N e i g h p do send (tok, 0) to q ;w h ile recp < i f N e ig h p dob egin receive (tok, s) ; recp := recp + 1 ;s i z e p ■= s i z e p + sen d(* Размер сети равен s i z e p *)endДля неинициаторов:b egin receive (tok, s) from neighbor q ; f a t h e r p := q ; recp := recp + 1 ;to rail r e N e i g h p , г Ф f a t h e r p do send (tok, 0) to r ;w h ile recp < f f N e i g h p dob egin receive (tok, s) ; recp := recp + 1 ;s i z e p := s i z e p + send;send (tok, s i z e P) to fa t h e r ,,endАлгоритм 9.1.
Централизованное вычисление размера сетиЧтобы назначить процессам уникальные имена, сначала вычисляется размерсети при помощи алгоритма 9.1, после чего отрезок натурального ряда {0, . . . , N —разделяется между процессами и каждое поддерево получает свой отрезок, длинакоторого соответствует его размеру.Теорема 9.3. С у щ е с т в у е т д е т е р м и н и р о в а н н ы й ц е н т р а л и з о в а н н ы й а л г о р и т м в ы ч и с л е н и я р а з м е р а с е т и , к о т о р ы й т р е б у е т 2 \Е \ о б м е н о в с о о б щ е н и я м и и им еет слож ност ь п о вр ем ен и , со ст а вля ю щ ую в е л и ч и н у 0 (N ).
С ущ ест вует дет ер м и ни р о ва нн ы й ц ен т р а ли зо ва н н ы й алгорит м н а зн а ч е н и яу н и к а л ь н ы х и м е н п р о ц е с с а м с е т и , к о т о р ы й т р е б у е т 2\Е \ + ( N — 1) о б м е н о в сообщ ен и ям и и и м еет слож ност ь п о вр ем ен и , со ст а вля ю щ ую в е л и ч и н у0 (N ).Существует и более эффективный алгоритм назначения имен; см. упражнение 9.3. Как следует из теоремы 9.3, доступность лидера может со сравнительнонебольшими издержками компенсировать отсутствие уникальных имен. Поэтомупри изучении анонимных сетей предполагается, что наряду с отсутствием именв сети нет и лидера.9.2.
Детерминированные алгоритмы3319.1.4. Синхронный и асинхронный обмен сообщениями.Результаты, связанные с выборами лидера на анонимных кликах, оказываются существенно зависящими от того, какого типа взаимосвязь проводится —с синхронным или асинхронным обменом сообщениями. При синхронном обменесообщениями два процесса совместно участвуют в осуществлении единого перехода системы, и при этом симметрия между этими двумя процессами может бытьразрушена.Теорема 9.4. Для сети, состоящей из двух процессов, взаимодействующих путем синхронного обмена сообщениями, существует детерминированный алгоритм избрания лидера, завершающийся по признаку окончания работы процессов.Д о к а з а т е л ь с т в о .
Каждый процесс имеет три состояния, а именно sleep,leader, и lost, причем начальным состоянием является sleep. Каждый процессможет либо отправить сообщение и перейти в заключительное состояние leader,либо принять сообщение и перейти в заключительное состояние lost.В соответствии с этим система имеет девять конфигураций, из которых лишьтри являются достижимыми; из начальной конфигурации (sleep, sleep) системаможет перейти в конфигурации (leader, lost) и (lost, leader). В каждой из этихдвух конфигураций процессы завершили работу, и при этом в точности один изних пребывает в состоянии leader, в то время как другой пребывает в состоянииlost.□Этот алгоритм позаимствован из работы Энглуин [8 ]; она также обобщила данный алгоритм для случая клик произвольного размера.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
