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

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).             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, определяется неявно из

   (*прямая*)

    (*косвенная*)

Порог для становления косвенным поддерживающим означает, что если корректный процесс поддерживает процесс q, то q послал по крайней мере одно сообщение <bm, 1>. Действительно, предположим, что некоторый корректный процесс поддерживает q, пусть i - первый импульс, в котором это происходит. Так как косвенная поддержка q требует получения по крайней мере одного сообщения <bm, q> от корректного процесса в более раннем импульсе, первая поддержка корректным процессом процесса q - прямая. Прямая поддержка корректным процессом означает, что этот процесс получил сообщение <bm, 1> от q.

(2)   Подтверждение. Процесс p подтверждает процесс q после получения сообщения <bm, q> от H процессов, то есть,

Выбор порогов означает, что, если корректный процесс p подтверждает q, то все корректные процессы подтверждают q самое большее одним импульсом позже. Действительно, предположим, что p подтверждает q после импульса i. Процесс p получил сообщения <bm, q> от H процессов, включая (выбором порогов) по крайней мере L корректных поддерживающих для q. Корректные поддерживающие для q посылают сообщение <bm, q> всем процессам, что означает, что в импульсе i все корректные процессы получают по крайней мере L сообщений <bm, q> и поддерживают q в импульсе i + 1. Таким образом, в импульсе i + 1 все корректные процессы посылают <bm, q>, и поскольку число корректных процессов по крайней мере H, каждый корректный процесс получает достаточную поддержку, чтобы подтвердить q.

(3)   Инициирование. Процесс p инициирует, когда у него есть достаточно доказательств того, что окончательное значения решения будет 1. После инициирования, процесс p посылает сообщения <bm, 1>. Инициирование может быть вызвано тремя типами доказательств, а именно (1) p - командующий и , (2) p получает <bm, 1> от командующего в импульсе 1, или (3) p подтвердил достаточно много помощников в конце последнего импульса. Последняя возможность в частности требует некоторого внимания, так как число подтвержденных помощников, которое является "достаточным" увеличивается в течение выполнения, и подтвержденный командующий не идет в счет для этого правила. В первых трех импульсах L помощников должны быть подтверждены, чтобы инициировать, но начиная с импульса 4 порог увеличивается через каждые два импульса. Таким образом, инициирование согласно правилу (3) требует, чтобы к концу импульса i,  помощников было подтверждено. Запись  в алгоритме обозначает множество подтвержденных помощников, то есть, . Инициирование процессом p представляется булевой переменной .

Если корректный помощник r инициирует в конце импульса i, все корректные процессы подтверждают r в конце импульса i + 2. Действительно, r “выкрикивает” <bm, 1> в импульсе i + 1, поэтому все корректные процессы (прямо) поддерживают r в импульсе i + 2, так что каждый процесс получает по крайней мере H сообщений <bm, q> в этом импульсе.

Алгоритм продолжается в течение 2t + 3 импульсов; если процесс p подтвердил по крайней мере H процессов (здесь считает командующий) к концу того импульса, p принимает решение 1, иначе p принимает решение 0. См. Алгоритм 14.4.

var              : boolean init false

                             : boolean init if  then true else false;

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

if  then shout<bm, 1>;

forall  do shout<bm, q>;

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

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

if i = 1 and  then  ;

if  then ;

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

   if  then  else

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

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

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

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