Быстрый поиск

Упражнение 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, 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