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

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

Текущая версия на 18:48, 3 июня 2019

Проблема двух генералов[править]

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

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

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

Византийская ошибка[править]

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

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