Проблема византийских генералов — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
[[Категория:Параллельное программирование]] | [[Категория:Параллельное программирование]] | ||
== Проблема двух генералов == | == Проблема двух генералов == | ||
Текущая версия на 19:15, 4 сентября 2022
Проблема двух генералов
Проблема двух генералов: двум процессам в синхронной системе надо прийти к консенсусу по ненадёжному каналу связи. Например, генералы хотят согласовать время атаки, а гонца с сообщением могут перехватить, хоть мы и знаем, с какой скоростью он бегает.
Эта проблема не решается: одного сообщения мало (мы можем даже узнать о перехвате, но не знаем о его сообщении), нужно подтверждение, потом подтверждение подтверждения...
Аналогично не решается для большего числа процессов: нам для консенсуса нужны хоть какие-то относительно надёжные каналы.
Византийская ошибка
Это самый суровый вид ошибок: у нас имеется $f$ византийских процессов, которые могут отсылать какие угодно сообщения другим процессам. Могут эмулировать корректное поведение, могут "терять" сообщения или не отвечать, могут посылать заведомо некорректные сообщения, могут пытаться сломать систему. Но не могут подделывать сообщения "от имени" других процессов, то есть автора сообщения мы всегда гарантированно знаем.
Задача: могут ли $N$ процессов, среди которых не более $f$ византийских, прийти к консенсусу? Предполагаем надёжные каналы связи. Нас не интересует, какое решение примут византийские процессы (они творят, что хотят), только нормальные.
