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

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

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

В заключение рассмотрим сценарий 2, где процессы в S сбойные и ведут себя следующим образом. Процессам в T они посылают сообщения сценария 0 и процессам в U они посылают сообщения сценария 1. Теперь можно показать индукцией по номеру импульса, что сообщения, посланные T к U (или, от U к T) - точно те, что посланы в сценарии 0 (или 1, соответственно). Следовательно, для процессов в T сценарий 2 неотличим от сценария 0 и для процессов в U он неотличим от сценария 1. Из этого следует, что процессы в T останавливаются на 0, и процессы в U останавливаются на 1. Противоречие. 

В доказательстве используется то, что Византийские процессы могут посылать сообщения 1-сценария, даже если они получили только сообщения 0-сценария. То есть, процессы могут "лгать" не только о своем собственном состоянии, но также и о сообщениях, которые они получили. Именно эту возможность можно устранить с помощью установления подлинности, как описано в Разделе 14.2; это ведет к способности восстановления N-1.

14.1.2 Алгоритм Византийского вещания

В этом подразделе будет показано, что верхняя граница способности восстановления, показанная в предыдущем подразделе, точна. Кроме того, противопоставляя ситуации в асинхронных сетях, максимальная способность восстановления достижима при использовании детерминированных алгоритмов. Мы представляем рекурсивный алгоритм, также Пиза и других [PSL80], который допускает t Византийских отказа при t < N/3. Способность восстановления - параметр алгоритма.

Алгоритм Broadcast(N, 0) дан как Алгоритм 14.2; он не допускает отказов (t = 0), и если отказов не происходит, все процессы останавливаются на входе командующего в 1 импульсе. Если отказ происходит, соглашение может быть нарушено, но завершение (и одновременность), тем не менее, гарантируется.

Импульс

1: Командующий посылает <value, > всем процессам,

помощники не посылают.

Получить сообщения импульса 1.

Командующий принимает решение на .

Помощники принимают решение следующим образом:

if от g в импульсе 1 было получено cообщение <value, x>

then принять решение x

else принять решение udef

Алгоритм 14.2 Broadcast (N, 0).

