Приведите детерминированные, 1-аварийно устойчивые протоколы согласия для каждого из следующих ограничений на входные значения.
(1) Дано, что четность входа является четной (то есть, имеется четное число процессов со входом 1) в каждой начальной конфигурации.
(2) Имеются два (известных) процесса и , и каждая начальная конфигурация удовлетворяет .
(3) В каждой начальной конфигурации имеется, по крайней мере, процессов с одним и тем же входом.
Упражнение 13.3 Покажите, что при t-изначально-мертвых-устойчивого алгоритма выбора нет.
Упражнение 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.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.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.