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

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

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

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

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

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

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

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