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

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

Pr [Процессы в S не приняли решения в раунде k + 2]

Pr [Процессы в S не не приняли решения до раунда k],

что подтверждает результат. o

Лемма 13.23 Если все процессы начинают алгоритм с входом v, то все они принимают решение v в раунде 2.

Доказательство. Все процессы получают только голоса за v в раунде 1, так что все процессы свидетельствуют за v в раунде 2. Это означает, что все они они принимают решение в этом раунде. o

Теорема 13.24 Алгоритм 13.3 - вероятностный, t-аварийно-устойчивый протокол согласия при t < N/2.

Доказательство. Сходимость показана в Лемме 13.22, а соглашение - в Лемме 13.21; нетривиальность следует из Леммы 13.23. o

Зависимость решения от входных значениях анализируется далее в Упражнении 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. Из этого получается конфигурация, в которой корректные процессы приняли решение по-разному, что находится в противоречии с требованием соглашения. o

Заявление 13.27 Достижимой бивалентной конфигурации не существует.

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

Последнее заявление противоречит существованию бивалентных начальных конфигураций. Таким образом Теорема 13.25 доказана. o

p

r

Рисунок 13.4 Византийский процесс, моделирующий другие процессы.

Византийско-устойчивый алгоритм согласия Брахи и Туэга. При t < N/3, t-Византийско-устойчивые протоколы согласия существуют. Необходимо, чтобы система связи позволяла процессу определять, каким процессом было послано полученное сообщение. Если Византийский процесс p может послать корректному процессу r сообщение и успешно симулировать получение процессом r сообщения от q (см Рисунок 13.4), проблема становится неразрешимой. Действительно, процесс p может моделировать достаточно много корректных процессов, чтобы навязать неправильное решение в процессе r.

Подобно аварийно-устойчивому протоколу, Византийско-устойчивый протокол (Алгоритм 13.5) функционирует в раундах. В каждый раунде каждый процесс может представлять на рассмотрение голоса, и решение принимается, когда достаточно много процессов голосуют за одно и то же значение. Более низкая способность восстановления (t < N/3) устраняет необходимость в различении свидетелей и не-свидетелей; процесс принимает решение после принятия более (N + t) /2 голосов за одно и то же значение.

Злонамеренность этой модели отказов требует, однако, введения механизма проверки голоса, что является затруднением протокола. Без такого механизма Византийский процесс может нарушать голосование среди корректных процессов, посылая различные голоса различным корректным процессам. Такое злонамеренное поведение не возможно в модели аварийного отказа. Механизм проверки гарантирует, что, хотя Византийский процесс r может посылать различные голоса корректным процессам p и q, он не может обмануть p и q, чтобы они приняли различные голоса за r (в некотором раунде).

Механизм проверки основан на отражении сообщений. Процесс “выкрикивает” свой голос (как initial, in), и каждый процесс, после получения первого голоса за некоторый процесс в некотором раунде, отражает эхом голос (как echo, ec). Процесс примет голос, если для него были приняты более (N+t)/2 отраженных сообщений. Механизм проверки сохраняет (частичную) правильность коммуникации между корректными процессами (Лемма 13.28), и корректные процессы никогда не принимают различные голоса за один и тот же процесс (Лемма 13.29). Тупиков нет (Лемма 13.30).

Мы говорим, что процесс p принимает v-голос за процесс r в раунде k, если p увеличивает после получения сообщения голоса <vote, ec, r, v, k>. Алгоритм гарантирует, что p проходит раунд k только после принятия N-t голосов, и что p принимает также самое большее один голос за каждый процесс в каждом раунде.

var : (0, 1) init ;

: integer init 0;

repeat forall do begin ; end;

shout<vote, in, p, , >;

(*Теперь принять N-t голосов для текущего раунда*)

while do

begin receive<vote, t, r, v, rn> from q;

if <vote, t, r, *, rn> уже был получен от q

then skip (*q повторяет, должно быть, Византийский*)

else if t=in and

then skip (*q лжет, должно быть, Византийский *)

else if

then (*обработать сообщение в более позднем раунде*)

send<vote, t, r, v, rn> to p

else (*Обработать или отразить сообщение голоса*)

case t of

in: shout<vote, ec, r, v, rn>

ec: if then

begin

then

end

else skip (*старое сообщение*)

esac

end;

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

if then else ;

if then ;

until false

Алгоритм 13.5 Византийско-устойчивый алгоритм согласия.

Лемма 13.28 Если корректный процесс p принимает в раунде k голос v за корректный процесс r, то r голосовал за v в раунде k.

Доказательство. Процесс p принимает голос после получения сообщения <vote, ec, r, v, k> от более (N+t)/2 (различных) процессов; по крайней мере один корректный процесс s послал такое сообщение p. Процесс s посылает эхо p после получения сообщения <vote, in, r, v, k> от r, что означает, так как r корректен, что r голосует за v в раунде k. o

Лемма 13.29 Если корректные процессы p и q принимают голос за процесс r в раунде k, они принимают тот же самый голос.

Доказательство. Предположим, что в раунде k процесс p принимает v-голос за r, а процесс q принимает w-голос. Таким образом, p получил <vote, ec, r, v, k> от более (N+t)/2 процессов, и q получил <vote, ec, r, w, k> от более (N+t)/2 процессов. Так как имеется только N процессов, то, должно быть, более t процессов послали <vote, ec, r, v, k> процессу p и <vote, ec, r, w, k> процессу q. Это значит, что по крайней мере один корректный процесс сделал так, и следовательно v = w. o

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62