ref (664672), страница 45

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 45)

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

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

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

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

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

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

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

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

1. Для второго сценария, предположим, что командующий корректен и имеет вход 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

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 верных готовых сообщений и примут верное решение. 

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

Доказательство. Слабое завершение следует из Лемм 13.39 и 13.38, соглашение - из Леммы 13.38, и зависимость - из Леммы 13.39. 

Упражнения к Главе 13

Раздел 13.1

Упражнение 13.1 Удаление любого из трех требований Определения 13.3 (завершения, соглашения, нетривиальности) для проблемы согласия позволяет принять очень простое решение. Покажите это, представив три простых решения.

Упражнение 13.2 В доказательстве Леммы 13.6 предполагается, что каждое из назначений бит N процессам производит возможную входную конфигурацию.

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

1. Дано, что четность входа является четной (то есть, имеется четное число процессов со входом 1) в каждой начальной конфигурации.

2. Имеются два (известных) процесса и , и каждая начальная конфигурация удовлетворяет .

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

Раздел 13.2

Упражнение 13.3 Покажите, что при t-изначально-мертвых-устойчивого алгоритма выбора нет.

Характеристики

Список файлов реферата