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

Распределенная задача описывается множествами возможных входных и выходных

значений X и D, и (возможно частичным) отображением

[pic].

Интерпретация отображения T: если вектор [pic] описывает вход процессов, то

[pic] - набор допустимых выходов алгоритма, описанный как вектор решения

[pic]. Если T - частичная функция, допустима не каждая комбинация входных

значений.

Определение 13.10 Алгоритм является t-аварийно устойчивым решением для

задачи T если он удовлетворяет следующим утверждениям.

Завершение. В каждом t-аварийно законном выполнении, все корректные

процессы принимают решение.

Непротиворечивость. Если все процессы корректны, вектор решения [pic]

находится в [pic].

Условие непротиворечивости подразумевает, что в выполнении, где

подмножество процессов принимает решение, частичный вектор решений всегда

можно расширить до вектора в [pic]. Множество [pic] обозначает совокупность

всех векторов выхода, то есть, диапазон T.

Пример: согласие. Проблема согласия требует, чтобы все решения были равны,

т.е.,

[pic].

Пример: выбор. Проблема выбора требует, чтобы один процесс принял решение

1, а другие 0, т.е.,

[pic].

Пример: приблизительное соглашение. В проблеме [pic]-приблизительного

соглашения каждый процесс имеет действительное входное значение и принимает

решение о действительном выходном значении. Максимальное различие между

двумя значениями выхода самое большее e, и выходы должны быть заключены

между двумя входами.

[pic].

Пример: переименование. В проблеме переименования каждый процесс имеет

отдельный идентификатор, который может браться из произвольно большой

области. Каждый процесс должен принять решение о новом имени, из меньшей

области 1, ..., K, так, чтобы все новые имена различались.

[pic].

В сохраняющей порядок версии проблемы переименования, новые имена должны

сохранять порядок старых имен, то есть, [pic].

13.3.1 Разрешимая Проблема: Переименование

В этом подразделе будет представлен алгоритм для переименования Аттийи и

других [ABND+90]. Алгоритм допускает до [pic] аварий (t - параметр

алгоритма) и осуществляет переименование в пространстве имен размера [pic].

Верхняя граница t. Мы сначала покажем, что никакой алгоритм переименования

не сможет выдержать N/2 или большее количество сбоев; фактически, почти все

аварийно-устойчивые алгоритмы имеют ограничение t;

while true

do begin receive

if [pic] then

begin [pic];

if [pic] and [pic] then

(*[pic] впервые не изменялось: принять решение*)

[pic]

end

else if [pic] then

skip (*Игнорировать “старую” информацию*)

else (*новый вход; обновить Vp и начать счет заново*)

begin if [pic] then [pic] else [pic];

[pic]; shout

end

end

end

Алгоритм 13.2 Простой алгоритм переименования.

Алгоритм переименования. В алгоритме переименования (Алгоритм 13.2),

процесс p сохраняет множество [pic] входов процесса, которые p видел;

первоначально, [pic] содержит только [pic]. Каждый раз, когда p получает

множество входов, включая те, которые являются новыми для p, [pic]

расширяется новыми входами. При старте и каждый раз, когда [pic]

расширяется, p “выкрикивает” свое множество. Как видно, множество [pic]

растет только в течение выполнения, т.е., последующие значения [pic]

полностью упорядочиваются при включении, и, кроме того, [pic] содержит

самое большее N имен. Следовательно, процесс p “выкрикивает” свое множество

самое большее N раз, что показывает, что алгоритм завершается и что

сложность по сообщениям ограничена [pic].

Далее, p считает (в переменной [pic]) сколько раз он получил копии своего

текущего множества [pic]. Первоначально [pic] равна 0, и увеличивается

каждый раз, когда получается сообщение, содержащее [pic]. Получение

сообщения может вызвать рост [pic], что требует сброса [pic]. Если

новое значение [pic] равняется V (то есть, если V - строгое надмножество

старого [pic]), [pic] устанавливается в 1, иначе в 0.

Говорят, что процесс p, достигает устойчивого множества V если [pic]

становится равным N-t, когда значение [pic] - V. Другими словами, p получил

в (N-t)-й раз текущее значение V Vp.

Лемма 13.12 Устойчивые множества полностью упорядочены, то есть, если q

достигает устойчивого множества [pic] и r достигает устойчивого множества

[pic], то [pic] или [pic].

Доказательство. Предположим, что q достигает устойчивого множества [pic] и

