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

Следовательно, множественные сообщения - такие, которые были бы посланы

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

отражений злонамеренных начальных голосов.

13.5 Слабое Завершение

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

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

процессе g, командующем, известным всем процессам. Формально, требование

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

решения является входом командующего, если он корректен:

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

останавливаются на (принимают решение о) его входе.

При таком уточнении, однако, командующий становится единичной точкой

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

теореме.

Теорема 13.35 1-Византийско-устойчивого алгоритма, удовлетворяющего

сходимости, соглашению, и зависимости, даже если сходимость требуется

только, если командующий послал по крайней мере одно сообщение, не

существует.

Доказательство. Рассмотрим два сценария. В первом командующий считается

Византийским; сценарий служит, чтобы определить достижимую конфигурацию

[pic]. Затем получается противоречие во втором сценарии.

Предположим, что командующий - Византийский и что он посылает сообщение,

чтобы инициализировать вещание "0" процессу [pic] и сообщение, чтобы

инициализировать вещание "1" процессу [pic]. Затем командующий

останавливается. Назовем возникающую в результате конфигурацию [pic].

Из сходимости следует, что решенная конфигурация может быть достигнута даже

если отказывает командующий; пусть S = P \ {g}, и предположим, что [pic],

где [pic] 0-решенная.

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

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

[pic] и [pic], после которого его сообщения задерживаются в течение очень

длительного времени. Теперь предположим, что [pic]- Византийский, и, после

получения сообщения, изменяет свое состояние на состояние в [pic], то есть,

притворяется, что получил 0-сообщение от командующего. Так как [pic], то

теперь можно достичь 0-решения без взаимодействия с командующим, что не

дозволяется, потому что командующий корректен и имеет вход 1.

