Алгоритм использует два порога, 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 удовлетворяет завершению (и одновременности) и зависимости.
Доказательство. Из алгоритма видно, что все корректные процессы принимают решение в конце импульса 2t + 3, что показывает завершение и одновременность. Чтобы показать зависимость, мы предположим, что командующий корректен.
Если командующий корректен и имеет вход 1, он “выкрикивает” сообщение <bm, 1> в импульсе 1, заставляя каждый корректный процесс q инициировать. Следовательно, каждый корректный процесс q “выкрикивает” <bm, 1> в импульсе 2, так что к концу импульса 2 каждый корректный процесс p поддерживает все другие корректные процессы. Это означает, что в импульсе 3 каждый корректный p “выкрикивает” <bm, q> для каждого корректного q, так что в конце импульса 3 каждый корректный процесс получает <bm, q> от каждого другого корректного процесса, заставляя его подтвердить q. Таким образом с конца раунда 3 каждый корректный процесс подтвердил H процессов, что означает, что окончательное решение будет 1. (Командующий поддерживается и подтверждается всеми корректными процессами одним импульсом ранее других процессов.)
Если командующий корректен и имеет вход 0, он не “выкрикивает” <bm, 1> в импульсе 1, чего не делает и никакой другой корректный процесс. Предположим, что никакой корректный процесс не инициировал в импульсах с 1 по i-1; тогда никакой корректный процесс не посылает <bm, 1> в импульсе i. В конце импульса i никакой корректный процесс не поддерживает и не подтверждает никакого корректного процесса, так как, как мы видели ранее, это подразумевает, что последний процесс послал сообщение <bm, 1>. Следовательно, никакой корректный процесс не инициирует в конце импульса i. Отсюда следует, что никакой корректный процесс не инициирует вообще. Это означает, что никакой корректный процесс никогда не подтверждает корректный процесс, так что никакой корректный процесс не подтверждает более t процессов, и решение в конечном импульсе - 0. -
Мы продолжим доказательством соглашения, и будем предполагать в следующих леммах, что командующий сбойный. Достаточная "критическая масса" сообщений, ведущая неизбежно к 1-решению, создается инициированием L корректных процессов, когда имеется по крайней мере четыре импульса.
Лемма 14.7 Если L корректных процессов инициируют к концу импульса i, i < 2t, то все корректные процессы останавливаются на значении 1.
Доказательство. Пусть i - первый импульс, в конце которого по крайней мере L корректных процессов инициируют, и пусть А обозначает множество корректных процессов, которые инициировали в конце импульса i. Все процессы в A - помощники, так как командующий сбойный. В конце импульса i + 2 все корректные процессы подтвердили помощников в А; мы покажем, что в это время все корректные процессы инициируют.
Случай i = 1: Все корректные процессы подтвердили помощников из А к концу импульса 3, и инициируют, так как .
Случай : По крайней мере один процесс, допустим r, из А инициировал в импульсе i, так как он подтвердил Th(i) помощников (инициирование с помощью получения <bm, 1> от командующего возможно только в импульсе 1). Эти Th(i) помощников подтверждены всеми корректными процессами в конце импульса i + l, но r не принадлежит к этим Th(i) подтвержденным помощникам, так как r впервые посылает сообщения <bm, 1> в импульсе i + 1. Однако, все корректные процессы подтвердят r к концу импульса i + 2; таким образом они подтвердили по крайней мере Th(i) + 1 помощников в конце раунда i + 2. В заключение, так как Th(i+2)= Th(i)+1, все корректные процессы инициируют.
Теперь, поскольку все корректные процессы инициируют к концу раунда i + 2, они подтверждены (всеми корректными процессами) в конце раунда i + 4, следовательно все корректные процессы подтвердили по крайней мере H помощников. Поскольку предполагалось, что i < 2t, , так что все корректные процессы останавливаются на значении 1. -