Сценарий 1 определен аналогично, но здесь процессы в T сбойные и они посылают сообщения, которые должны были послать в сценарии 0. В этом сценарии процессы в U останавливаются на 1.
В заключение рассмотрим сценарий 2, где процессы в S сбойные и ведут себя следующим образом. Процессам в T они посылают сообщения сценария 0 и процессам в U они посылают сообщения сценария 1. Теперь можно показать индукцией по номеру импульса, что сообщения, посланные T к U (или, от U к T) - точно те, что посланы в сценарии 0 (или 1, соответственно). Следовательно, для процессов в T сценарий 2 неотличим от сценария 0 и для процессов в U он неотличим от сценария 1. Из этого следует, что процессы в T останавливаются на 0, и процессы в U останавливаются на 1. Противоречие. o
В доказательстве используется то, что Византийские процессы могут посылать сообщения 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.
Помощник p действует следующим образом.
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). o
Чтобы доказывать зависимость (также индукцией) предполагается, что командующий корректен, следовательно все 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 выдает нужное значение . o
Лемма 14.4 (Соглашение) Все корректные процессы останавливается на одном и том же значении.
Доказательство. Так как зависимость означает соглашение в выполнениях, в которых командующий является корректным, мы теперь сконцентрируемся на случае, когда командующий сбойный. Но тогда самое большее t-l помощников сбойные, что означает, что вложенные вызовы функционируют в пределах своих способностей восстановления!
Действительно, t < N/3 означает t - 1 < (N - 1) / 3, следовательно, вложенные вызовы удовлетворяют соглашению. Таким образом, все корректные помощники остановятся на одном и том же значении для каждого помощника q во вложенном вызове . Таким образом, каждый корректный помощник вычисляет точно такой же вектор W в импульсе t + 1, что означает, что применение major дает тот же самый результат в каждом корректном процессе. o
Теорема 14.5 Протокол Broadcast(N, t) (Алгоритм 14.2/14.3) - t-Византийско-устойчивый протокол вещания при t < N/3.
Доказательство. Завершение было показано в Лемме 14.2, зависимость в Лемме 14.3, и соглашение в Лемме 14.4. o
Протокол 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 в конце каждого импульса имеем: .
В отличие от протокола Broadcast предыдущего подраздела, протокол Долева и других является асимметричным в значениях 0 и 1. Решение 0 - значение по умолчанию и выбирается, если в обмене было недостаточно много сообщений. Если командующий имеет вход 1, он будет “выкрикивать” сообщения <bm, 1>, и получение достаточно большого количества отраженных сообщений, типа <bm, q>, заставляет процесс принять решение 1.
В алгоритме уместны три типа действия: инициирование, поддержка и подтверждение.
(1) Поддержка. Процесс p поддерживает процесс q в импульсе i, если в более ранних импульсах p получил достаточно доказательств, что q послал сообщения <bm, 1>; если дело обстоит так, p пошлет <bm, q> сообщения в импульсе i. Процесс p прямо поддерживает q, если p получил сообщение <bm, 1> от q. Процесс p косвенно поддерживает q, если p получил сообщение <bm, q> по крайней мере от L процессов. Множество процессов , поддерживаемых p, определяется неявно из
Страницы: 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, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90