(

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

вещание и останавливается (первый сценарий) без предоставления достаточной

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

покажем, что (детерминированное) решение возможно, если завершение

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

Определение 13.36 t-Византийско-устойчивый алгоритм вещания - алгоритм,

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

Слабое завершение. Все корректные процессы принимают решение, или никакой

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

корректные процессы принимают решение.

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

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

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

останавливаются на его входе.

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

доказательстве Теоремы 13.25, что способность восстановления асинхронного

Византийского алгоритма вещания ограничена t < N/3. Алгоритм вещания Брахи

и Туэга [BT85], данный как Алгоритм 13.6, использует три типа сообщений

голосов: начальные (initial) сообщения (тип in), отраженные (echo)

сообщения (тип ec), и готовые (ready) сообщения (тип re). Каждый процесс

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

считая самое большее одно сообщение, полученное от каждого процесса.

Командующий инициализирует вещание, “выкрикивая” начальный голос. После

получения начального голоса от командующего, процесс “выкрикивает”

отраженный голос, содержащий то же самое значение. Когда было получено

более (N+t)/2 отраженных сообщения со значением v, “выкрикивается” готовое

сообщение. Число отраженных сообщений достаточно велико, чтобы

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

сообщений для различные значения (Лемма 13.37). Получение более t готовых

сообщений для одного и того же значения (что означает, что по крайней мере

один корректный процесс послал такое сообщение) также вызывает

“выкрикивание” готовых сообщений. Получение более 2t готовых сообщений для

одного и того же значения (что означает, что более t корректных процессов

послали такое сообщение) вызывает принятие решения для этого значения. В

Алгоритме 13.6 не принято никаких мер, чтобы предотвратить “выкрикивание”

готового сообщения корректным процессом дважды, т.к. такое сообщение все

равно игнорируется корректными процессами.

var [pic] : integer init 0;

Только для командующего: shout

Для всех процессов:

while [pic] do

begin receive from q;

if от q уже было получено сообщение голоса

then skip (*q повторяется, игнорировать*)

else if t = in and [pic]

then skip (*q подражает g, должно быть, Византийский*)

else begin [pic];

case t of

in: if [pic]= 1 then shout

ec: if [pic]

then shout

re: if [pic] then shout;

if [pic] then [pic];

esac

end

end

Алгоритм 13.6 Византийско-устойчивый алгоритм вещания.

Лемма 13.37 Никакие два корректных процесса не посылают готовых сообщений

для различных значений.

Доказательство. Корректный процесс принимает самое большее одно начальное

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

для самое большее одного значения.

Пусть p - первый корректный процесс, который шлет готовое сообщение для v,

и q - первый корректный процесс, который шлет готовое сообщение для w. Хотя

готовое сообщение может быть послано после получения достаточно большого

числа готовых сообщений, дело обстоит не так для первого корректного

процесса, который посылает готовое сообщение. Это происходит из-за того,

что перед его посылкой должны быть получены t+1 готовых сообщения, что

означает, что готовое сообщение от по крайней мере одного корректного

процесса уже было получено. Таким образом, p получил v-отражения от более

(N+t)/2 процессов и q получил w--отражения от более (N+t)/2 процессов.

Так как имеется только N процессов и t < N/3, есть более t процессов,

включая по крайней мере один корректный процесс r, от которых p получил v-

отражение, а q получил w-отражение. Так как r корректен, то v = w.

(

Лемма 13.38 Если корректный процесс принимает решение, то все корректные

процессы принимают решение относительно одного и того же значения.

Доказательство. Чтобы остановиться на v, для v должно быть получено более

2t готовых сообщений, которые включают в себя более t готовых сообщений от

корректных процессов; по Лемме 13.37 решения будут согласованными.

Предположим, что корректный процесс p останавливается на v; p получил более

2t готовых сообщений, включая более t сообщений от корректных процессов.

Корректный процесс, посылающий готовое сообщение к p, посылает это

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

получают более t готовых сообщений. Это, в свою очередь, значит, что все

корректные процессы посылают готовое сообщение, так что каждый корректный

процесс в конечном счете получает N-t > 2t готовых сообщений и принимает

решение.

(

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

останавливаются на его входе.

Доказательство. Если командующий корректен, он не посылает начальных

сообщений со значениями, отличными от своего входа. Следовательно, никакой

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

командующего, что означает, что самое большее t процессов посылают неверные

отражения. Такого количества неверных отражений недостаточно для того,

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

что означает, что самое большее t процессов посылают неверные готовые

сообщения. Такого количества неверных готовых сообщений недостаточно для

того, чтобы корректный процесс посылал готовые сообщения или принимал

решения, что означает, что никакой корректный процесс не посылает неверного

готового сообщения и не принимает неправильного решения.

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

всем корректным процессам, и все корректные процессы “выкрикивают”

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

по крайней мере N-t > (N+t)/2 корректных отраженных сообщений и “выкрикнут”

готовое сообщение с корректным значением. Таким образом, все корректные

процессы получат по крайней мере N-t > 2t верных готовых сообщений и примут

верное решение. (

Теорема 13.40 Алгоритм 13.6 - асинхронный t-Византийско-устойчивый алгоритм

вещания при t < N/3.

Доказательство. Слабое завершение следует из Лемм 13.39 и 13.38, соглашение

- из Леммы 13.38, и зависимость - из Леммы 13.39. (

Упражнения к Главе 13

Раздел 13.1

Упражнение 13.1 Удаление любого из трех требований Определения 13.3

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

принять очень простое решение. Покажите это, представив три простых

решения.

Упражнение 13.2 В доказательстве Леммы 13.6 предполагается, что каждое из

[pic] назначений бит N процессам производит возможную входную конфигурацию.

Приведите детерминированные, 1-аварийно устойчивые протоколы согласия для

каждого из следующих ограничений на входные значения.

Дано, что четность входа является четной (то есть, имеется четное число

процессов со входом 1) в каждой начальной конфигурации.

Имеются два (известных) процесса [pic] и [pic], и каждая начальная

конфигурация удовлетворяет [pic].

В каждой начальной конфигурации имеется, по крайней мере, [pic] процессов с

одним и тем же входом.

Раздел 13.2

Упражнение 13.3 Покажите, что при [pic] t-изначально-мертвых-устойчивого

алгоритма выбора нет.

Раздел 13.3

Упражнение 13.4 Покажите, что никакой алгоритм для [pic]-приблизительного

соглашения не может вынести [pic] сбоев.

Упражнение 13.5 Дайте биекцию из множества

{ (S, r): [pic] and [pic]}

на целые числа в диапазоне [1, ..., K].

Проект 13.6 Алгоритм 13.2 нетривиален?

Упражнение 13.7 Адаптируйте доказательство Теоремы 13.15 для случая, когда

[pic] состоит из k связных компонент.

Упражнение 13.8 В этом упражнении мы рассматриваем проблему [k, l]-выбора,

который обобщает обычную проблему выбора. Проблема требует, чтобы все

корректные процессы остановились или на 0 ("побежденный") или на 1

("избранный"), и что число процессов, которые принимают решение 1 находится

между k и l (включительно).

Каковы использования [k, l]-выбора?

Покажите, что не существует детерминированного 1-аварийно-устойчивого

алгоритма для [k, k]-выбора (если 0 < k < N).

Приведите детерминированный t-аварийно-устойчивый алгоритм для [k, k+2t]-

выборa.

Раздел 13.4

Упражнение 13.9 Означает ли требование сходимости, что ожидаемое число

шагов ограничено?

Ограничено ли ожидаемое число шагов во всех алгоритмах этого раздела?

Упражнение 13.10 Покажите, что, если все корректные процессы начинают раунд

k аварийно-устойчивого алгоритма согласия (Алгоритм 13.3), то все

корректные процессы также закончат раунд k.

Упражнение 13.11

Докажите, что если более (N+t)/2 процессов начинают аварийно-устойчивый

алгоритм согласия (Алгоритм 13.3) с входом v, то решение для v принимается

за три раунда.

Докажите, что если более (N-t)/2 процессов начинают этот алгоритм с входом

v, то решение для v возможно.

Является ли решение для v возможным, если ровно (N-t)/2 процесса начинают

алгоритм с входом v?

Каковы бивалентные входные конфигурации алгоритма?

Упражнение 13.12

Докажите, что, если более (N+t)/2 корректных процессов начинают Алгоритм

13.5 с входом v, то в конечном счете принимается v-решение.

Докажите, что если более (N+t)/2 корректных процессов начинают Алгоритм

13.5 с входом v и t < N/5, то v-решение принимается в течение двух раундов.

Раздел 13.5

Упражнение 13.13 Докажите, что при t>N/3 асинхронного t-Византийско-

устойчивого алгоритма вещания не существует.

Упражнение 13.14 Докажите, что в течение выполнения Алгоритма 13.6

корректными процессами посылается самое большее N (3N + 1) сообщений.

14 Отказоустойчивость в Синхронных Системах

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

асинхронных системах. Хотя достижима приемлемая устойчивость, надежные

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

использование таймеров и верхних пределов времени доставки сообщений. В

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

простые, и алгоритмы в большинстве случаев гарантируют верхнюю границу

времени ответа.

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

корректных процессов в замешательство, не посылая информацию;

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

него используется значение по умолчанию, и отправитель становится

подозреваемым в отказе. Таким образом, потерпевшие крах процессы немедленно

обнаруживаются и не представляют никакие проблем в синхронных системах; мы

концентрируемся на Византийских сбоях в этой главе.

В Разделе 14.1 изучается проблема выполнения вещания в синхронных сетях; мы

представим верхнюю границу способности восстановления (t < N/3), а также

два алгоритма с оптимальной способностью восстановления. Алгоритмы

детерминированы и достигают согласия; предполагается, что все процессы

знают, когда начинается вещание. Так как согласие не детерминированно

достижимо в асинхронных системах (Теорема 13.8), то в присутствии сбоев

(даже одиночной аварии), синхронные системы проявляют определенно более

сильную вычислительную мощность чем асинхронные.

Так как авария и отсутствие посылки информации обнаруживаются (и

следовательно "безобидны") в синхронных системах, только Византийские

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

своем собственном состоянии или неправильно пересылая (forwarding)

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

систем может быть далее расширена с помощью методов для установления

подлинности информации. Эти механизмы делают невозможной “ложь”

злонамеренных процессов об информации, полученной от других процессов. Тем

не менее, возможность посылки противоречивой информации о собственном

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

установления подлинности на практике возможна при использовании

криптографических методов.

Алгоритмы в Разделах 14.1 и 14.2 предполагают идеализированную модель

синхронных систем, в которых вычисление идет в импульсах (раундах); см.

Главу 11. Существенно более высокая способность восстановления синхронных

систем по сравнению с асинхронными системами означает невозможность любой 1-

аварийно-устойчивой детерминированной реализации импульсной модели в

асинхронной модели. (Такая реализация, синхронизатор, возможна в надежных

сетях; см. Раздел 11.3).

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

ограниченной задержки (Подраздел 11.1.3), где процессы обладают часами, и

известна верхняя граница задержки сообщений. Реализация возможна, даже если

часы идут неверно и до одной трети процессов злонамеренно отказывают.

Наиболее трудная часть реализации - надежно синхронизировать часы

процессов, проблема, которая будет обсуждена в Разделе 14.3.

14.1 Синхронные Протоколы Решения

В этом разделе мы представим алгоритмы для Византийско-устойчивого вещания

в синхронных (импульсных) сетях; мы начнем с краткого обзора модели

импульсных сетей, которые определены в Разделе 11.1.1. В синхронной сети

процессы функционируют в импульсах, пронумерованных 1, 2, 3, и так далее;

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

локальный алгоритм не завершается. Начальная конфигурация ([pic])

описывается начальными состояниями процессов, и конфигурации после i-го

импульса (обозначается [pic]) также описывается состояниями процессов. В

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

зависимости от своего состояния в [pic]. Впоследствии каждый процесс

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

состояние на основе старого и совокупности сообщений, полученных в

импульсе.

Модель импульса - идеализированная модель синхронных вычислений.

Синхронность отражается в

очевидно одновременном возникновении переходов состояний в процессах; и

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

этого импульса.

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

реалистичных предположений, а именно (1) доступности аппаратных часов и (2)

верхней границы времени доставки сообщений. Возникающая в результате модель

асинхронных сетей ограниченных задержек позволяет очень эффективно

реализовать модель импульса (см. Раздел 11.1.3). Как показано во Главе 11,

одновременность переходов состояний - только видимость. В реализации модели

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

гарантируется своевременное получение всех сообщений. Кроме того,

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

Последнее требование исключает реализации Главы 11 из использования их в

отказоустойчивых прикладных программах, потому что они все страдают

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

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

Разделе 14.3.

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

импульсе, процесс способен определить, что сосед не посылал ему сообщения.

Это свойство, отсутствующее в асинхронных системах, предлагает решение для

проблемы согласия, и даже для проблемы надежного вещания, в синхронных

системах, что мы вскорости и увидим.

В проблеме Византийского-вещания отдельному процессу g, командующему

(general), дается вход [pic], который берется из множества V (обычно {0,

1}). Процессы, отличные от командующего, назвыаются помощниками

(lieutenants). Должны выполняться следующие три требования.

Завершение. Каждый корректный процесс p остановится на значении [pic].

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

значении.

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

останавливаются на [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. Таким

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18