#Византийская ошибка (byzantine failure) (сломавшийся процесс может слать любой мусор)
Теорема FLP (ФишерИерархия ошибок строится по тому, что более сильные ошибки могут имитировать менее сильные -Линчвизантийская ошибка имитирует поведение при ненадежной доставке сообщений, ненадежная доставка может имитировать полный отказ канала, а отказ всех каналов к узлу -Патерсон):отказ узла.
Для Невозможность консенсуса в асинхронной системы N потоков системе с хотя бы одним сбойным потоком нельзя построить решение задачи консенсуса.отказом узла (FLP)(Фишер-Линч-Патерсон)
Разрешением утверждения, которое постулируется в теореме выше, могут стать следующие изменения4 требования/предпосылки:* Сделать сеть синхронной Система асинхронна (ограничить время нет предела времени доставки сообщенийсообщения)* Сделать алгоритм недетерминированным (случайнымОдин) узел может отказать (crash)* Ослабить требования при которых в алгоритме обязан быть прогресс (т.е. он обязан завершаться)Консенсус надо достичь за конечное время* Детерминированный алгоритм консенсуса
ТЕОРЕМА: Невозможно достичь консенсуса N процессам, даже на множестве значений из двух элементов 0 и 1
Соответственно, можно придти к консенсусу, если:
* сделать сеть синхронной (ограничить время доставки сообщений)
* сделать алгоритм недетерминированным (случайным)
* ослабить требования при которых в алгоритме обязан быть прогресс (т.е. он обязан завершаться)
TODO: доказательство из презентации Елизарова.
Инфо: http://bailonga.es/tpmtp/lecture09.pdf + презентация Р.Елизарова
