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

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

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.