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

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

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