Проблема византийских генералов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 2 промежуточные версии 2 участников)
Строка 2: Строка 2:
 
== Проблема двух генералов ==
 
== Проблема двух генералов ==
 
'''Проблема двух генералов''': двум процессам в синхронной системе надо прийти к консенсусу по ненадёжному каналу связи.
 
'''Проблема двух генералов''': двум процессам в синхронной системе надо прийти к консенсусу по ненадёжному каналу связи.
Например, генералы хотят согласовать время атаки, а гонца с сообщением могут перехватить.
+
Например, генералы хотят согласовать время атаки, а гонца с сообщением могут перехватить, хоть мы и знаем, с какой скоростью он бегает.
  
 
Эта проблема не решается: одного сообщения мало (мы можем даже узнать о перехвате, но не знаем о его сообщении), нужно подтверждение, потом подтверждение подтверждения...
 
Эта проблема не решается: одного сообщения мало (мы можем даже узнать о перехвате, но не знаем о его сообщении), нужно подтверждение, потом подтверждение подтверждения...

Текущая версия на 19:15, 4 сентября 2022

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

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

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

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

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

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

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