Невозможность Теорема Фишера, Линча и Патерсона (FLP, 1985 год) невозможно достичь даже необоснованного [[Консенсус в распределённой системе|консенсуса в асинхронной системе]] с $N>2$ процессами даже на одном бите при следующих условиях:* Алгоритм должен завершиться за конечное время.* Один из узлов [[Иерархия ошибок в распределённых системах|отказом узламожет отказать]] при детерминированном алгоритме (FLP)(Фишер-Линч-Патерсон)* Система [[Асинхронные и синхронные распределённые системы|асинхронна]]* Алгоритм должен быть детерминирован.
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
