Пусть каждому процессу подаётся число 0 или 1 на вход (могут быть разными на разных процессах). Задача - прийти к нетривиальному обоснованному консенсусу всем работающим процессам на одном значении, которое было дано на вход хотя бы одному невизантийскому процессу.
[[Файл:byzantine.png|frame|right]] Предположим обратное. Пусть существует алгоритм консенсуса. Тогда расставим алгоритм — это код, которому требуется дать два канала связи с оставшимися двумя процессами.Сделаем страшное и странное: запустим 4 ноды процесса с этим алгоритмомтак, как на картинке, и подадим верхним на вход 0, и а нижним = — 1.Они будут как-то работать, посмотри, к какому выводу могут прийти эти процессы (если вообще придут).
Тогда если считать 2 верхних процесса рабочими, а 2 нижних - одним сбойным, верхние обязаны прийти к консенсусу на 0. Аналогично, если считать 2 нижних процесса рабочими, а 2 верхних - одним сбойным - нижние приходят к консенсусу на 1[[Файл:byzantine.png]]
И Посмотрим на картинку одним способом: как будто два верхних процесса — это обычные процессы, а нижняя половина — это византийских процесс (у него два канала связи с нормальными, он внутри что-то как-то делает и с ними общается, выдавая чушь).Тогда верхние процессы обязаны независимо от происходящего в нижней половине прийти к консенсусу на 0.Аналогично, если считать 2 нижних процесса рабочими, а 2 верхних — одним сбойным, то нижние приходят к консенсусу на 1.То есть все процессы завершились и посчитали, что консенсус есть. А теперь если мы считаем рабочими 2 правых, а 2 левых - — одним сбойным(ведущим себя как пара из верхнего рабочего и нижнего рабочего) - , то два правых должны прийти к консенсусу.Но вместо этого верхний правый придет к консенсусу на 0 вместе с воображаемым верхним соседом, а нижний правый - — к консенсусу на 1 с воображаемым нижним соседом. FailПротиворечие.
Поэтому такого алгоритма нет, и консенсус при N=3 и f=1 невозможен.
