Невозможность византийского консенсуса

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Можно доказать, например, что при n = 3, f = 1 (три процесса, из них один византийский) консенсус византийских генералов невозможен.

Доказательство от Елизарова:

Пусть каждому процессу подаётся число 0 или 1 на вход (могут быть разными на разных процессах). Задача - прийти к нетривиальному обоснованному консенсусу всем работающим процессам на одном значении, которое было дано на вход хотя бы одному невизантийскому процессу.

Предположим обратное. Пусть существует алгоритм консенсуса. Тогда алгоритм — это код, которому требуется дать два канала связи с оставшимися двумя процессами. Сделаем страшное и странное: запустим 4 процесса с этим алгоритмом так, как на картинке, и подадим верхним на вход 0, а нижним — 1. Они будут как-то работать, посмотри, к какому выводу могут прийти эти процессы (если вообще придут).

Посмотрим на картинку одним способом: как будто два верхних процесса — это обычные процессы, а нижняя половина — это византийских процесс (у него два канала связи с нормальными, он внутри что-то как-то делает и с ними общается, выдавая чушь). Тогда верхние процессы обязаны независимо от происходящего в нижней половине прийти к консенсусу на 0. Аналогично, если считать 2 нижних процесса рабочими, а 2 верхних — одним сбойным, то нижние приходят к консенсусу на 1. То есть все процессы завершились и посчитали, что консенсус есть.

А теперь если мы считаем рабочими 2 правых, а 2 левых — одним сбойным (ведущим себя как пара из верхнего рабочего и нижнего рабочего), то два правых должны прийти к консенсусу. Но вместо этого верхний правый придет к консенсусу на 0 вместе с воображаемым верхним соседом, а нижний правый — к консенсусу на 1 с воображаемым нижним соседом. Противоречие.

Поэтому такого алгоритма нет, и консенсус при N=3 и f=1 невозможен.