Теорема Фишера-Линча-Патерсона (FLP)

Материал из Викиконспекты
Перейти к: навигация, поиск

Невозможность консенсуса в асинхронной системе с отказом узла при детерминированном алгоритме (FLP)(Фишер-Линч-Патерсон)

4 требования/предпосылки:

  • Система асинхронна (нет предела времени доставки сообщения)
  • (Один) узел может отказать (crash)
  • Консенсус надо достичь за конечное время
  • Детерминированный алгоритм консенсуса

ТЕОРЕМА: Невозможно достичь консенсуса N процессам, даже на множестве значений из двух элементов 0 и 1

Соответственно, можно придти к консенсусу, если:

  • сделать сеть синхронной (ограничить время доставки сообщений)
  • сделать алгоритм недетерминированным (случайным)
  • ослабить требования при которых в алгоритме обязан быть прогресс (т.е. он обязан завершаться)

TODO: доказательство из презентации Елизарова. Инфо: http://bailonga.es/tpmtp/lecture09.pdf + презентация Р.Елизарова