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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 3 промежуточные версии 2 участников)
Строка 1: Строка 1:
 +
[[Категория: Параллельное программирование]]
 
Можно доказать, например, что при ''n'' = 3, ''f'' = 1 (три процесса, из них один византийский) консенсус [[Проблема византийских генералов|византийских генералов]] невозможен.
 
Можно доказать, например, что при ''n'' = 3, ''f'' = 1 (три процесса, из них один византийский) консенсус [[Проблема византийских генералов|византийских генералов]] невозможен.
  
Строка 5: Строка 6:
 
Пусть каждому процессу подаётся число 0 или 1 на вход (могут быть разными на разных процессах). Задача - прийти к нетривиальному обоснованному консенсусу всем работающим процессам на одном значении, которое было дано на вход хотя бы одному невизантийскому процессу.
 
Пусть каждому процессу подаётся число 0 или 1 на вход (могут быть разными на разных процессах). Задача - прийти к нетривиальному обоснованному консенсусу всем работающим процессам на одном значении, которое было дано на вход хотя бы одному невизантийскому процессу.
  
[[Файл:byzantine.png|frame|right]] Предположим обратное. Пусть существует алгоритм консенсуса. Тогда расставим 4 ноды с этим алгоритмом, подадим верхним на вход 0, и нижним = 1.
+
Предположим обратное. Пусть существует алгоритм консенсуса. Тогда алгоритм — это код, которому требуется дать два канала связи с оставшимися двумя процессами.
 +
Сделаем страшное и странное: запустим 4 процесса с этим алгоритмом так, как на картинке, и подадим верхним на вход 0, а нижним 1.
 +
Они будут как-то работать, посмотри, к какому выводу могут прийти эти процессы (если вообще придут).
  
Тогда если считать 2 верхних процесса рабочими, а 2 нижних - одним сбойным, верхние обязаны прийти к консенсусу на 0. Аналогично, если считать 2 нижних процесса рабочими, а 2 верхних - одним сбойным - нижние приходят к консенсусу на 1.
+
[[Файл:byzantine.png]]
  
И если мы считаем рабочими 2 правых, а 2 левых - одним сбойным(ведущим себя как пара из верхнего рабочего и нижнего рабочего) - то верхний правый придет к консенсусу на 0 вместе с воображаемым верхним соседом, а нижний правый - к консенсусу на 1 с воображаемым нижним соседом. Fail.
+
Посмотрим на картинку одним способом: как будто два верхних процесса — это обычные процессы, а нижняя половина — это византийских процесс (у него два канала связи с нормальными, он внутри что-то как-то делает и с ними общается, выдавая чушь).
 +
Тогда верхние процессы обязаны независимо от происходящего в нижней половине прийти к консенсусу на 0.
 +
Аналогично, если считать 2 нижних процесса рабочими, а 2 верхних — одним сбойным, то нижние приходят к консенсусу на 1.
 +
То есть все процессы завершились и посчитали, что консенсус есть.
 +
 
 +
А теперь если мы считаем рабочими 2 правых, а 2 левых одним сбойным (ведущим себя как пара из верхнего рабочего и нижнего рабочего), то два правых должны прийти к консенсусу.
 +
Но вместо этого верхний правый придет к консенсусу на 0 вместе с воображаемым верхним соседом, а нижний правый к консенсусу на 1 с воображаемым нижним соседом.
 +
Противоречие.
  
 
Поэтому такого алгоритма нет, и консенсус при N=3 и f=1 невозможен.
 
Поэтому такого алгоритма нет, и консенсус при N=3 и f=1 невозможен.

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

Можно доказать, например, что при n = 3, f = 1 (три процесса, из них один византийский) консенсус византийских генералов невозможен.

Доказательство от Елизарова:

Пусть каждому процессу подаётся число 0 или 1 на вход (могут быть разными на разных процессах). Задача - прийти к нетривиальному обоснованному консенсусу всем работающим процессам на одном значении, которое было дано на вход хотя бы одному невизантийскому процессу.

Предположим обратное. Пусть существует алгоритм консенсуса. Тогда алгоритм — это код, которому требуется дать два канала связи с оставшимися двумя процессами. Сделаем страшное и странное: запустим 4 процесса с этим алгоритмом так, как на картинке, и подадим верхним на вход 0, а нижним — 1. Они будут как-то работать, посмотри, к какому выводу могут прийти эти процессы (если вообще придут).

Byzantine.png

Посмотрим на картинку одним способом: как будто два верхних процесса — это обычные процессы, а нижняя половина — это византийских процесс (у него два канала связи с нормальными, он внутри что-то как-то делает и с ними общается, выдавая чушь). Тогда верхние процессы обязаны независимо от происходящего в нижней половине прийти к консенсусу на 0. Аналогично, если считать 2 нижних процесса рабочими, а 2 верхних — одним сбойным, то нижние приходят к консенсусу на 1. То есть все процессы завершились и посчитали, что консенсус есть.

А теперь если мы считаем рабочими 2 правых, а 2 левых — одним сбойным (ведущим себя как пара из верхнего рабочего и нижнего рабочего), то два правых должны прийти к консенсусу. Но вместо этого верхний правый придет к консенсусу на 0 вместе с воображаемым верхним соседом, а нижний правый — к консенсусу на 1 с воображаемым нижним соседом. Противоречие.

Поэтому такого алгоритма нет, и консенсус при N=3 и f=1 невозможен.