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

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

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

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

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

Доказательство

Из презентации Р. Елизарова.

От противного: пусть есть такой алгоритм, тогда мы проанализируем варианты его исполнения, подстроим порядок доставки сообщений (без откладывания сообщений бесконечно далеко) и получим противоречие с нетривиальностью консенсуса.

Модель

Определение:
Процесс — это детерминированный автомат, который может выполнять три операции:
  • receive() : msg — бесконечная блокировка до получения ближайшего сообщения. Так как система асинхронна, возможности "посмотреть следующее сообщение" или таймаутов нет.
  • send(msg) — отправка сообщения другому процессу. Гарантируется, что сообщение дойдёт получателю за конечное время, но это время может быть сколь угодно большим.
  • decided(value) — процесс принял решение value. Решение процесс может принять только один раз, но после этого он может продолжить выполняться и помогать остальным процессам.
Заметим, что так как нет "времени", можно считать все переходы в процессе мгновенными.

Для доказательства от противного у нас есть такой алгоритм для процессов, что все они вызывают decided(value) с одинаковым значением через конечное время, независимо от того, как система задерживает сообщения.

Определение:
Конфигурация — это состояния всех процессов плюс все сообщения в пути (которые отправили, но ещё не доставили).

В начальной конфигурация у каждого процесса может быть сколько угодно входных данных и даже своя программа.

Определение:
Шаг из одной конфигурации в другую — это приём какого-то сообщения процессом (событие) и последовавшие за этим внутренние действия процесса до следующего receive(). Эти действия однозначно определяются предыдущей конфигурацией и событием.


Определение:
Исполнение — это бесконечная цепочка шагов из начальной конфигурации. Бесконечная, потому что процессы могут выполняться и после принятия решений.


Определение:
Отказавший процесс — это процесс, который делает только конечное количество шагов в исполнении. Такой в системе может быть максимум один (это более сильное условие, чем если может много процессов отказывать).


Также гарантируется, что в любом исполнении любое сообщение, предназначенное не отказавшему процессу, обрабатывается через конечное число шагов. Другими словами, сообщения не теряются.

Валентность

Начальная бивалентная конфигурация

Цепочка бивалентных конфигураций

Ссылки

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