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

                                    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.

                                                                                                                                             o

Лемма 13.38 Если корректный процесс принимает решение, то все корректные процессы принимают решение относительно одного и того же значения.

Доказательство. Чтобы остановиться на v, для v должно быть получено более 2t готовых сообщений, которые включают в себя более t готовых сообщений от корректных процессов; по Лемме 13.37 решения будут согласованными.

Предположим, что корректный процесс p останавливается на v; p получил более 2t готовых сообщений, включая более t сообщений от корректных процессов. Корректный процесс, посылающий готовое сообщение к p, посылает это сообщение всем процессам, что означает, что все корректные процессы получают более t готовых сообщений. Это, в свою очередь, значит, что все корректные процессы посылают готовое сообщение, так что каждый корректный процесс в конечном счете получает N-t > 2t готовых сообщений и принимает решение.

                                                                                                                                             o

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

Доказательство. Если командующий корректен, он не посылает начальных сообщений со значениями, отличными от своего входа. Следовательно, никакой корректный процесс не пошлет отраженных значений, отличных от входа командующего, что означает, что самое большее t процессов посылают неверные отражения. Такого количества неверных отражений недостаточно для того, чтобы корректные процессы посылали готовые сообщения для неверных значений, что означает, что самое большее t процессов посылают неверные готовые сообщения. Такого количества неверных готовых сообщений недостаточно для того, чтобы корректный процесс посылал готовые сообщения или принимал решения, что означает, что никакой корректный процесс не посылает неверного готового сообщения и не принимает неправильного решения.

Если командующий корректен, он посылает начальный голос со своим входом всем корректным процессам, и все корректные процессы “выкрикивают” отражение с этим значением. Следовательно, все корректные процессы получат по крайней мере N-t > (N+t)/2 корректных отраженных сообщений и “выкрикнут” готовое сообщение с корректным значением. Таким образом, все корректные процессы получат по крайней мере N-t > 2t верных готовых сообщений и примут верное решение.                       o

Теорема 13.40 Алгоритм 13.6 - асинхронный t-Византийско-устойчивый алгоритм вещания при t < N/3.

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

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

Раздел 13.1

Упражнение 13.1 Удаление любого из трех требований Определения 13.3 (завершения, соглашения, нетривиальности) для проблемы согласия позволяет принять очень простое решение. Покажите это,  представив три простых решения.

Упражнение 13.2 В доказательстве Леммы 13.6  предполагается, что каждое из  назначений бит N процессам производит возможную входную конфигурацию.

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

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

(2)   Имеются два (известных) процесса  и , и каждая начальная конфигурация удовлетворяет .

(3)   В каждой начальной конфигурации имеется, по крайней мере,  процессов с одним и  тем же входом.

Раздел 13.2

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

Раздел 13.3

Упражнение 13.4 Покажите, что никакой алгоритм для -приблизительного соглашения не может вынести  сбоев.

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

{ (S, r):  and }

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

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

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

Упражнение 13.8 В этом упражнении мы рассматриваем проблему [k, l]-выбора, который обобщает обычную проблему выбора. Проблема требует, чтобы все корректные процессы остановились или на 0 ("побежденный") или на 1 ("избранный"), и что число процессов, которые принимают решение 1 находится между k и l (включительно).

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

(2)   Покажите, что не существует детерминированного 1-аварийно-устойчивого алгоритма для [k, k]-выбора (если 0 < k < N).

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

Раздел 13.4

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

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

Упражнение 13.10 Покажите, что, если все корректные процессы начинают раунд k аварийно-устойчивого алгоритма согласия (Алгоритм 13.3), то все корректные процессы также закончат раунд k.

Упражнение 13.11

(1)   Докажите, что если более (N+t)/2 процессов начинают аварийно-устойчивый алгоритм согласия (Алгоритм 13.3) с входом v, то решение для v принимается за три раунда.

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

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

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

Упражнение 13.12

(1)   Докажите, что, если более (N+t)/2 корректных процессов начинают Алгоритм 13.5 с входом v, то в конечном счете принимается v-решение.

(2)   Докажите, что если более (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, и так далее; каждый процесс может выполнять неограниченное число импульсов, пока его локальный алгоритм не завершается. Начальная конфигурация () описывается начальными состояниями процессов, и конфигурации после i-го импульса (обозначается ) также описывается состояниями процессов. В импульсе i, каждый процесс сначала посылает конечное множество сообщений, в зависимости от своего состояния в . Впоследствии каждый процесс получает все сообщения, посланные ему в этом импульсе, и вычисляет новое состояние на основе старого и совокупности сообщений, полученных в импульсе.

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

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

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

Эти идеализированные предположения могут быть ослаблены до более реалистичных предположений, а именно (1) доступности аппаратных часов и (2) верхней границы времени доставки сообщений. Возникающая в результате модель асинхронных сетей ограниченных задержек позволяет очень эффективно реализовать модель импульса (см. Раздел 11.1.3). Как показано во Главе 11, одновременность переходов состояний - только видимость. В реализации модели переходы состояний могут происходить в разное время, если только гарантируется своевременное получение всех сообщений. Кроме того, реализация должна допускать неограниченное число импульсов процесса. Последнее требование исключает реализации Главы 11 из использования их в отказоустойчивых прикладных программах, потому что они все страдают тупиками, большинство из них даже в случае одиночной потери сообщения. Как уже было упомянуто, к устойчивой реализации модели импульса мы обратимся в Разделе 14.3.

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

В проблеме Византийского-вещания отдельному процессу g, командующему (general), дается вход , который берется из множества V (обычно {0, 1}). Процессы, отличные от командующего, назвыаются помощниками (lieutenants). Должны выполняться следующие три требования.

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

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

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

Можно, кроме этого, требовать одновременности, то есть, что все корректные процессы принимают решение в одном и том же импульсе. Все алгоритмы, обсуждаемые в этом и следующем разделах, удовлетворяют требованию одновременности; см. также Подраздел 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, где сбойная группа обозначена двойным блоком.

Рисунок 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. Противоречие.  o

В доказательстве используется то, что Византийские процессы могут посылать сообщения 1-сценария, даже если они получили только сообщения 0-сценария. То есть, процессы могут "лгать" не только о своем собственном состоянии, но также и о сообщениях, которые они получили. Именно эту возможность можно устранить с помощью установления подлинности, как описано в Разделе 14.2; это ведет к способности восстановления N-1.

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

В этом подразделе будет показано, что верхняя граница способности восстановления, показанная в предыдущем подразделе, точна. Кроме того, противопоставляя ситуации в асинхронных сетях, максимальная способность восстановления достижима при использовании детерминированных алгоритмов. Мы представляем рекурсивный алгоритм, также Пиза и других [PSL80], который допускает t Византийских отказа при t < N/3. Способность восстановления - параметр алгоритма.

Алгоритм Broadcast(N, 0) дан как Алгоритм 14.2; он не допускает отказов (t = 0), и если отказов не происходит, все процессы останавливаются на входе командующего в 1 импульсе. Если отказ происходит, соглашение может быть нарушено, но завершение (и одновременность), тем не менее, гарантируется.

Импульс

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.

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