r достигает устойчивого множества [pic]. Это подразумевает, что q получил

от N-t процессов и r получил от N-t процессов.

Так как 2(N-t) > N, то есть по крайней мере один процесс, допустим p, от

которого q получил и r получил . Следовательно,

как [pic] так и [pic] - значения [pic], что означает, что одно включено в

другое. (

Лемма 13.13 Каждый корректный процесс по крайней мере однажды достигает

устойчивого множества в каждом законном t-аварийном выполнении.

Доказательство. Пусть p - корректный процесс; множество [pic] может только

расширяться, и содержит самое большее N входных имен. Следовательно, для

[pic] достигается максимальное значение [pic]. Процесс p “выкрикивает” это

значение, и сообщение получается каждым корректным процессом,

что показывает, что каждый корректный процесс в конечном счете имеет

надмножество [pic].

Однако, это надмножество не строгое; иначе корректный процесс послал бы

строгое надмножество [pic] к p, что противоречит выбору [pic] (как самого

большого множества когда-либо побывавшего в p). Следовательно, каждый

корректный процесс q имеет значение [pic] по крайней мере один раз при

выполнении, и следовательно каждый корректный процесс посылает p сообщение

в течение выполнения. Все эти сообщения получаются при

выполнении, и, поскольку [pic] никогда не увеличивается за пределы [pic],

они все подсчитываются и заставляют [pic] стать устойчивым в p. (

После достижения устойчивого множества V впервые, процесс p останавливается

на паре (s, r), где s - размер V, и r - положение [pic] в V. Устойчивый

множество было получено от N-t процессов, и следовательно содержит по

крайней мере N-t входных имен, что показывает [pic]. Положение в множестве

размера s удовлетворяет [pic]. Число возможных решений, следовательно,

[pic], что равняется [pic]; если нужно, можно использовать фиксированное

отображение пар на целые числа в диапазоне 1,..., K (Упражнение 13.5).

Теорема 13.14 Алгоритм 13.2 решает проблему переименования с выходным

пространством имен размера [pic].

Доказательство. Так как, в любом законном t-аварийном выполнении каждый

корректный процесс достигает устойчивого множества, каждый корректный

процесс останавливается на новом имени. Чтобы показать, что все новые имена

различны, рассмотрим устойчивые множества [pic] и [pic], достигаемые

процессами q и r соответственно. Если эти множества имеют различные

размеры, решения q и r различны, потому что размер включается в решение.

Если множества имеют один и тот же размер, то по Лемме 13.12, они равны;

тогда q и r имеют различный ранг в множестве, что снова показывает, что их

решения различны. (

Обсуждение. Заметьте, что процесс не завершает Алгоритм 13.2 после принятия

решения о своем имени; он продолжает алгоритм, чтобы "помочь" другим

процессам тоже принять решение. Aттийя и другие [ABND+90] показывают, что

это необходимо, потому что алгоритм должен справиться с ситуацией, когда

некоторые процессы настолько медленны, что выполняют первый шаг после того,

как некоторые другие процессы уже приняли решение.

Простой алгоритм, представленный здесь не самый лучший в отношении размера

пространства имен, используемого для переименования. Aттийя и другие

[ABND+90] привели более сложный алгоритм, который назначает имена в

диапазоне от 1 до N + t. Результаты следующего подраздела предполагают

нижнюю границу размера нового пространства имен для аварийно-устойчивого

переименования N + 1.

Aттийя и другие предложили также алгоритм для переименования, сохраняющего

порядок. Он осуществляет переименование на целые числа в диапазоне от 1 до

[pic], что, как было показано, является самым маленьким размером

пространства имен, позволяющего t-аварийно-устойчивое переименование,

сохраняющее порядок.

13.3.2 Расширение Результатов Невозможности

Результат о невозможности согласия (Теорема 13.8) был обобщен Мораном и

Вольфшталом [MW87] для более общих проблем решения. Граф решения задачи T -

граф [pic], где [pic] и

E = {([pic], [pic]): [pic] и [pic] отличаются точно в одном компоненте}.

Задача T называется связной, если [pic]- связный граф, и несвязной иначе.

Моран и Вольфштал предположили, что входной граф задачи T (определенный

аналогично графу решения) связный, то есть, как в доказательстве Леммы 13.6

мы можем двигаться между любыми двумя входными конфигурациями, изменяя по

порядку входы процесса. Кроме того, результат невозможности был доказан для

не-тривиальных алгоритмов, то есть, алгоритмов, которые удовлетворяют, в

дополнение к (1) завершению и (2) непротиворечивости,

Нетривиальность. Для каждого [pic] имеется достижимая конфигурация, в

которой процессы остановились на (приняли решение) [pic].

Теорема 13.15 Нетривиального 1-аварийно-устойчивого алгоритма решения для

несвязной задачи T не существует.

Доказательство. Предположим, напротив, что такой алгоритм, A, существует;

из него можно получить алгоритм согласия А', что противоречит Теореме 13.8.

Чтобы упростить аргументацию, мы полагаем, что [pic] содержит два связных

компонента, "0" и "1".

Алгоритм А’ сначала моделирует A, но вместо того, чтобы остановиться на

значении d, процесс “выкрикивает” и ждет получения N-1 сообщений

голосования. Тупика не возникает, потому что все корректные процессы

принимают решение в A; следовательно по крайней мере N-1 процессов

“выкрикивают” сообщение голосования.

После получения сообщений, у процесса p есть N-l компонентов вектора в

[pic]. Этот вектор можно расширить значением процесса, от которого голос не

был получен так, чтобы весь вектор находился в [pic]. (Действительно,

непротиворечивое решение принято этим процессом, или все еще возможно.)

Теперь заметим, что различные процессы могут вычислять различные

расширения, но эти расширения принадлежат одному и тому же связному

компоненту графа [pic]. Каждый процесс, который получил N-1 голосов,

останавливается на (принимает решение) имени связанного компонента,

которому принадлежит расширенный вектор. Остается показать, что А' является

алгоритмом согласия.

Завершение. Выше уже обсуждалось, что каждый корректный процесс получает по

крайней мере N-1 голосов.

Соглашение. Мы сначала докажем, что существует вектор [pic] такой, что

каждый корректный процесс получает N-1 компонентов [pic].

Случай 1: Все процессы нашли решение в A. Пусть [pic] будет вектором

достигнутых решений; каждый процесс получает N-1 компонентов [pic], хотя

"недостающий" компонент может быть различным для каждого процесса.

Случай 2: Все процессы за исключением одного, допустим r, нашли решение в

A. Все корректные процессы получают одни и те же N-1 решений, а именно

решения всех процессов за исключением r. Возможно, что r потерпел аварию,

но, так как возможно , что r просто очень медленный, он все же сможет

достичь решения, то есть, существует вектор [pic], который расширяет

решения, принятые на настоящий момент.

Из существования [pic] следует, что каждый процесс принимает решение о

связном компоненте этого вектора.

Нетривиальность. Из нетривиальности A, можно достичь векторы решения как в

компоненте 0, так и в компоненте 1; по построению А’ оба решения возможны.

Таким образом, А' является асинхронным, детерминированным, 1-аварийно-

устойчивым алгоритмом согласия. Алгоритма А не существует по Теореме 13.8.

(

Обсуждение. Требование нетривиальности, утверждающее, что каждый вектор

решения в [pic] достижим, является довольно сильным. Можно спросить, могут

ли некоторые алгоритмы, которые являются тривиальными в этом смысле тем не

менее быть интересными. В качестве примера, рассмотрим Алгоритм 13.2 для

переименования; с ходу не видно, что он нетривиален, то есть, каждый вектор

с отдельным именем достижим (да, достижим); еще менее понятно то, почему

нетривиальность может представлять интерес в этом случае.

Исследование доказательства Теоремы 13.15 показывает, что в доказательстве

можно использовать более слабое требование нетривиальности, а именно, что

векторы решения достижимы по крайней мере в двух различных связных

компонентах [pic]. Такую ослабленную нетривиальность можно иногда вывести

из формулировки проблемы.

Фундаментальная работа о задачах решения, которые являются разрешимыми и

неразрешимыми при наличии одного сбойного процессора, была выполнена

Бираном, Мораном и Заксом [BMZ90]. Они дали полную комбинаторную

характеристику разрешимых задач решения.

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

В доказательстве Теоремы 13.8 показано, что каждый асинхронный алгоритм

согласия имеет бесконечные выполнения, в которых никакое решение не

принимается. К счастью, для хорошо подобранных алгоритмов такие выполнения

могут быть достаточно редки и иметь вероятность 0, что делает алгоритмы

очень полезными в вероятностном смысле; см. Главу 9. В этом разделе мы

представляем два вероятностных алгоритма согласия, один для модели аварий,

другой для Византийской модели; алгоритмы были предложены Брахой и Туэгом

[BT85]. В обоих случаях сначала доказывается верхний предел для способности

восстановления (t < N/2 и t < N/3, соответственно) и что и оба алгоритма

удовлетворяют соответствующей границе.

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

требование завершения сделано вероятностным, то есть, заменено более слабым

требованием сходимости.

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

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

Частичная правильность (Соглашение) должна удовлетворяться при каждом

выполнении; возникающие в результате вероятностные алгоритмы имеют класс

Las Vegas (Подраздел 9.1.2).

Вероятность принимается всеми выполнениями, начинающимися в данной

начальной конфигурации. Чтобы вероятности были значимыми, должно быть

задано распределение вероятности над этими выполнениями. Это можно сделать

использованием рандомизации в процессах (как в Главе 9), но здесь вместо

этого определяется распределение вероятности на прибытиях сообщений.

Распределение вероятности на выполнениях, начинающихся в данной начальной

конфигурации, определяется предположением о законном планировании. Оба

алгоритма функционируют в раундах; в раунде процесс “выкрикивает” сообщение

и ждет получения N-t сообщений. Определим R(q, p, k) как событие, когда в

раунде k процесс p получает (раунд-k) сообщение q среди первых N-t

сообщений. Законное планирование означает, что

[pic] [pic].

Для всех 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-аварийно-устойчивого протокола согласия для [pic]не

существует.

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

следующий три требования.

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

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

читателю. (

Для подмножества процессов S, конфигурация [pic] называется S-валентной,

если и 0- и 1-решенные конфигурации достижимы из [pic] с помощью только

шагов в S. [pic]называется S-0-валентной если, делая шаги только в S, 0-

решенная конфигурация, и никакая 1-решенная конфигурации, может быть

достигнута, S-1-валентная конфигурация определяется аналогично.

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

Требование 13.18 Достижимая конфигурация [pic]является или S-0-валентной и

T-0-валентной, или S-1-валентной и T-1-валентной.

Доказательство. Действительно, высокая способность восстановления протокола

подразумевает, что и S и T могут достигать решения независимо; если

возможны различные решения, можно достичь противоречивой конфигурации,

объединяя планы. (

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

Доказательство. Пусть дана достижимая бивалентная конфигурация [pic] и

предположим, что это [pic] S-l-валентна и T-1-валентна (используем

Требование 13.18). Однако, [pic] бивалентна, поэтому (ясно из связи между

группами) 0-решенная конфигурация [pic] также достижима из [pic]. В

последовательности конфигураций от [pic]до [pic] имеются две последующих

конфигурации [pic] и [pic], где [pic] является и S-v-валентной и T-v-

валентной. Пусть p - процесс, вызывающий переход из [pic] в [pic]. Теперь

невыполнимо [pic], потому что [pic] S-1-валентна и [pic] S-0-валентна;

аналогично невыполнимо [pic]. Мы пришли к противоречию. (

Противоречие существованию протокола 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 [pic] : (0, 1) init [pic] (*голос p*)

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

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

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

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

begin

while [pic] do

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

shout;

while [pic] do

begin receive;

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

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

else if r = [pic] then

begin [pic]

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

[pic]

end

else (*r < [pic], ignore*) skip

end;

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

if [pic] then [pic]:= 0

else if [pic] then [pic]:= 1

else if [pic] then [pic]:= 0

else [pic]:= 1;

[pic];

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

if [pic] then [pic];

[pic]

end;

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

shout;

shout

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 [pic][никакого решения не принято в раунде[pic]] = 0.

Доказательство. Пусть S - множество N-t корректных процессов (такое

множество существует) и предположим, что до раунда [pic] не принято

никакого решения. Предположение законного планирования подразумевает, что,

для некоторого [pic], в любом раунде вероятность того, что каждый процесс в

S получает точно N-t голосов процессов в S, по крайней мере [pic]. Это

происходит в трех последующих раундах [pic], [pic] и [pic] с вероятностью

по крайней мере [pic].

Если это происходит, процессы в S получают одни и те же голоса в раунде

[pic] и следовательно выбирают одно и то же значение, допустим [pic] в

раунде [pic]. Все процессы в S голосуют за [pic] в раунде [pic], что

означает, что каждый процесс в S получает N-t голосов за [pic] в раунде

[pic]. Это значит, что процессы в S за [pic] в раунде [pic]; следовательно

они все получают N-t > t свидетелей [pic] в раунде [pic], и все принимают

решение [pic] в этом раунде. Отсюда

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

[pic]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 Византийско-устойчивые Протоколы Согласия

Византийская модель сбоев более недоброжелательна, чем модель аварий,

потому что Византийские процессы могут выполнять произвольные переводы

состояний и могут посылать сообщения, которые расходятся с алгоритмом. В

дальнейшем мы будем использовать запись [pic] (или [pic]) для обозначения

того, что имеется последовательность корректных шагов, то есть, переходов

протокола (в процессах S), ведущих систему из [pic] в [pic]. Аналогично,

[pic] достижима, если имеется последовательность корректных шагов, ведущих

из начальной конфигурации в [pic]. Злонамеренность Византийской модели

подразумевает более низкий максимум способности восстановления, чем для

модели аварийного отказа.

Теорема 13.25 t-Византийско-устойчивого протокола согласия при [pic] не

существует.

Доказательство. Предположим, напротив, что такой протокол существует.

Читателю снова предоставляется показать существование бивалентной начальной

конфигурации любого такого протокола (используйте, как обычно,

нетривиальность).

Высокая способность восстановления протокола означает, что можно выбрать

два множества S и T таких, что [pic], [pic], и [pic]. Словом, и S и T

достаточно большие, чтобы выжить независимо, но их пересечение может быть

полностью злонамеренно. Это используется для демонстрации того, что никакие

бивалентные конфигурации не являются достижимыми.

Заявление 13.26 Достижимая конфигурация [pic] является или S-0-валентной и

T-0-валентной, или S-1- валентной и T-1-валентной.

Доказательство. Так как [pic] достигается последовательностью корректных

шагов, все возможности для выбора множества t процессов, которые дают сбой,

все еще открыты. Предположим, напротив, что S и T могут достичь разных

решений, то есть, [pic] и [pic], где [pic] - конфигурация, где все

процессы в S (в T) остановились на v ([pic]). Можно достичь противоречивого

состояния, предполагая, что процессы в [pic] злонамеренные, и объединяя

планы следующим образом. Начиная с конфигурации [pic], процессы в [pic]

сотрудничают с другими процессами в S в последовательности, ведущей к v-

решению в S. Когда это решение было принято процессами в S, злонамеренные

процессы восстанавливают свое состояние как в конфигурации [pic] и

впоследствии сотрудничают с процессами в T в последовательности, ведущей к

[pic] решению в T. Из этого получается конфигурация, в которой корректные

процессы приняли решение по-разному, что находится в противоречии с

требованием соглашения. (

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

Доказательство. Пусть дана достижимая бивалентная конфигурация [pic] и

предположим, что [pic] является, и S-1-валентной и T-1-валентной (Заявление

13.26). Однако, [pic] бивалентна, поэтому из [pic] также достижима 0-

решенная конфигурация [pic] (очевидно, в сотрудничестве между S и T). В

последовательности конфигураций из [pic]в [pic] имеются две вытекающих

конфигурации [pic] и [pic], причем [pic] и S-v-валентна и T-v-валентна.

Пусть p - процесс, вызывающий переход из [pic] в [pic]. Теперь не

выполняется [pic], потому что [pic] S-1-валентна и [pic] S-0-валентна;

аналогично не выполняется [pic]. Пришли к противоречию. (

Последнее заявление противоречит существованию бивалентных начальных

конфигураций. Таким образом Теорема 13.25 доказана. (

Рисунок 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

увеличивает [pic] после получения сообщения голоса .

Алгоритм гарантирует, что p проходит раунд k только после принятия N-t

голосов, и что p принимает также самое большее один голос за каждый процесс

в каждом раунде.

var [pic] : (0, 1) init [pic];

[pic] : integer init 0;

[pic] : integer init 0;

[pic] : integer init 0;

repeat forall [pic]do begin [pic]; [pic] end;

shout;

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

while [pic] do

begin receive from q;

if уже был получен от q

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

else if t=in and [pic]

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

else if [pic]

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

send to p

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

case t of

in: shout

ec: if [pic] then

begin [pic]

if [pic]

then [pic]

end

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

esac

end;

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

if [pic] then [pic] else [pic];

if [pic] then [pic];

[pic]

until false

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

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

корректный процесс r, то r голосовал за v в раунде k.

Доказательство. Процесс p принимает голос после получения сообщения от более (N+t)/2 (различных) процессов; по крайней мере один

корректный процесс s послал такое сообщение p. Процесс s посылает эхо p

после получения сообщения от r, что означает, так как r

корректен, что r голосует за v в раунде k. (

Лемма 13.29 Если корректные процессы p и q принимают голос за процесс r в

раунде k, они принимают тот же самый голос.

Доказательство. Предположим, что в раунде k процесс p принимает v-голос за

r, а процесс q принимает w-голос. Таким образом, p получил от более (N+t)/2 процессов, и q получил от более

(N+t)/2 процессов. Так как имеется только N процессов, то, должно быть,

более t процессов послали процессу p и процессу q. Это значит, что по крайней мере один корректный процесс

сделал так, и следовательно v = w. (

Лемма 13.30 Если все корректные процессы начинают раунд k, то они принимают

достаточно много голосов в этом раунде, чтобы закончить его.

Доказательство. Корректный процесс r, начинающий раунд k с [pic],

“выкрикивает” начальный голос для этого раунда, который отражается всеми

корректными процессами. Таким образом, для корректных процессов p и r,

посылается p по крайней мере N-t процессами, позволяя p

принять v-голос за r в раунде k, если не принято ранее N-t других голосов.

Отсюда следует, что процесс p принимает N-t голосов в этом раунде. (

Теперь доказательство правильности протокола похоже на доказательство

правильности аварийно-устойчивого протокола.

Лемма 13.31 Если корректный процесс принимает решение (останавливается на)

v в раунде k, то все корректные процессы выбирают v в раунде k и всех более

поздних раундах.

Доказательство. Пусть S - множество по крайней мере (N + t)/2 процессов,

для которых p принимает v-голос в раунде k. Корректный процесс q принимает

в раунде k N-t голосов, включая по крайней мере [pic] голосов за процессы в

S. По Лемме 13.29, q принимает более (N-t)/2 v-голоса, что означает, что q

выбирает v в раунде k.

Чтобы показать, что все корректные процессы выбирают v в более поздних

раундах, предположим, что все корректные процессы выбирают v в некотором

раунде l; следовательно, все корректные процессы голосуют за v в раунде

l+1. В раунде l+1 каждый корректный процесс принимает N-t голосов, включая

более (N-t)/2 голосов за корректные процессы. По Лемме 13.28, корректный

процесс принимает по крайней мере (N-t)/2 v-голоса, и, следовательно, снова

выбирает v в раунде l+1. (

Лемма 13.32 [pic] Pr [Корректный процесс p не принял решения до раунда k] =

0.

Доказательство. Пусть S - множество по крайней мере N-t корректных

процессов и предположим, что p не принял решения до раунда k. С

вероятностью [pic] > 0 все процессы в S принимают в раунде k голоса за одну

и ту же совокупность N-t процессов и, в раунде k + 1, только голоса за

процессы в S. Если это происходит, процессы в S голосуют одинаково в раунде

k + 1 и принимают решение в раунде k + 1. Отсюда

Pr [Корректный процесс p не принял решения до раунда k + 2]

[pic]Pr [Корректный процесс p не принял решения до раунда k],

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

Лемма 13.33 Если все корректные процессы начинают алгоритм с входом v, в

конечном счете принимается решение v.

Доказательство. Как в доказательстве Леммы 13.31 можно показать, что все

корректные процессы выбирают v снова в каждом раунде. (

Теорема 13.34 Алгоритм 13.5 - вероятностный, t-Византийско-устойчивый

протокол согласия при t < N/3.

Доказательство. Сходимость показана в Лемме 13.32 и соглашение - в Лемме

13.31; нетривиальность следует из Леммы 13.33. (

Зависимость решения от входных значений проанализирована далее в Упражнении

13.12. Алгоритм 13.5 описывается как бесконечный цикл для простоты

представления; мы в заключение описываем, как можно модифицировать

алгоритм, чтобы он завершался в каждом решающем процессе. После принятия

решения v в раунде k процесс p выходит из цикла и “выкрикивает”

"множественные" голоса и отражает . Эти сообщения интерпретируются как начальный и отражаемый голоса для

всех раундов после k. Действительно, p голосует за v во всех более поздних

раундах, и все корректные процессы будут голосовать так же (Лемма 13.31).

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18