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

Заявление 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;

                  : integer           init 0;

            : 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

                                                            if

                                                               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

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

Доказательство. Корректный процесс r, начинающий раунд k с , “выкрикивает” начальный голос для этого раунда, который отражается всеми корректными процессами. Таким образом, для корректных процессов p и r, <vote, ec, r, v, k> посылается p по крайней мере N-t процессами, позволяя p принять v-голос за r в раунде k, если не принято ранее N-t других голосов. Отсюда следует, что процесс p принимает N-t голосов в этом раунде.                                                                                                         o

Теперь доказательство правильности протокола похоже на доказательство правильности аварийно-устойчивого протокола.

Лемма 13.31 Если корректный процесс принимает решение (останавливается на) v в раунде k, то все корректные процессы выбирают v в раунде k и всех более поздних раундах.

Доказательство. Пусть S - множество по крайней мере (N + t)/2 процессов, для которых p принимает v-голос в раунде k. Корректный процесс q принимает в раунде k N-t голосов, включая по крайней мере  голосов за процессы в 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.                                        o

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

Доказательство. Пусть S - множество по крайней мере N-t корректных процессов и предположим, что p не принял решения до раунда k. С вероятностью  > 0 все процессы в S принимают в раунде k голоса за одну и ту же совокупность N-t процессов и, в раунде k + 1, только голоса за процессы в S. Если это происходит, процессы в S голосуют одинаково в раунде k + 1 и принимают решение в раунде k + 1. Отсюда

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

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

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

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

Доказательство. Как в доказательстве Леммы 13.31 можно показать, что все корректные процессы выбирают v снова в каждом раунде.                                                                                        o

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

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

Зависимость решения от входных значений проанализирована далее в Упражнении 13.12. Алгоритм 13.5 описывается как бесконечный цикл для простоты представления; мы в заключение описываем, как можно модифицировать алгоритм, чтобы он завершался в каждом решающем процессе. После принятия решения v в раунде k процесс p выходит из цикла и “выкрикивает” "множественные" голоса <vote, in, p, k+, v> и отражает <vote, ec, *, k+, v>. Эти сообщения интерпретируются как начальный и отражаемый голоса для всех раундов после k. Действительно, p голосует за v во всех более поздних раундах, и все корректные процессы будут голосовать так же (Лемма 13.31). Следовательно, множественные сообщения - такие, которые были бы посланы процессом p при продолжении алгоритма, с возможным исключением для отражений злонамеренных начальных голосов.

13.5 Слабое Завершение

В этом разделе изучается проблема асинхронного Византийского вещания. Цель вещания состоит в том, чтобы cделать значение, которое присутствует в одном процессе g, командующем, известным всем процессам. Формально, требование нетривиальности для протокола согласия усилено заданием того, что значение решения является входом командующего, если он корректен:

(3)   Зависимость. Если командующий корректен, все корректные процессы останавливаются на (принимают решение о) его входе.

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

Теорема 13.35 1-Византийско-устойчивого алгоритма, удовлетворяющего сходимости, соглашению, и зависимости, даже если сходимость требуется только, если командующий послал по крайней мере одно сообщение, не существует.

Доказательство. Рассмотрим два сценария. В первом командующий считается Византийским; сценарий служит, чтобы определить достижимую конфигурацию . Затем получается противоречие во втором сценарии.

(1)   Предположим, что командующий - Византийский и что он посылает сообщение, чтобы инициализировать вещание "0" процессу  и сообщение, чтобы инициализировать вещание "1" процессу . Затем командующий останавливается. Назовем возникающую в результате конфигурацию .

Из сходимости следует, что решенная конфигурация может быть достигнута даже если отказывает командующий; пусть S = P \ {g}, и предположим, что , где  0-решенная.

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

                                                                                                                                             o

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

Определение 13.36 t-Византийско-устойчивый алгоритм вещания - алгоритм, удовлетворяющий следующим трем требованиям.

(1)   Слабое завершение. Все корректные процессы принимают решение, или никакой корректный процесс не принимают решения. Если командующий корректен, все корректные процессы принимают решение.

(2)   Соглашение. Если корректные процессы принимают решение, они останавливаются на одном и том же значении.

(3)   Зависимость. Если командующий корректен, все корректные процессы останавливаются на его входе.

Можно показать, пользуясь аргументами, подобными используемым в доказательстве Теоремы 13.25, что способность восстановления асинхронного Византийского алгоритма вещания ограничена t < N/3. Алгоритм вещания Брахи и Туэга [BT85], данный как Алгоритм 13.6, использует три типа сообщений голосов: начальные (initial) сообщения (тип in), отраженные (echo) сообщения (тип ec), и готовые (ready) сообщения (тип re). Каждый процесс подсчитывает для каждого типа и значения, сколько сообщений были получены, считая самое большее одно сообщение, полученное от каждого процесса.

Командующий инициализирует вещание, “выкрикивая” начальный голос. После получения начального голоса от командующего, процесс “выкрикивает” отраженный голос, содержащий то же самое значение. Когда было получено более (N+t)/2 отраженных сообщения со значением v, “выкрикивается” готовое сообщение. Число отраженных сообщений достаточно велико, чтобы гарантировать, что никакие корректные процессы не посылают готовых сообщений для различные значения (Лемма 13.37). Получение более t готовых сообщений для одного и того же значения (что означает, что по крайней мере один корректный процесс послал такое сообщение) также вызывает “выкрикивание” готовых сообщений. Получение более 2t готовых сообщений для одного и того же значения (что означает, что более t корректных процессов послали такое сообщение) вызывает принятие решения для этого значения. В Алгоритме 13.6 не принято никаких мер, чтобы предотвратить “выкрикивание” готового сообщения корректным процессом дважды, т.к. такое сообщение все равно игнорируется корректными процессами.

var        : integer           init 0;

Только дëÿ командующего: shout<vote, in, >

Äëÿ âñåõ ïðîöåññîâ:

while  do

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

                        if от q уже было получено сообщение голоса <vote, t, v>

                                    then skip         (*q повторяется, игнорировать*)

                        else if t = in and

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

                        else      begin   ;

                                                case t of

                                                   in:     if = 1 then shout<vote, ec, v>

                                                   ec:     if

then shout<vote, re, v>

                                                   re:     if  then shout<vote, re, v>;

                                                            if  then ;

                                                esac

Страницы: 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