Требование 13.19 P не имеет достижимой бивалентной конфигурации.
Доказательство. Пусть дана достижимая бивалентная конфигурация и предположим, что это S-l-валентна и T-1-валентна (используем Требование 13.18). Однако, бивалентна, поэтому (ясно из связи между группами) 0-решенная конфигурация также достижима из . В последовательности конфигураций от до имеются две последующих конфигурации и , где является и S-v-валентной и T-v-валентной. Пусть p - процесс, вызывающий переход из в . Теперь невыполнимо , потому что S-1-валентна и S-0-валентна; аналогично невыполнимо . Мы пришли к противоречию. -
Противоречие существованию протокола P является результатом Требований 13.17 и 13.19; таким образом Теорема 13.16 доказана. -
Аварийно-устойчивый алгоритм согласия Брахи и Туэга. Аварийно-устойчивый алгоритм согласия, предложенный Брахой и Туэгом [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. -
Лемма 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. -
Лемма 13.22 [никакого решения не принято в раунде] = 0.
Доказательство. Пусть S - множество N-t корректных процессов (такое множество существует) и предположим, что до раунда не принято никакого решения. Предположение законного планирования подразумевает, что, для некоторого , в любом раунде вероятность того, что каждый процесс в S получает точно N-t голосов процессов в S, по крайней мере . Это происходит в трех последующих раундах , и с вероятностью по крайней мере .
Если это происходит, процессы в S получают одни и те же голоса в раунде и следовательно выбирают одно и то же значение, допустим в раунде . Все процессы в S голосуют за в раунде , что означает, что каждый процесс в S получает N-t голосов за в раунде . Это значит, что процессы в S за в раунде ; следовательно они все получают N-t > t свидетелей в раунде , и все принимают решение в этом раунде. Отсюда
Pr [Процессы в S не приняли решения в раунде k + 2]
Pr [Процессы в S не не приняли решения до раунда k],
что подтверждает результат. -
Лемма 13.23 Если все процессы начинают алгоритм с входом v, то все они принимают решение v в раунде 2.
Доказательство. Все процессы получают только голоса за v в раунде 1, так что все процессы свидетельствуют за v в раунде 2. Это означает, что все они они принимают решение в этом раунде. -
Теорема 13.24 Алгоритм 13.3 - вероятностный, t-аварийно-устойчивый протокол согласия при t < N/2.
Доказательство. Сходимость показана в Лемме 13.22, а соглашение - в Лемме 13.21; нетривиальность следует из Леммы 13.23. -
Зависимость решения от входных значениях анализируется далее в Упражнении 13.11.
13.4.2 Византийско-устойчивые Протоколы Согласия
Византийская модель сбоев более недоброжелательна, чем модель аварий, потому что Византийские процессы могут выполнять произвольные переводы состояний и могут посылать сообщения, которые расходятся с алгоритмом. В дальнейшем мы будем использовать запись (или ) для обозначения того, что имеется последовательность корректных шагов, то есть, переходов протокола (в процессах S), ведущих систему из в . Аналогично, достижима, если имеется последовательность корректных шагов, ведущих из начальной конфигурации в . Злонамеренность Византийской модели подразумевает более низкий максимум способности восстановления, чем для модели аварийного отказа.
Теорема 13.25 t-Византийско-устойчивого протокола согласия при не существует.
Доказательство. Предположим, напротив, что такой протокол существует. Читателю снова предоставляется показать существование бивалентной начальной конфигурации любого такого протокола (используйте, как обычно, нетривиальность).
Высокая способность восстановления протокола означает, что можно выбрать два множества S и T таких, что , , и . Словом, и S и T достаточно большие, чтобы выжить независимо, но их пересечение может быть полностью злонамеренно. Это используется для демонстрации того, что никакие бивалентные конфигурации не являются достижимыми.
Заявление 13.26 Достижимая конфигурация является или S-0-валентной и T-0-валентной, или S-1- валентной и T-1-валентной.
Доказательство. Так как достигается последовательностью корректных шагов, все возможности для выбора множества t процессов, которые дают сбой, все еще открыты. Предположим, напротив, что S и T могут достичь разных решений, то есть, и , где - конфигурация, где все процессы в S (в T) остановились на v (). Можно достичь противоречивого состояния, предполагая, что процессы в злонамеренные, и объединяя планы следующим образом. Начиная с конфигурации , процессы в сотрудничают с другими процессами в S в последовательности, ведущей к v-решению в S. Когда это решение было принято процессами в S, злонамеренные процессы восстанавливают свое состояние как в конфигурации и впоследствии сотрудничают с процессами в T в последовательности, ведущей к решению в T. Из этого получается конфигурация, в которой корректные процессы приняли решение по-разному, что находится в противоречии с требованием соглашения. -
Заявление 13.27 Достижимой бивалентной конфигурации не существует.
Доказательство. Пусть дана достижимая бивалентная конфигурация и предположим, что является, и S-1-валентной и T-1-валентной (Заявление 13.26). Однако, бивалентна, поэтому из также достижима 0-решенная конфигурация (очевидно, в сотрудничестве между S и T). В последовательности конфигураций из в имеются две вытекающих конфигурации и , причем и S-v-валентна и T-v-валентна. Пусть p - процесс, вызывающий переход из в . Теперь не выполняется , потому что S-1-валентна и S-0-валентна; аналогично не выполняется . Пришли к противоречию. -