Задача византийских генералов: согласование при отказах

Задача византийских генералов объясняет, как участникам распределённой системы согласовать действие, если некоторые из них могут передавать разные или ложные сообщения. Один сервер способен сообщить двум соседям несовместимые сведения, а исправные участники заранее не знают, кому доверять.
В калькуляторе выберите число возможных неисправных участников: он покажет минимальный размер группы для классической модели без пересылаемых подписей. Ниже разберём, откуда берётся граница и почему её нельзя переносить на любую сеть без проверки условий.
Приказ, которому нельзя просто поверить
Представим армию, разделённую на отряды вокруг города. Командир должен передать лейтенантам приказ: атаковать или отступить. Связь идёт через сообщения. Некоторые участники могут быть неисправны: они способны молчать, лгать или отправлять разным получателям разные приказы. Остальные выполняют протокол точно, но не знают, кто неисправен.
Требования к постановке командования два. Во-первых, все исправные лейтенанты должны выбрать одинаковое действие. Во-вторых, если командир исправен, они должны выполнить именно его приказ. Второе условие исключает бесполезный протокол «всегда отступать». Если командир неисправен, результат не обязан совпасть с его намерением: у него может не быть единого намерения вообще.
Метафору и её формальную постановку описали Лесли Лэмпорт, Роберт Шостак и Маршалл Пиз в статье 1982 года. В вычислительной системе генералам соответствуют процессы или серверы, а приказу - значение, которое нужно согласовать. Речь идёт о модели связи, а не о реконструкции истории Византии.
Чем византийский отказ отличается от остановки
Остановившийся сервер просто перестаёт отвечать. Византийский участник может действовать произвольно: отвечать неверно, нарушать порядок шагов и отправлять противоречивые данные. Причиной может быть как атака, так и программная ошибка. Слово «предатель» в учебной истории описывает поведение, а не обязательно злой умысел.
Проверить правильность такого участника одним запросом нельзя. Получив ответ «атака», лейтенант не знает, получил ли сосед тот же ответ. Даже большинство только среди непосредственных ответов не решает задачу автоматически: неисправные узлы могут менять ответы в зависимости от адресата.
Это отличие существенно при выборе протокола. Например, Raft рассчитан на остановку узлов, а не на произвольное злонамеренное поведение. Само наличие лидера и голосования большинством ещё не делает систему византийски отказоустойчивой.
Почему трёх участников недостаточно
Пусть есть командир и два лейтенанта; допускается один неисправный участник. Командир может отправить первому «атаковать», а второму «отступить». После обмена сообщениями первый видит свой приказ и противоположное утверждение соседа. Он не знает, врёт ли командир или сосед.
Рассмотрим ситуацию, которая для первого выглядит так же: командир исправен и действительно приказал атаковать, а второй лейтенант солгал об отходе. Условие верности приказу заставляет первого атаковать. Симметричное рассуждение для второго лейтенанта заставляет его отступить в неотличимой для него ситуации. При неисправном командире решения могут разойтись.
Это не недостаток конкретного правила голосования: в классической модели устных сообщений доказана невозможность гарантированного решения при трёх участниках и одном неисправном. Исправный получатель знает, кто прислал ему сообщение напрямую, но не может проверить исходное содержание чужого сообщения, пересказанного неисправным посредником.
Граница n ≥ 3f + 1
Обозначим через общее число участников, включая командира, а через - верхнюю границу неисправных. Для синхронной модели устных сообщений гарантированное решение возможно при условии
Так, для одного возможного отказа нужны четыре участника, для двух - семь. При формула даёт один участник: это вырожденный случай без лейтенантов. Граница говорит о наихудшем допустимом поведении, а не предсказывает, что группа из трёх обязательно ошибётся при каждом обмене.

