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

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

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

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

теореме.

Теорема 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].

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