Проблема византийских генералов

НЕТ ВОЙНЕ

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

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

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

Проблема двух генералов

Проблема двух генералов: двум процессам в синхронной системе надо прийти к консенсусу по ненадёжному каналу связи. Например, генералы хотят согласовать время атаки, а гонца с сообщением могут перехватить, хоть мы и знаем, с какой скоростью он бегает.

Эта проблема не решается: одного сообщения мало (мы можем даже узнать о перехвате, но не знаем о его сообщении), нужно подтверждение, потом подтверждение подтверждения...

Аналогично не решается для большего числа процессов: нам для консенсуса нужны хоть какие-то относительно надёжные каналы.

Византийская ошибка

Это самый суровый вид ошибок: у нас имеется $f$ византийских процессов, которые могут отсылать какие угодно сообщения другим процессам. Могут эмулировать корректное поведение, могут "терять" сообщения или не отвечать, могут посылать заведомо некорректные сообщения, могут пытаться сломать систему. Но не могут подделывать сообщения "от имени" других процессов, то есть автора сообщения мы всегда гарантированно знаем.

Задача: могут ли $N$ процессов, среди которых не более $f$ византийских, прийти к консенсусу? Предполагаем надёжные каналы связи. Нас не интересует, какое решение примут византийские процессы (они творят, что хотят), только нормальные.