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