Теорема Фишера-Линча-Патерсона (FLP)
Версия от 15:52, 3 июня 2019; Yeputons (обсуждение | вклад)
Теорема Фишера, Линча и Патерсона (FLP, 1985 год) невозможно достичь даже необоснованного консенсуса $N>2$ процессами даже на одном бите при следующих условиях:
- Алгоритм должен завершиться за конечное время.
- Один из узлов может отказать
- Система асинхронна
- Алгоритм должен быть детерминирован.
Если отказов нет, есть простой алгоритм. Если система синхронна, то есть консенсус в синхронных системах. Если разрешаем недетерминизм, то есть алгоритм Бен-Ора.
- TODO: доказательство из презентации Елизарова.
- Инфо: http://bailonga.es/tpmtp/lecture09.pdf + презентация Р.Елизарова
- Инфо: https://github.com/volhovm/study-notes/blob/master/parallel_programming/parallel_programming.org
