Быстрый поиск

Реферат: Распределенные алгоритмы

Фундаментальная работа о задачах решения, которые являются разрешимыми и неразрешимыми при наличии одного сбойного процессора, была выполнена Бираном, Мораном и Заксом [BMZ90]. Они дали полную комбинаторную характеристику разрешимых задач решения.

13.4 Вероятностные Алгоритмы Согласия

В доказательстве Теоремы 13.8 показано, что каждый асинхронный алгоритм согласия имеет бесконечные выполнения, в которых никакое решение не принимается. К счастью, для хорошо подобранных алгоритмов такие выполнения могут быть достаточно редки и иметь вероятность 0, что делает алгоритмы очень полезными в вероятностном смысле; см. Главу 9. В этом разделе мы представляем два вероятностных алгоритма согласия, один для модели аварий, другой для Византийской модели; алгоритмы были предложены Брахой и Туэгом [BT85]. В обоих случаях сначала доказывается верхний предел для способности восстановления (t < N/2 и t < N/3, соответственно) и что и оба алгоритма удовлетворяют соответствующей границе.

В требованиях правильности для этих вероятностных алгоритмов согласия, требование завершения сделано вероятностным, то есть, заменено более слабым требованием сходимости.

(1) Сходимость. Для каждой начальной конфигурации,

[корректный процесс не принял решение после k шагов] = 0.

Частичная правильность (Соглашение) должна удовлетворяться при каждом выполнении; возникающие в результате вероятностные алгоритмы имеют класс Las Vegas (Подраздел 9.1.2).

Вероятность принимается всеми выполнениями, начинающимися в данной начальной конфигурации. Чтобы вероятности были значимыми, должно быть задано распределение вероятности над этими выполнениями. Это можно сделать использованием рандомизации в процессах (как в Главе 9), но здесь вместо этого определяется распределение вероятности на прибытиях сообщений.

Распределение вероятности на выполнениях, начинающихся в данной начальной конфигурации, определяется предположением о законном планировании. Оба алгоритма функционируют в раундах; в раунде процесс “выкрикивает” сообщение и ждет получения N-t сообщений. Определим R(q, p, k) как событие, когда в раунде k процесс p получает (раунд-k) сообщение q среди первых N-t сообщений. Законное планирование означает, что

(1) .

(2) Для всех k и различных процессов p, q, r, события R(q, p, k) и R(q, r, k) независимы.

Заметьте, что Утверждение 13.4 также выполняется для вероятностных алгоритмов, когда требуется сходимость (завершение с вероятностью один). Действительно, так как достижимая конфигурация достигается с положительной вероятностью, решенная конфигурация должна быть достижима из каждой достижимой конфигурации (хотя не обязательно достигаемой в каждом выполнении).

13.4.1 Аварийно-устойчивые Протоколы Согласия

В этом подразделе изучается проблема согласия в модели аварийного отказа. Сначала доказывается верхняя граница t < N/2 способности восстановления, потом приводится алгоритм со способностью восстановления t < N/2.

Теорема 13.16 t-аварийно-устойчивого протокола согласия для не существует.

Доказательство. Существование такого протокола, допустим P, подразумевает следующий три требования.

Требование 13.17 P имеет бивалентную начальную конфигурацию.

Доказательство. Аналогично доказательству Леммы 13.6; детали оставлены читателю. o

Для подмножества процессов S, конфигурация называется S-валентной, если и 0- и 1-решенные конфигурации достижимы из с помощью только шагов в S. называется S-0-валентной если, делая шаги только в S, 0-решенная конфигурация, и никакая 1-решенная конфигурации, может быть достигнута, S-1-валентная конфигурация определяется аналогично.

Разделим процессы на две группы, S и T, размера и .

Требование 13.18 Достижимая конфигурация является или S-0-валентной и T-0-валентной, или S-1-валентной и T-1-валентной.

Доказательство. Действительно, высокая способность восстановления протокола подразумевает, что и S и T могут достигать решения независимо; если возможны различные решения, можно достичь противоречивой конфигурации, объединяя планы. o

Требование 13.19 P не имеет достижимой бивалентной конфигурации.

Доказательство. Пусть дана достижимая бивалентная конфигурация и предположим, что это S-l-валентна и T-1-валентна (используем Требование 13.18). Однако, бивалентна, поэтому (ясно из связи между группами) 0-решенная конфигурация также достижима из . В последовательности конфигураций от до имеются две последующих конфигурации и , где является и S-v-валентной и T-v-валентной. Пусть p - процесс, вызывающий переход из в . Теперь невыполнимо , потому что S-1-валентна и S-0-валентна; аналогично невыполнимо . Мы пришли к противоречию. o

Противоречие существованию протокола P является результатом Требований 13.17 и 13.19; таким образом Теорема 13.16 доказана. o

Аварийно-устойчивый алгоритм согласия Брахи и Туэга. Аварийно-устойчивый алгоритм согласия, предложенный Брахой и Туэгом [BT85] функционирует в раундах: в раунде k процесс посылает сообщение всем процессам (включая себя) и ждет получения N-t сообщений раунда k. Ожидание такого числа сообщений не представляет возможность тупика (см. Упражнение 13.10).

