Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 85
Текст из файла (страница 85)
Так, в гл. 14 будет показано, что они играют важную роль для достижения отказоустойчивости распределенных систем. Кроме того, для некоторыхзадач, разрешимых при помощи детерминированных алгоритмов, существуют вероятностные решения, имеющие меньшую сложность; однако далее эту тему мыв нашей книге обсуждать не будем.9.1. Основные понятияАнонимной сетью называется сеть, в которой невозможно различать процессы по индивидуальным отличительным признакам. Предполагается также, чтонет и заранее выделенного лидера. Следовательно, процессы, подключенные к одному и тому же числу каналов, совершенно идентичны. Энглуин в работе [8 ]324Гл. 9.
Анонимные сетипредложила использовать термин процессный ряд для бесконечной последовательности процессов Р\, Р 2 , ■.., где Pi — процесс степени / (т. е. подключен к /каналам). Для обозначения сетей, в которых все процессы одинаковы (симметричны), используется также термин симметричные системы.9.1.1. ОпределенияВ этом параграфе будет показано, как можно обобщить модель распределенных систем, введенную нами в гл. 2 , чтобы охватить алгоритмы, опирающиесяна рандомизацию. Рандомизация состоит в том, чтобы при помощи «электронного подбрасывания монеты» и генератора случайных чисел добиться случайногоповедения процесса, причем каждое из возможных случайных поведений проявляется с известной вероятностью. Рандомизацию следует отличать от недетерминизма, обусловленного как непредсказуемостью относительного быстродействияпроцессов, так и тем обстоятельством, что всякий процесс наделен возможностьюпо-разному продолжить одно и то же вычисление за счет реализации различныхсобытий.
Мы применяем программное средство, чтобы определить распределениевероятностей на совокупности вычислений системы, и благодаря этому получаемвозможность говорить о том, что свойства алгоритма соблюдаются с определенной вероятностью. Недетерминизм, присущий распределенным системам, нельзяконтролировать, и поэтому проектировщик алгоритмов должен всегда уметь совладать с наихудшим из всех вариантов выбора, возникающим в связи с неустранимым недетерминизмом.Вероятностные алгоритмы.
Модель вероятностного процесса образуется за счет того, что некоторый процесс подбрасывает монету на каждом шаге своего выполнения. Совокупность очередных возможных шагов зависит не толькоот состояния процесса, но также и от исходов подбрасывания монеты на предыдущих шагах процесса. Первый шаг процесса зависит от исхода подбрасывания,совершенного в начальном состоянии.Невероятностные процессы (или алгоритмы) обычно называют детерминированными процессами (или алгоритмами); однако этот термин не исключаетвозможности того, что сеть невероятностных процессов функционирует недетерминированно. Такого рода сети ведут себя недетерминированно в соответствиис моделью из гл.
2 , но при этом выбор обусловлен расписанием событий в вычислении, и он не поддается никакому вероятностному анализу. А вот выбор,возникающий в связи с рандомизацией, подчиняется вероятностному анализу,благодаря которому на множестве вычислений системы вводится распределение вероятностей. Чтобы сделать это распределение явным, в формальной модели предполагается, что вся последовательность подбрасываний монеты, котораяосуществляется процессом по ходу его выполнения, задана заранее до началавыполнения.Чтобы лучше понять формальное определение, мы вначале рассмотрим процессы, допускающие только внутренние события.
Вероятностный процесс задается четверкой р = (Z, /, Ь°, Ь1), где элементы множеств Z и / точно такие же,9.1. Основные понятия325как и в определении 2.4, а Ь° и Ь 1 — это бинарные отношения на Z. Процесссовершает г-й шаг согласно отношению Ь°, если исходом г-го подбрасывания монеты был ноль, и согласно отношению Ь 1 в противном случае. Рассмотрим бесконечную последовательность р = (ро, рь ...) исходов подбрасывания монеты, т. е.последовательность, состоящую из нулей и единиц. Тогда р-выполнением процесса р назовем такую максимальную последовательность состояний со, И,что Со € / и (с/, Cj+i)€ И '. Отметим, что неустранимый недетерминизм по-прежнему присутствует, поскольку заданному исходу подбрасывания монеты могутотвечать различные события. Однако никаких вероятностных допущений относительно их выбора сделать нельзя. А вот что касается вероятностного выбора,то здесь делается допущение о том, что для всякого k > О любая последовательность из k битов осуществляется в качестве префикса р с одной и той же вероятностью (а именно 2~к).
Если последовательность р задана, то вероятностныйпроцесс ведет себя так же, как и детерминированный процесс, который можнорассматривать как частный случай вероятностного процесса.Чтобы ввести обмен сообщениями между процессами, всякий процесс определяют восьмеркой, состоящей из множества состояний, множества начальныхсостояний и шести отношений событий, а именно событий отправления, событийприема и внутренних событий как для нулевого, так и для единичного исхода подбрасывания монеты.
Вероятностный распределенный алгоритм представляется в виде совокупности Р вероятностных процессов. Вместо того чтобы выписывать полное формальное определение, мы укажем здесь отличия данного определения от определения, приведенного в §2.1.2. Конфигурация вероятностногораспределенного алгоритма складывается из состояния и натурального числа длякаждого из процессов и совокупности сообщений, если в алгоритме используется асинхронный обмен сообщениями. Для каждого процесса натуральное числообозначает количество событий, осуществленных данным процессом. Переходысистемы определяются так же, как и в § 2 .
1 .2 , с той лишь разницей, что всякий переход, относящийся к процессу р, увеличивает на единицу число шагов,выполненных р.Пусть р — это приписывание последовательностей рр, состоящих из нулейи единиц, каждому процессу р. Тогда р-вычислением системы называется вычисление, в котором г-й переход, относящийся к процессу р, задается отношением событий, определяемым г'-м элементом последовательности рр. Если совокупность последовательностей р задана, то вероятностный алгоритм ведет себятак же, как и детерминированный распределенный алгоритм, который, в своюочередь, может рассматриваться как частный случай вероятностного распределенного алгоритма. Вероятностное допущение состоит в том, что для каждогоk > 0 всякая совокупность из N последовательностей длины k имеет одну и туже вероятность осуществления (а именно 2~kN) в качестве префиксов последовательностей из р.
Вследствие этого допущения мы получаем, что в каждом частном случае вероятностного алгоритма всякий процесс выполняет тот или инойлокальный алгоритм с вероятностью, равной единице.326Гл. 9. Анонимные сетиВероятностная корректность и сложность. В этой главе мы будем рассматривать задачи, критерий правильного решения которых характеризуется постусловием ф; цель алгоритма состоит в том, чтобы достичь заключительнойконфигурации, в которой выполняется ф.
Это постусловие зависит от конкретной задачи; для задачи об избрании его следует понимать как «один процесспребывает в состоянии leader а все остальные процессы — в состоянии lost»,а для задачи вычисления размера сети ф определяется требованием «для каждого процесса р значение sizep равно N». Заключительная конфигурация можетбыть либо завершенной по признаку окончания приема сообщений (все процессыожидают поступления какого-нибудь сообщения), либо завершенной по признакуокончания работы процессов (все процессы пребывают в заключительном состоянии).Корректность детерминированных алгоритмов задается так, как это было определено в §2.5.2.
Детерминированный алгоритм завершается, если каждое вычисление достигает заключительной конфигурации. Детерминированный алгоритмсчитается частично корректным (относительно предусловия ф), если каждаязаключительная конфигурация данного алгоритма удовлетворяет ф. Детереминированный алгоритм называется корректным, если он завершается и являетсячастично корректным.Для вероятностных алгоритмов корректность определяется на основании анализа частных случаев алгоритма, полученных при уточнении приписывания последовательностей р. Вероятностный алгоритм называется р-завершающимся,если каждое p-вычисление достигает заключительной конфигурации. Вероятностный алгоритм считается р-частично корректным (относительно предусловия ф), если каждая заключительная конфигурация всякого p-вычисления удовлетворяет предусловию ф.
Вероятностный алгоритм называется р- корректным,если он является р-завершающимся и p-частично корректным.Вероятностный алгоритм считается завершающимся, если он является рзавершающимся для каждого приписывания последовательностей р. Вероятностный алгоритм называется частично корректным, если он является р-частичнокорректным для каждого р. Вероятностный алгоритм называется корректным,если он является и р-корректным для каждого р.Вероятностный алгоритм завершается с вероятностью Р, если вероятность того, что алгоритм является р-завершающимся, не меньше Р. Вероятностный алгоритм является частично корректным с вероятностью Р, если вероятность того, что алгоритм является p-частично корректным, не меньше Р.Вероятностный алгоритм является корректным с вероятностью Р, если вероятность того, что алгоритм является р-корректным, не меньше Р.Завершаемость (равно как частичная корректность или корректность) не равносильна завершаемости (соответственно частичной корректности или корректности) с вероятностью единица.
Вероятностный алгоритм может давать неверныйрезультат для непустого множества приписываний р, но при этом вероятностьтого, что приписывание р принадлежит этому множеству, равна нулю.Определим р-сложность по числу обменов сообщениями вероятностного алгоритма как наибольшее число обменов сообщениями, которое возможно9.1. Основные понятия327в р-вычислении. С л о ж н о с т ь в с р е д н е м п о ч и с л у о б м е н о в с о о б щ е н и я м и вероятностного алгоритма — это математическое ожидание p-сложности по числуобменов сообщениями. Аналогично определяются сложность вероятностных алгоритмов по времени и по числу битов.Обоснование отрицательных результатов. В этой главе будет доказан рядотрицательных результатов, т.
е. утверждений о том, что не существует алгоритмов, которые могли бы достичь тех или иных постусловий. Для детерминированных алгоритмов доказательство утверждений такого рода обычно построитьпроще; достаточно привести пример единственного вычисления, которое не завершается конфигурацией, удовлетворяющей постусловию ф. Типичный примердоказательства такого рода представлен для теоремы 9.5.Построение единственного бесконечного вычисления не опровергает существования нужного вероятностного алгоритма; такой алгоритм может иметь бесконечно много вычислений и при этом завершаться с вероятностью, равной единице. Чтобы доказать, что вероятностное решение невозможно, можно показать,как построить некорректное решение исходя из предполагаемого корректного вычисления, имеющего другую начальную конфигурацию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
