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

Соглашение. Все корректные процессы останавливаются на одном и том же

значении.

Зависимость. Если командующий корректен, все корректные процессы

останавливаются на [pic].

Можно, кроме этого, требовать одновременности, то есть, что все корректные

процессы принимают решение в одном и том же импульсе. Все алгоритмы,

обсуждаемые в этом и следующем разделах, удовлетворяют требованию

одновременности; см. также Подраздел 14.2.6.

14.1.1 Граница Способности восстановления

Способность восстановления синхронных сетей после Византийских сбоев, как в

случае асинхронных сетей (Теорема 13.25), ограничена t < N/3. Эта граница

была впервые продемонстрирована Пизом, Шостаком и Лампортом [PSL80]

представлением нескольких сценариев для алгоритма в присутствии N/3 или

более Византийских процессов. В отличие от сценариев, используемых в

доказательстве Теоремы 13.25, здесь корректные процессы получают

противоречивую информацию, позволяющую заключить, что некоторые процессы

являются сбойными. Однако, как оказывается, невозможно определить, какие

процессы являются ненадежными, и неверные процессы могут навязать неверное

решение.

Теорема 14.1 t-Византийско-устойчивого протокола вещания при t>N/3 не

существует.

Доказательство. Как в ранних доказательствах, способность восстановления

N/3 или выше позволяет разделить процессы на три группы (S, T, и U), каждая

из которых может быть полностью сбойной. Группа, содержащая командующего,

называется S. Противоречие получается из рассмотрения трех сценариев,

изображенных на Рисунке 14.1, где сбойная группа обозначена двойным блоком.

[pic]

Рисунок 14.1 Сценарии для доказательства теоремы 14.1.

В сценарии 0 командующий вещает значение 0, и процессы в группе U сбойные;

в сценарии 1 командующий вещает 1 и процессы в T сбойные. В импульсе i

сценария 0 процессы группы U посылают процессам группы T в точности те

сообщения, которые они послали бы (согласно протоколу) в 1 сценарии. (То

есть, сообщения, посланные в ответ на сообщения, полученные в импульсе i-1

сценария 1.) Процессам в S они посылают сообщения, направляемые протоколом.

Процессы в S и T, конечно, посылают корректные сообщения во всех импульсах.

Заметьте, что в этом сценарии только процессы группы U посылают

неправильные сообщения, и спецификации протокола предписывают, что все

корректные процессы, включая группу T, останавливаются на 0.

Сценарий 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. Противоречие.