В модели известны отправители непосредственных сообщений, каждое отправленное сообщение доставляется корректно, а отсутствие сообщения обнаруживается и заменяется заранее выбранным значением. Это требует предположений о времени и связи. Формула не утверждает, что любые четыре сервера и произвольный алгоритм автоматически выдержат атаку.
Как работает обмен OM(1)
Алгоритм устных сообщений рекурсивно пересылает сведения о приказах. При сначала командир отправляет приказ каждому лейтенанту. Затем каждый лейтенант передаёт остальным то, что получил от командира. В конце каждый применяет заранее согласованное правило большинства к своему непосредственному приказу и пересказам двух соседей.
Возьмём пример из ролика: командир неисправен и отправил лейтенантам А и Б приказ «атака», а В - «отход». Все три лейтенанта исправны. После полного обмена каждый видит один непосредственный приказ и два пересказа. У каждого набор содержит две атаки и один отход, поэтому все трое выбирают атаку. Они не обязаны выявить неисправного командира, чтобы согласовать решение.
Другой случай: командир исправен и приказал атаку, а один лейтенант пересказывает отход. Каждый исправный лейтенант получает непосредственную атаку и ещё одну атаку от исправного соседа. Не более одного значения может быть ложным; большинство снова равно атаке. Именно эти разные случаи нужно проверять при доказательстве, а не только один удачный пример. Полезно записать сообщения в таблицу: строка - получатель, столбец - источник значения. Промежуточные состояния помогают разбирать и другие алгоритмы, например алгоритм Дейкстры.
При общем каждый уровень рекурсии учитывает на одного возможного неисправного участника меньше. Для требуется синхронных раундов. Число сообщений быстро растёт; это объясняет, почему практическим системам нужны более экономные протоколы и чёткие предположения о сети.
Кворумы и практические протоколы
В системах с часто используют кворумы размера . Два таких множества пересекаются минимум в участнике: сумма их размеров минус размер всей группы равна . Поскольку неисправных максимум , в пересечении есть хотя бы один исправный участник.
Это важный строительный блок безопасности: при подходящих правилах исправный участник не подтвердит два конфликтующих решения для одной и той же ситуации. Но одно только пересечение не задаёт весь протокол: нужны правила голосования, перехода между лидерами, проверки сообщений и обработки задержек.
Пример практического протокола - PBFT Кастро и Лисков. Его реплики согласуют порядок операций, используя несколько фаз обмена и аутентификацию. Такое согласование может служить частью надёжного хранения данных, где отдельно рассматривают и ACID-свойства транзакций. Безопасность и продвижение зависят от разных условий; нельзя считать задержанную сеть мгновенно исправной лишь потому, что формула числа реплик выполнена.
Подписи, время и пределы гарантий
Цифровая подпись позволяет проверить происхождение и целостность подписанного сообщения при предположении, что ключ исправного участника не скомпрометирован. Если переслать подписанный приказ, посредник не сможет незаметно заменить его содержимое. Но сам неисправный командир по-прежнему может подписать два разных приказа: подпись не превращает ложь в правду. Криптографические механизмы также требуют корректного управления ключами; обмен секретами - отдельная задача, связанная, например, с алгоритмом Диффи - Хеллмана.
В модели подписанных сообщений результат отличается от границы устных сообщений. Поэтому утверждение «всегда необходимы ровно узлов» слишком широко: сначала нужно назвать модель, цели и допущения.
Время тоже важно. Безопасность означает отсутствие запрещённого расхождения решений; живучесть - возможность в итоге принять решение. Результат Фишера, Линч и Патерсона показывает: в полностью асинхронной модели детерминированный протокол консенсуса не гарантирует завершение во всех допустимых исполнениях даже при одном возможном остановившемся процессе. Это не запрет на практические системы: они используют дополнительные предположения о времени или вероятностные механизмы.
Частые ошибки
- Не считать командира в . В приведённой формуле он входит в общее число участников.
- Объявлять любой неверный ответ атакой. Византийская модель допускает и ошибки без злого умысла.
- Принимать пример за доказательство. Протокол обязан работать при любом допустимом расположении неисправных участников и поведении в пределах модели.
- Считать подпись доказательством истинности. Она подтверждает происхождение сообщения, но подписант может сообщить ложь.
- Переносить границу на все протоколы. Подписи, модель времени, состав участников и нужные гарантии меняют постановку.
FAQ
Сколько участников нужно для двух византийских отказов?
В классической синхронной модели устных сообщений минимум семь: . Это общее число, включая командира.
Обязательно ли обнаруживать неисправного участника?
Нет. Задача требует согласованного решения исправных участников и выполнения приказа исправного командира, а не обязательной идентификации виновного.
Одинаковы ли византийский консенсус и блокчейн?
Нет. Византийское согласование - семейство задач о согласии при произвольных отказах; блокчейн - способ организации данных и протокола, который может использовать разные механизмы согласования и предположения.
Коротко
Задача византийских генералов показывает, что противоречивые сообщения делают согласование сложнее простого ожидания большинства. В классической синхронной модели устных сообщений произвольных отказов выдерживает протокол при ; подписи и другие модели меняют условия. Для оценки реальной системы всегда проверяют и алгоритм, и сеть, и смысл требуемых гарантий.
Читайте также

Абсолютно неупругий удар: сохранение импульса
Как найти скорость тел после абсолютно неупругого удара, применить закон сохранения импульса и вычислить потерю кинетической энергии на понятных примерах с формулами.

Абсолютное и избыточное давление: формулы и вакуум
Абсолютное и избыточное давление, разрежение и вакуум: как выбрать начало отсчёта, перевести показания манометра и решить задачи с примерами в килопаскалях.

АЦП последовательного приближения: схема и принцип работы
Разберите схему АЦП последовательного приближения: как компаратор, ЦАП и регистр определяют код по битам, как вычислить шаг квантования и оценить погрешность.

Аддитивная и мультипликативная погрешность
Аддитивная и мультипликативная погрешность прибора: формулы сдвига нуля и ошибки масштаба, пример расчёта показания и поправки, калибровка прибора и пределы линейной модели.

Адиабатический процесс: уравнение Пуассона и расчёт
Уравнение Пуассона для адиабатического процесса: вывод через первое начало термодинамики, связь давления, объёма и температуры, пример и границы применения.

Адресация: прямая, косвенная и непосредственная
Разбираем прямую, косвенную и непосредственную адресацию операндов на одном примере памяти: как найти значение, посчитать чтения и не перепутать адрес с данными.