Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 86
Текст из файла (страница 86)
Вероятностный распределенный алгоритм представляется в виде совокупности P вероятностных процессов. Вместо того чтобы выписывать полное формальное определение, мы укажем здесь отличия данного определения от определения, приведенного в § 2.1.2. Конфигурация вероятностногораспределенного алгоритма складывается из состояния и натурального числа длякаждого из процессов и совокупности сообщений, если в алгоритме используется асинхронный обмен сообщениями. Для каждого процесса натуральное числообозначает количество событий, осуществленных данным процессом. Переходысистемы определяются так же, как и в § 2.1.2, с той лишь разницей, что всякий переход, относящийся к процессу p, увеличивает на единицу число шагов,выполненных p.Пусть — это приписывание последовательностей p , состоящих из нулейи единиц, каждому процессу p.
Тогда -вычислением системы называется вычисление, в котором i-й переход, относящийся к процессу p, задается отношением событий, определяемым i-м элементом последовательности p . Если совокупность последовательностей задана, то вероятностный алгоритм ведет себятак же, как и детерминированный распределенный алгоритм, который, в своюочередь, может рассматриваться как частный случай вероятностного распределенного алгоритма. Вероятностное допущение состоит в том, что для каждогоk > 0 всякая совокупность из N последовательностей длины k имеет одну и туже вероятность осуществления (а именно 2−kN) в качестве префиксов последовательностей из . Вследствие этого допущения мы получаем, что в каждом частном случае вероятностного алгоритма всякий процесс выполняет тот или инойлокальный алгоритм с вероятностью, равной единице.предложила использовать термин процессный ряд для бесконечной последовательности процессов P1 , P2 , .
. ., где Pi — процесс степени i (т. е. подключен к iканалам). Для обозначения сетей, в которых все процессы одинаковы (симметричны), используется также термин симметричные системы.9.1. Основные понятия324Гл. 9. Анонимные сети9.1. Основные понятияОбоснование отрицательных результатов. В этой главе будет доказан рядотрицательных результатов, т. е. утверждений о том, что не существует алгоритмов, которые могли бы достичь тех или иных постусловий. Для детерминированных алгоритмов доказательство утверждений такого рода обычно построитьпроще; достаточно привести пример единственного вычисления, которое не завершается конфигурацией, удовлетворяющей постусловию . Типичный примердоказательства такого рода представлен для теоремы 9.5.Построение единственного бесконечного вычисления не опровергает существования нужного вероятностного алгоритма; такой алгоритм может иметь бесконечно много вычислений и при этом завершаться с вероятностью, равной единице.
Чтобы доказать, что вероятностное решение невозможно, можно показать,как построить некорректное решение исходя из предполагаемого корректного вычисления, имеющего другую начальную конфигурацию. Примеры доказательстватакого рода представлены в теоремах 9.12 и 9.13.9.1.2. Классификация вероятностных алгоритмовАлгоритмы типа Шервуд. Корректные вероятностные алгоритмы называются алгоритмами типа Шервуд (см. [36]). Если нас интересует только разрешимость задачи (а не сложность ее решения), алгоритмы типа Шервуд представляютнезначительный интерес, поскольку справедливо следующее утверждение.Теорема 9.1.
Если существует корректный вероятностный алгоритм,в котором достигается постусловие , то существует и корректныйнедетерминированный алгоритм, в котором достигается постусловие .Д о к а з а т е л ь с т в о. Предположим, что PA — корректный вероятностный алгоритм. Алгоритм PA является -корректным для каждого и, в частности, для такого , в котором каждому процессу приписывается последовательность, состоящая из одних нулей; обозначим такое приписывание символом (0) .Рассмотрим алгоритм DA, который действует так же, как действует PA в томслучае, когда исход всякого подбрасывания монеты равен нулю (т. е.
всякое обращение к случайному биту заменяется в программе числом 0). Такой алгоритмявляется детерминированным, и при этом он остается корректным, поскольку PAявляется (0) -корректным.Вероятностные алгоритмы в зависимости от гарантируемой степени корректности подразделяются на следующие типы: алгоритмы типа Лас-Вегас, алгоритмы типа Монте-Карло и алгоритмы типа Шервуд. Вероятностные алгоритмы могут быть корректными (т.
е., частично корректными и завершающимися),или только корректными с определенной вероятностью, как это было определенов § 9.1.1.в -вычислении. Сложность в среднем по числу обменов сообщениями вероятностного алгоритма — это математическое ожидание -сложности по числуобменов сообщениями. Аналогично определяются сложность вероятностных алгоритмов по времени и по числу битов.Вероятностная корректность и сложность. В этой главе мы будем рассматривать задачи, критерий правильного решения которых характеризуется постусловием ; цель алгоритма состоит в том, чтобы достичь заключительнойконфигурации, в которой выполняется . Это постусловие зависит от конкретной задачи; для задачи об избрании его следует понимать как «один процесспребывает в состоянии leader а все остальные процессы — в состоянии lost»,а для задачи вычисления размера сети определяется требованием «для каждого процесса p значение sizep равно N». Заключительная конфигурация можетбыть либо завершенной по признаку окончания приема сообщений (все процессыожидают поступления какого-нибудь сообщения), либо завершенной по признакуокончания работы процессов (все процессы пребывают в заключительном состоянии).Корректность детерминированных алгоритмов задается так, как это было определено в § 2.5.2.
Детерминированный алгоритм завершается, если каждое вычисление достигает заключительной конфигурации. Детерминированный алгоритмсчитается частично корректным (относительно предусловия ), если каждаязаключительная конфигурация данного алгоритма удовлетворяет . Детереминированный алгоритм называется корректным, если он завершается и являетсячастично корректным.Для вероятностных алгоритмов корректность определяется на основании анализа частных случаев алгоритма, полученных при уточнении приписывания последовательностей . Вероятностный алгоритм называется -завершающимся,если каждое -вычисление достигает заключительной конфигурации.
Вероятностный алгоритм считается -частично корректным (относительно предусловия ), если каждая заключительная конфигурация всякого -вычисления удовлетворяет предусловию . Вероятностный алгоритм называется -корректным,если он является -завершающимся и -частично корректным.Вероятностный алгоритм считается завершающимся, если он является завершающимся для каждого приписывания последовательностей . Вероятностный алгоритм называется частично корректным, если он является -частичнокорректным для каждого .
Вероятностный алгоритм называется корректным,если он является и -корректным для каждого .Вероятностный алгоритм завершается с вероятностью P, если вероятность того, что алгоритм является -завершающимся, не меньше P. Вероятностный алгоритм является частично корректным с вероятностью P, если вероятность того, что алгоритм является -частично корректным, не меньше P.Вероятностный алгоритм является корректным с вероятностью P, если вероятность того, что алгоритм является -корректным, не меньше P.Завершаемость (равно как частичная корректность или корректность) не равносильна завершаемости (соответственно частичной корректности или корректности) с вероятностью единица.
Вероятностный алгоритм может давать неверныйрезультат для непустого множества приписываний , но при этом вероятностьтого, что приписывание принадлежит этому множеству, равна нулю.Определим -сложность по числу обменов сообщениями вероятностного алгоритма как наибольшее число обменов сообщениями, которое возможно327326328Гл. 9. Анонимные сетиИз этого результата не следует, что алгоритмы типа Шервуд бесполезны; ихсложность в среднем может свидетельствовать об их преимуществе по сравнению со сложностью (в худшем случае) наилучших детерминированных алгоритмов.
Рассморим в качестве примера алгоритм избрания Ченя —Робертса (алгоритм 7.3), который в худшем случае имеет сложность по числу сообщений,составляющую величину Θ (N 2), но при этом его сложность в среднем оценивается величиной Θ (N log N). В рандомизованном варианте этого алгоритма каждыйпроцесс дополняет свое имя случайно выбранной битовой строкой; эта случайновыбранная часть наиболее существенна для проведения сравнений. Независимоот распределения исходных отличительных признаков, математическое ожиданиесложности модифицированного алгоритма равно сложности в среднем исходногоалгоритма, т. е.
составляет Θ (N log N) сообщений.В этой книге мы не будем касаться алгоритмов типа Шервуд.Алгоритмы типа Лас-Вегас и Монте-Карло. Как следует из теоремы 9.1,самое большее, чего можно достичь при решении задачи, для которой не существует детерминированного решения, — это построить вероятностный алгоритм,который будет корректен с вероятностью P (0 6 P 6 1).
Обычно каждое вычисление удовлетворяет либо требованию завершаемости, либо требованию частичной корректности.Определение 9.2. Алгоритмом типа Лас-Вегас называется вероятностныйалгоритм, который1) завершается с положительной вероятностью и при этом2) является частично корректным.Алгоритмом типа Монте-Карло называется вероятностный алгоритм, который1) завершается и при этом2) является частично корректным с положительной вероятностью.Вероятность завершения алгоритма типа Лас-Вегас чаще всего равна единице; бесконечные вычисления действительно возможны, но они случаются толькотогда, когда неудачный набор случайных битов выбирается бесконечно часто. Напрактике это означает, что алгоритмы типа Лас-Вегас всегда завершаются, хотяпри этом можно оценить лишь среднее число совершенных шагов, но нельзяуказать верхней оценки числа шагов алгоритма.
Примером алгоритма типа ЛасВегас служит алгоритм избрания Айтаи и Роде (алгоритм 9.4).Вероятность вычисления неверного результата алгоритмом Монте-Карло (еслитолько это не алгоритм типа Шервуд) обычно меньше единицы. В конечном ошибочном вычислении используется лишь конечное число случайных битов, и поэтому вероятность такого вычисления положительна. Обычно удается установитьверхнюю оценку числа шагов, совершаемых алгоритмом типа Монте-Карло. Примером алгоритма типа Монте-Карло служит алгоритм Айтаи и Роде вычисленияразмеров кольца (алгоритм 9.5).9.1. Основные понятия329При некоторых дополнительных ограничениях на основе алгоритма типа ЛасВегас можно построить алгоритм типа Монте-Карло и наоборот; см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