В каждом раунде, процесс p “выкрикивает” голос за 0 или за 1 вместе с весом. Вес - число голосов, полученных для этого значения в предыдущем раунде (1 в первом раунде); голос с весом, превышающим N/2, называется свидетелем. Хотя различные процессы в раунде могут голосовать по-разному, в одном раунде никогда нет свидетелей различных значений, как будет показано ниже. Если процесс p получает свидетеля в раунде k, p голосует за свое значение в раунде k+1; иначе p голосует за большинство полученных голосов. Решение принимается, если в раунде получено больше, чем t свидетелей; решительный процесс выходит основной цикл и свидетели криков в течение следующих двух раундов, чтобы дать возможность другим процессам решить. Протокол дан как Алгоритм 13.3.

var : (0, 1) init (*голос p*)

: integer init 0 (*номер раунда*)

: integer init 1 (*Вес голоса p*)

: integer init 0 (*Счетчик полученных голосов*)

: integer init 0 (*Счетчик полученных свидетелей *)

begin

while do

begin (*сброс счетчиков*)

shout<vote, , , >;

while do

begin receive<vote, r, v, w>;

if r > then (*Будущий раунд…*)

send< vote, r, v, w> to p (*…обработать позже*)

else if r = then

begin

if w > N/2 then (*Свидетель*)

end

else (*r < , ignore*) skip

end;

(*Выбрать новое значение: голос и вес в следующем раунде*)

if then := 0

else if then := 1

else if then := 0

else := 1;

;

(*Принять решение, если более t свидетелей*)

if then ;

end;

(*Помочь другим процессам принять решение*)

shout<vote, , , N-t>;

shout<vote, +1, , N-t>

end

Алгоритм 13.3 Аварийно-устойчивый алгоритм согласия

Голоса, прибывающие для более поздних раундов должны быть обработаны в соответствующем раунде; это моделируется в алгоритме с помощью посылки сообщения самому процессу для обработки позже. Заметьте, что в любом раунде процесс получает самое большее один голос от каждого процесса, общим количеством до N-t голосов; так как более, чем N-t процессов могут “выкрикивать” голос, процессы могут принимать во внимание различные подмножества “выкрикиваемых” голосов. Мы впоследствии покажем несколько свойств алгоритма, которые вместе означают, что это - вероятностный аварийно-устойчивый протокол согласия (Теорема 13.24).

Лемма 13.20 В любом раунде никакие два процесса не свидетельствуют за различные значения.

Доказательство. Предположим, что в раунде k, процесс p свидетельствует за v, и процесс q свидетельствует за w; k > 1, потому что в раунде 1 никакие процессы не свидетельствуют. Предположение подразумевает, что в раунде k-1, p получил больше чем N/2 голосов за v, и q получил больше чем N/2 голосов за w. Вместе задействовано более N голосов; следовательно, процессы от которых p и q получили голоса перекрываются, то есть, есть r, который послал v-голос процессу p и w-голос процессу q. Это означает, что v =w. o

Лемма 13.21 Если процесс принимает решение, то все корректные процессы принимают решение об одном и том же значении, и самое большее два раунда спустя.

Доказательство. Пусть k будет первым раундом, в котором принимается решение, p - процесс, принимающий решение в раунде k, и v - значение решения p. Решение подразумевает, что в раунде k имелись v-свидетели; следовательно, по Лемме 13.20 не имелось свидетелей других значений, так что никакое другое решение не принимается в раунде k.

В раунде k имелось более t свидетелей v (это следует из решения p), следовательно, все корректные процессы получают по крайней мере одного v-свидетеля в раунде k. В результате, все процессы, которые голосуют в раунде k + 1, голосуют за v (заметьте также, что p все еще “выкрикивает” голос в раунде k + 1). Это означает, что, если решение вообще принимается в раунде k + 1, это решение v.

В раунде k + 1 предлагаются только v-голоса, следовательно все процессы, которые голосуют в раунде k + 2 свидетельствуют за v в этом раунде (p тоже). В результате, в раунде k + 2 все корректные процессы, которые не приняли решения в более ранних раундах, получают N-t v-свидетелей и останавливаются на v. o

Лемма 13.22 [никакого решения не принято в раунде] = 0.

Доказательство. Пусть S - множество N-t корректных процессов (такое множество существует) и предположим, что до раунда не принято никакого решения. Предположение законного планирования подразумевает, что, для некоторого , в любом раунде вероятность того, что каждый процесс в S получает точно N-t голосов процессов в S, по крайней мере . Это происходит в трех последующих раундах , и с вероятностью по крайней мере .

Если это происходит, процессы в S получают одни и те же голоса в раунде и следовательно выбирают одно и то же значение, допустим в раунде . Все процессы в S голосуют за в раунде , что означает, что каждый процесс в S получает N-t голосов за в раунде . Это значит, что процессы в S за в раунде ; следовательно они все получают N-t > t свидетелей в раунде , и все принимают решение в этом раунде. Отсюда