Теорема Фишера-Линча-Патерсона (FLP) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
−
Невозможность [[Консенсус в распределённой системе|консенсуса в асинхронной системе]] с [[Иерархия ошибок в распределённых системах|отказом узла]] при детерминированном алгоритме (FLP)(Фишер-Линч-Патерсон)
+
Теорема Фишера, Линча и Патерсона (FLP, 1985 год) невозможно достичь даже необоснованного [[Консенсус в распределённой системе|консенсуса]] $N>2$ процессами даже на одном бите при следующих условиях:
 +
* Алгоритм должен завершиться за конечное время.
 +
* Один из узлов [[Иерархия ошибок в распределённых системах|может отказать]]
 +
* Система [[Асинхронные и синхронные распределённые системы|асинхронна]]
 +
* Алгоритм должен быть детерминирован.
  
−
4 требования/предпосылки:
+
Если отказов нет, есть [[Консенсус в распределённой системе#Решение при отсутствии отказов|простой алгоритм]].
−
* Система асинхронна (нет предела времени доставки сообщения)
+
Если система синхронна, то есть [[консенсус в синхронных системах]].
−
* (Один) узел может отказать (crash)
+
Если разрешаем недетерминизм, то есть [[алгоритм Бен-Ора]].
−
* Консенсус надо достичь за конечное время
 
−
* Детерминированный алгоритм консенсуса
 
  
−
'''ТЕОРЕМА''': Невозможно достичь консенсуса N процессам, даже на множестве значений из двух элементов 0 и 1
+
* TODO: доказательство из презентации Елизарова.
−
 
+
* Инфо: http://bailonga.es/tpmtp/lecture09.pdf + презентация Р.Елизарова
−
Соответственно, можно придти к консенсусу, если:
+
* Инфо: https://github.com/volhovm/study-notes/blob/master/parallel_programming/parallel_programming.org
−
* сделать сеть синхронной (ограничить время доставки сообщений)
 
−
* сделать алгоритм недетерминированным (случайным)
 
−
* ослабить требования при которых в алгоритме обязан быть прогресс (т.е. он обязан завершаться)
 
−
 
 
−
TODO: доказательство из презентации Елизарова.
 
−
Инфо: http://bailonga.es/tpmtp/lecture09.pdf + презентация Р.Елизарова
 

Версия 15:52, 3 июня 2019

Теорема Фишера, Линча и Патерсона (FLP, 1985 год) невозможно достичь даже необоснованного консенсуса $N>2$ процессами даже на одном бите при следующих условиях:

  • Алгоритм должен завершиться за конечное время.
  • Один из узлов может отказать
  • Система асинхронна
  • Алгоритм должен быть детерминирован.

Если отказов нет, есть простой алгоритм. Если система синхронна, то есть консенсус в синхронных системах. Если разрешаем недетерминизм, то есть алгоритм Бен-Ора.

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Фишера-Линча-Патерсона_(FLP)&oldid=71468»