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