Изменения

Перейти к: навигация, поиск

Теорема Фишера-Линча-Патерсона (FLP)

5837 байт добавлено, 08:49, 4 июня 2019
Нет описания правки
[[Категория:Параллельное программирование]]Теорема Фишера, Линча и Патерсона (FLP, 1985 год) : невозможно достичь даже необоснованного [[Консенсус в распределённой системе|консенсуса]] $N>2$ процессами даже на одном бите при следующих условиях:
* Алгоритм должен завершиться за конечное время.
* Один из узлов [[Иерархия ошибок в распределённых системах|может отказать]]
* Алгоритм должен быть детерминирован.
Если разрешаем незавершаемость в случае отказов, есть [[Paxos]] и [[Raft]].
Если отказов нет, есть [[Консенсус в распределённой системе#Решение при отсутствии отказов|простой алгоритм]].
Если система синхронна, то есть [[консенсус в синхронных системах]].
Если разрешаем недетерминизм, то есть [[алгоритм Бен-Ора]].
 
При этом даже если разрешить одновременную посылку сообщения сразу нескольким процессам (как в [[Общий порядок сообщений|общем порядке сообщений]]) и тем самым запретить процессу падать при массовой рассылке сообщений, лучше не станет: нет гарантии, в каком порядке и как скоро эти сообщения будут получены и обработаны получателями.
А вот если какую-нибудь гарантию дадим, то получаем [[Переформулировки консенсуса в распределённой системе#Terminating Reliable Broadcast (TRB)|TLB]], из которого сразу выводится консенсус.
== Доказательство ==
==== Шаг 2: существование соседних разновалентных конфигураций ====
 
Теперь мы хотим найти такие две соседние конфигурации $C_0, C_1 \in C$ (отличающиеся переходом $e'(C_0)=C_1$), что $D_0=e(C_0) \in D$ является 0-валентной, а $D_1=e(C_1)$ — 1-валентной (или наоборот).
Это можно сделать, если взять в $D$ конфигурацию $e(C_1)$, отличающуюся от валентности $e(G)$, а дальше посмотреть на цепочку конфигураций между $G$ и $e(C_1)$ и найти момент смены валентности.
 
Начнём искать, более строго. Не теряя общности можем сказать, что $e(G)\in D$ является 0-валентной (иначе повторим доказательство шага).
По предыдущему шагу найдём в $D$ 1-валентную конфигурацию $D_1=e(C_1)\in D$.
Конфигурация $C_1$ получена какой-то конечной непустой цепочкой сообщений $x_1, x_2, \dots, x_k$.
Будем по очереди убирать по одному сообщения с конца и смотреть на валентность конфигураций $e(x_{k-1}(\dots(x_1(G))\dots))$, $e(x_{k-2}(\dots(x_1(G))\dots))$, \dots — в какой-то момент она сменится с единицы на ноль (например, при пустой цепочке, т.е. при рассмотрении $e(G)\in D$).
Тогда мы как раз нашли искомую пару соседей $C_0$ и $C_1$ таких, что $e(C_0)$ и $e(C_1)$ разной валентности.
==== Шаг 3: разбор случаев ====
Теперь у нас, помимо конфигурации $C$ и события $e$, есть некоторое событие $e'$ и конфигурации $C_0$ и $C_1$, причём:
* $e(C_0)=D_0$ является 0-валентной, а $e(C_1)=D_1$ является 1-валентной (или наоборот, повторим доказательство)
* $e'(C_0)=C_1$
 
Разберём два случая, в зависимости от того, одному процессу приходят $e$ и $e'$ или разным.
 
===== Разным =====
Пусть $proc(e)\neq proc(e')$ (т.е. эти события в разных процессах).
Тогда нам всё равно, в каком порядке их обрабатывать, т.е. $e'(e(C_0))=e(e'(C_0))=e(C_1)=D_1$:
 
[[Файл:Distributed-flp-proof-case1.png|300px]]
 
Мы знаем, что $D_1$ является 1-валентной. Но так как они достижима из $D_0$, то она также является и 0-валентной, противоречие.
 
===== Одному =====
Пусть $proc(e) = proc(e') = p$ (т.е. это два сообщения одному и тому же процессу).
Тогда рассмотрим цепочку шагов $\sigma$ от состояния $C_0$, в которой процесс $p$ вообще отказал вместо обработки сообщений.
Тогда остальные процессы в этой цепочке пришли к какому-то решению в конфигурации $A=\sigma(C_0)$.
Тогда эта конфигурация должна быть либо 0-, либо 1-валентной (в ней уже принято решение).
 
[[Файл:Distributed-flp-proof-case2.png|400px]]
 
Но теперь мы можем сказать, что процесс $p$ не отказал, а просто очень долго работал и теперь получает событие $e$.
Так как $\sigma$ не обращается к $p$, то $E_0=e(\sigma(C_0)=\sigma(e(C_0))=\sigma(D_0)$ — конфигурация, достижимая из 0-валентной, т.е. тоже 0-валентная.
 
С другой стороны, можно аналогично сказать, что процесс $p$ теперь получает сообщение $e'$, а за ним — сообщение $e$.
Тогда получается $E_1=e(e'(\sigma(C_0))$.
Из-за коммутативности получаем $E_1=\sigma(e(e'(C_0)))=\sigma(e(C_1))=\sigma(D_1)$ — конфигурация, достижимая из 1-валентной, т.е. тоже 1-валентная.
 
Таким образом получаем, что из $A$ достижимы и 0-валентная, и 1-валентная конфигурация, противоречие.
== Ссылки ==
* http://bailonga.es/tpmtp/lecture09.pdf
* https://github.com/volhovm/study-notes/blob/master/parallel_programming/parallel_programming.org
292
правки

Навигация