(

В доказательстве используется то, что Византийские процессы могут посылать

сообщения 1-сценария, даже если они получили только сообщения 0-сценария.

То есть, процессы могут "лгать" не только о своем собственном состоянии, но

также и о сообщениях, которые они получили. Именно эту возможность можно

устранить с помощью установления подлинности, как описано в Разделе 14.2;

это ведет к способности восстановления N-1.

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

В этом подразделе будет показано, что верхняя граница способности

восстановления, показанная в предыдущем подразделе, точна. Кроме того,

противопоставляя ситуации в асинхронных сетях, максимальная способность

восстановления достижима при использовании детерминированных алгоритмов. Мы

представляем рекурсивный алгоритм, также Пиза и других [PSL80], который

допускает t Византийских отказа при t < N/3. Способность восстановления -

параметр алгоритма.

Алгоритм Broadcast(N, 0) дан как Алгоритм 14.2; он не допускает отказов (t

= 0), и если отказов не происходит, все процессы останавливаются на входе

командующего в 1 импульсе. Если отказ происходит, соглашение может быть

нарушено, но завершение (и одновременность), тем не менее, гарантируется.

Импульс

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

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

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

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

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

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

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 решения хранятся в массиве [pic], из которого решение p

получается большинством голосов (значение, полученное непосредственно от

командующего, здесь игнорируется!). Для этого на массивах определяется

детерминированная функция major, с таким свойством, что, если v имеет

большинство в W, (то есть, более половины элементов равны, то major(W)=v.

Импульс

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

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

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

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

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

then [pic] else [pic]

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

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

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

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

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

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

[pic] := решение в [pic];

[pic]

Алгоритм 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 выбирает [pic]. Теперь N > 2f + t

означает (N - 1) > 2f + (t - 1), поэтому гипотеза индукции применяется к

вложенным вызовам, даже если теперь все f сбойных процесса находятся среди

помощников. Таким образом, для корректных помощников p и q, решение p в

Broadcast(N-1, t-1) равняется [pic], то есть, [pic]. Но, поскольку строгое

большинство помощников корректно (N > 2f + t), процесс p завершится с

[pic], в котором большинство значений равняется [pic]. Следовательно,

применение major к p выдает нужное значение [pic]. (

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

том же значении.

Доказательство. Так как зависимость означает соглашение в выполнениях, в

которых командующий является корректным, мы теперь сконцентрируемся на

случае, когда командующий сбойный. Но тогда самое большее t-l помощников

сбойные, что означает, что вложенные вызовы функционируют в пределах своих

способностей восстановления!

Действительно, t < N/3 означает t - 1 < (N - 1) / 3, следовательно,

вложенные вызовы удовлетворяют соглашению. Таким образом, все корректные

помощники остановятся на одном и том же значении [pic] для каждого

помощника q во вложенном вызове [pic]. Таким образом, каждый корректный

помощник вычисляет точно такой же вектор 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

корректных процессов. Обратите внимание, что предположение [pic] необходимо

и достаточно для выбора L и H, удовлетворяющих этим трем свойствам.

Алгоритм обменивается сообщениями типа , где v или значение 1, или

имя процесса (bm обозначает “broadcast message”, “вещать сообщение”.)

Процесс p содержит двухмерную булеву таблицу R, где [pic] истинен тогда и

только тогда, когда p получил сообщение от процесса q.

Первоначально все элементы таблицы ложны, и мы полагаем, что таблица

обновляется в фазе получения каждого импульса (это не показано в Алгоритме

14.4). Заметьте, что [pic] монотонна в импульсах, то есть, если [pic]

становится истинным в некотором импульсе, он остается истиной в более

поздних импульсах. Кроме того, так как только корректные процессы

“выкрикивают” сообщения, для корректных p, q, и r в конце каждого импульса

имеем: [pic].

В отличие от протокола Broadcast предыдущего подраздела, протокол Долева и

других является асимметричным в значениях 0 и 1. Решение 0 - значение по

умолчанию и выбирается, если в обмене было недостаточно много сообщений.

Если командующий имеет вход 1, он будет “выкрикивать” сообщения , и

получение достаточно большого количества отраженных сообщений, типа , заставляет процесс принять решение 1.

В алгоритме уместны три типа действия: инициирование, поддержка и

подтверждение.

Поддержка. Процесс p поддерживает процесс q в импульсе i, если в более

ранних импульсах p получил достаточно доказательств, что q послал сообщения

; если дело обстоит так, p пошлет сообщения в импульсе i.

Процесс p прямо поддерживает q, если p получил сообщение от q.

Процесс p косвенно поддерживает q, если p получил сообщение по

крайней мере от L процессов. Множество процессов [pic], поддерживаемых p,

определяется неявно из [pic]

[pic] (*прямая*)

[pic] (*косвенная*)

[pic]

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

корректный процесс поддерживает процесс q, то q послал по крайней мере одно

сообщение . Действительно, предположим, что некоторый корректный

процесс поддерживает q, пусть i - первый импульс, в котором это происходит.

Так как косвенная поддержка q требует получения по крайней мере одного

сообщения от корректного процесса в более раннем импульсе, первая

поддержка корректным процессом процесса q - прямая. Прямая поддержка

корректным процессом означает, что этот процесс получил сообщение

от q.

Подтверждение. Процесс p подтверждает процесс q после получения сообщения

от H процессов, то есть,

[pic]

Выбор порогов означает, что, если корректный процесс p подтверждает q, то

все корректные процессы подтверждают q самое большее одним импульсом позже.

Действительно, предположим, что p подтверждает q после импульса i. Процесс

p получил сообщения от H процессов, включая (выбором порогов) по

крайней мере L корректных поддерживающих для q. Корректные поддерживающие

для q посылают сообщение всем процессам, что означает, что в

импульсе i все корректные процессы получают по крайней мере L сообщений

и поддерживают q в импульсе i + 1. Таким образом, в импульсе i + 1

все корректные процессы посылают , и поскольку число корректных

процессов по крайней мере H, каждый корректный процесс получает достаточную

поддержку, чтобы подтвердить q.

Инициирование. Процесс p инициирует, когда у него есть достаточно

доказательств того, что окончательное значения решения будет 1. После

инициирования, процесс p посылает сообщения . Инициирование может

быть вызвано тремя типами доказательств, а именно (1) p - командующий и

[pic], (2) p получает от командующего в импульсе 1, или (3) p

подтвердил достаточно много помощников в конце последнего импульса.

Последняя возможность в частности требует некоторого внимания, так как

число подтвержденных помощников, которое является "достаточным"

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

счет для этого правила. В первых трех импульсах L помощников должны быть

подтверждены, чтобы инициировать, но начиная с импульса 4 порог

увеличивается через каждые два импульса. Таким образом, инициирование

согласно правилу (3) требует, чтобы к концу импульса i, [pic] помощников

было подтверждено. Запись [pic] в алгоритме обозначает множество

подтвержденных помощников, то есть, [pic]. Инициирование процессом p

представляется булевой переменной [pic].

Если корректный помощник r инициирует в конце импульса i, все корректные

процессы подтверждают r в конце импульса i + 2. Действительно, r

“выкрикивает” в импульсе i + 1, поэтому все корректные процессы

(прямо) поддерживают r в импульсе i + 2, так что каждый процесс получает по

крайней мере H сообщений в этом импульсе.

Алгоритм продолжается в течение 2t + 3 импульсов; если процесс p подтвердил

по крайней мере H процессов (здесь считает командующий) к концу того

импульса, p принимает решение 1, иначе p принимает решение 0. См. Алгоритм

14.4.

var [pic] : boolean init false

[pic] : boolean init if [pic] then true else false;

Импульс i: (* Фаза посылки *)

if [pic] then shout;

forall [pic] do shout;

получить все сообщения импульса i;

(*обновление состояния*)

if i = 1 and [pic] then [pic];

if [pic] then [pic];

if i = 2t + 3 then (*принять решение*)

if [pic] then [pic] else [pic]

Алгоритм 14.4 Протокол с надежным вещанием.

Командующий, являющийся единственным процессом, который может

самостоятельно предписать инициирования (в других процессах) занимает

мощное положение в алгоритме. Легко заметить, что, если командующий

корректно инициирует, начинается лавина сообщений, которая заставляет все

корректные процессы подтвердить H процессов и остановиться на значении 1. К

тому же если он не инициирует, то нет "критической массы" сообщений,

которая ведет к инициированию любого корректного процесса.

Лемма 14.6 Алгоритм 14.4 удовлетворяет завершению (и одновременности) и

зависимости.

Доказательство. Из алгоритма видно, что все корректные процессы принимают

решение в конце импульса 2t + 3, что показывает завершение и

одновременность. Чтобы показать зависимость, мы предположим, что

командующий корректен.

Если командующий корректен и имеет вход 1, он “выкрикивает” сообщение в импульсе 1, заставляя каждый корректный процесс q инициировать.

Следовательно, каждый корректный процесс q “выкрикивает” в

импульсе 2, так что к концу импульса 2 каждый корректный процесс p

поддерживает все другие корректные процессы. Это означает, что в импульсе 3

каждый корректный p “выкрикивает” для каждого корректного q, так

что в конце импульса 3 каждый корректный процесс получает от

каждого другого корректного процесса, заставляя его подтвердить q. Таким

образом с конца раунда 3 каждый корректный процесс подтвердил H процессов,

что означает, что окончательное решение будет 1. (Командующий

поддерживается и подтверждается всеми корректными процессами одним

импульсом ранее других процессов.)

Если командующий корректен и имеет вход 0, он не “выкрикивает” в

импульсе 1, чего не делает и никакой другой корректный процесс.

Предположим, что никакой корректный процесс не инициировал в импульсах с 1

по i-1; тогда никакой корректный процесс не посылает в импульсе i.

В конце импульса i никакой корректный процесс не поддерживает и не

подтверждает никакого корректного процесса, так как, как мы видели ранее,

Страницы: 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