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

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

Лемма 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.

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

Определение 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

end

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

Лемма 13.37 Никакие два корректных процесса не посылают готовых сообщений для различных значений.

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

Пусть p - первый корректный процесс, который шлет готовое сообщение для v, и q - первый корректный процесс, который шлет готовое сообщение для w. Хотя готовое сообщение может быть послано после получения достаточно большого числа готовых сообщений, дело обстоит не так для первого корректного процесса, который посылает готовое сообщение. Это происходит из-за того, что перед его посылкой должны быть получены t+1 готовых сообщения, что означает, что готовое сообщение от по крайней мере одного корректного процесса уже было получено. Таким образом, p получил v-отражения от более (N+t)/2 процессов и q получил w--отражения от более (N+t)/2 процессов.

Так как имеется только N процессов и t < N/3, есть более t процессов, включая по крайней мере один корректный процесс r, от которых p получил v-отражение, а q получил w-отражение. Так как r корректен, то v = w.

Лемма 13.38 Если корректный процесс принимает решение, то все корректные процессы принимают решение относительно одного и того же значения.

Доказательство. Чтобы остановиться на v, для v должно быть получено более 2t готовых сообщений, которые включают в себя более t готовых сообщений от корректных процессов; по Лемме 13.37 решения будут согласованными.

Предположим, что корректный процесс p останавливается на v; p получил более 2t готовых сообщений, включая более t сообщений от корректных процессов. Корректный процесс, посылающий готовое сообщение к p, посылает это сообщение всем процессам, что означает, что все корректные процессы получают более t готовых сообщений. Это, в свою очередь, значит, что все корректные процессы посылают готовое сообщение, так что каждый корректный процесс в конечном счете получает N-t > 2t готовых сообщений и принимает решение.

Лемма 13.39 Если командующий корректен, все корректные процессы останавливаются на его входе.

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

Если командующий корректен, он посылает начальный голос со своим входом всем корректным процессам, и все корректные процессы “выкрикивают” отражение с этим значением. Следовательно, все корректные процессы получат по крайней мере N-t > (N+t)/2 корректных отраженных сообщений и “выкрикнут” готовое сообщение с корректным значением. Таким образом, все корректные процессы получат по крайней мере N-t > 2t верных готовых сообщений и примут верное решение. o

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

Доказательство. Слабое завершение следует из Лемм 13.39 и 13.38, соглашение - из Леммы 13.38, и зависимость - из Леммы 13.39. 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