Протокол для способности восстановления t>0 (Алгоритм 14.3) использует рекурсивные вызовы процедуры для способность восстановления t-1. Командующий посылает свой вход всем помощникам в импульсе 1, и в следующем импульсе, каждый помощник начинает вещание полученного значения другим помощникам, но это вещание имеет способность восстановления t-1. Эта уменьшенная способность восстановления - трудноуловимый момент алгоритма, потому что (если командующий корректен) все t Византийские процессы могут находиться среди помощников, так что фактическое число отказов может превышать способность восстановления вложенного вызова Broadcast. Чтобы доказать правильность возникающего в результате алгоритма, необходимо рассуждать, используя способность восстановления t и фактическое число сбойных процессов f (см. Лемму 14.3). В импульсе t+1 вложенные вызовы производят решение, поэтому помощник p принимает решение в N-1 вложенных вещаниях. Эти N-1 решения хранятся в массиве , из которого решение p получается большинством голосов (значение, полученное непосредственно от командующего, здесь игнорируется!). Для этого на массивах определяется детерминированная функция major, с таким свойством, что, если v имеет большинство в W, (то есть, более половины элементов равны, то major(W)=v.

Импульс

1: Командующий посылает <value, > всем процессам,

помощники не посылают.

Получить сообщения импульса 1.

Помощник p действует следующим образом.

if от g в импульсе 1 было получено cообщение <value, x>

then else

Объявить другим помощникам, действуя как командующий

в в следующем импульсе

(t+1): получить сообщения импульса t + 1.

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

Для помощника p:

Для каждого помощника q в встречается решение.

:= решение в ;

Алгоритм 14.3 Вещание (N, t) (ДЛЯ t> 0).

Лемма 14.2 (Завершение) Если Broadcast(N, t) начинается в импульсе 1, каждый процесс принимает решение в импульсе t+1.

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

В алгоритме Broadcast(N, 0) (Алгоритм 14.2), каждый процесс принимает решение в импульсе 1.

В алгоритме Broadcast(N, t) помощники начинают рекурсивные обращения алгоритма, Broadcast(N-1, t-1), в импульсе 2. Если алгоритм начат в импульсе 1, он принимает решение в импульсе t (это - гипотеза индукции), следовательно если он начат в импульсе 2, все вложенные вызовы принимают решение в импульсе t + 1. В одном том же импульсе принимается решение в Broadcast(N, t). 

Чтобы доказывать зависимость (также индукцией) предполагается, что командующий корректен, следовательно все t сбойных процесса находятся среди N-1 помощников. Так как t < (N - l) /3 не всегда выполняется, простую индукцию использовать нельзя, и мы рассуждаем, используя фактическое число неисправностей, обозначенное f.

Лемма 14.3 (Зависимость) Если командующий корректен, если имеется f сбойных процессов, и если N > 2f+t, то все корректные процессы останавливаются на входе командующего.

Доказательство. В алгоритме Broadcast(N, 0) если командующий корректен, все корректные процессы, останавливаются на значении входа генерала.

Теперь предположим, что лемма справедлива для Broadcast(N-1, t-1). Так как командующий корректен, он посылает свой вход всем помощникам в импульсе 1, так что каждый корректный помощник q выбирает . Теперь N > 2f + t означает (N - 1) > 2f + (t - 1), поэтому гипотеза индукции применяется к вложенным вызовам, даже если теперь все f сбойных процесса находятся среди помощников. Таким образом, для корректных помощников p и q, решение p в Broadcast(N-1, t-1) равняется , то есть, . Но, поскольку строгое большинство помощников корректно (N > 2f + t), процесс p завершится с , в котором большинство значений равняется . Следовательно, применение major к p выдает нужное значение . 

Лемма 14.4 (Соглашение) Все корректные процессы останавливается на одном и том же значении.

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

Действительно, t < N/3 означает t - 1 < (N - 1) / 3, следовательно, вложенные вызовы удовлетворяют соглашению. Таким образом, все корректные помощники остановятся на одном и том же значении для каждого помощника q во вложенном вызове . Таким образом, каждый корректный помощник вычисляет точно такой же вектор W в импульсе t + 1, что означает, что применение major дает тот же самый результат в каждом корректном процессе. 

Теорема 14.5 Протокол Broadcast(N, t) (Алгоритм 14.2/14.3) - t-Византийско-устойчивый протокол вещания при t < N/3.

Доказательство. Завершение было показано в Лемме 14.2, зависимость в Лемме 14.3, и соглашение в Лемме 14.4. 

Протокол Broadcast принимает решение в (t + 1)-ом импульсе, что является оптимальным; см. Подраздел 14.2.6. К сожалению, его сложность по сообщениям экспоненциальная; см. Упражнение 14.1.

14.1.3 Полиномиальный Алгоритм Вещания

В этом разделе мы представляем Византийский алгоритм вещания Долева и других [DFF+82], который использует только полиномиальное число сообщений и бит. Временная сложность выше, чем у предыдущего протокола; алгоритм требует 2t+3 импульса для достижения решения. В следующем описании будет предполагаться, что N = 3t + 1, и позже будет обсужден случай N > 3t + 1.

Алгоритм использует два порога, L = t + 1 и H = 2t + 1. Эти числа выбираются так, что (1) каждое множество из L процессов содержит по крайней мере один корректный процесс, (2) каждое множество из H процессов содержит по крайней мере L корректных процессов, и (3) имеется по крайней мере H корректных процессов. Обратите внимание, что предположение необходимо и достаточно для выбора L и H, удовлетворяющих этим трем свойствам.

Алгоритм обменивается сообщениями типа <bm, v>, где v или значение 1, или имя процесса (bm обозначает “broadcast message”, “вещать сообщение”.) Процесс p содержит двухмерную булеву таблицу R, где истинен тогда и только тогда, когда p получил сообщение <bm, v> от процесса q. Первоначально все элементы таблицы ложны, и мы полагаем, что таблица обновляется в фазе получения каждого импульса (это не показано в Алгоритме 14.4). Заметьте, что монотонна в импульсах, то есть, если становится истинным в некотором импульсе, он остается истиной в более поздних импульсах. Кроме того, так как только корректные процессы “выкрикивают” сообщения, для корректных p, q, и r в конце каждого импульса имеем: .

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

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