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

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

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

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

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

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

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

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