Теорема Фишера-Линча-Патерсона (FLP)
Теорема Фишера, Линча и Патерсона (FLP, 1985 год) невозможно достичь даже необоснованного консенсуса $N>2$ процессами даже на одном бите при следующих условиях:
- Алгоритм должен завершиться за конечное время.
- Один из узлов может отказать
- Система асинхронна
- Алгоритм должен быть детерминирован.
Если отказов нет, есть простой алгоритм. Если система синхронна, то есть консенсус в синхронных системах. Если разрешаем недетерминизм, то есть алгоритм Бен-Ора.
Содержание
Доказательство
Из презентации Р. Елизарова.
От противного: пусть есть такой алгоритм, тогда мы проанализируем варианты его исполнения, подстроим порядок доставки сообщений (без откладывания сообщений бесконечно далеко), получим бесконечную цепочку выполнения и противоречие с конечностью алгоритма.
Модель
| Определение: |
Процесс — это детерминированный автомат, который может выполнять три операции:
|
Для доказательства от противного у нас есть такой алгоритм для процессов, что все они вызывают decided(value) с одинаковым значением через конечное время, независимо от того, как система задерживает сообщения.
| Определение: |
| Конфигурация — это состояния всех процессов плюс все сообщения в пути (которые отправили, но ещё не доставили). |
В начальной конфигурация у каждого процесса может быть сколько угодно входных данных и даже своя программа. Начальных конфигураций может быть несколько, они могут отличаться, например, предложениями процессов.
| Определение: |
Шаг из одной конфигурации в другую — это приём какого-то сообщения процессом (событие) и последовавшие за этим внутренние действия процесса до следующего receive(). Эти действия однозначно определяются предыдущей конфигурацией и событием. |
| Определение: |
| Исполнение — это бесконечная цепочка шагов из какой-нибудь начальной конфигурации. Бесконечная, потому что процессы могут выполняться и после принятия решений. |
| Определение: |
| Отказавший процесс — это процесс, который делает только конечное количество шагов в исполнении. Такой в системе может быть максимум один (это более сильное условие, чем если может много процессов отказывать). |
Также гарантируется, что в любом исполнении любое сообщение, предназначенное не отказавшему процессу, обрабатывается через конечное число шагов.
Другими словами, сообщения не теряются.
Валентность
Заметим, что в любом исполнении всегда принимается решение. Даже если один процесс отказал, то все остальные должны прийти к решению за конечное число шагов.
| Определение: |
| Конфигурация называется $i$-валентной и одновалентной, если все цепочки шагов из неё приводят к решению $i$.
Таким образом, бывают 0-валентные и 1-валентные конфигурации. Если же из конфигурации есть цепочки, приводящие к каждому из решений, то такая конфигурация называется бивалентной. |
Наблюдение: пусть из конфигурации $X$ есть цепочка шагов, обрабатывающая сообщения из $X$ в подмножестве процессов $A$, за которой идёт цепочка процессов, обрабатывающая сообщения из $X$ в подмножестве процессов $B$, и в конце мы получили конфигурацию $Y$. Тогда эти цепочки коммутируют: можно сначала обработать сообщения подмножеством процессов $B$, а потом — $A$ (так как мы обрабатываем только сообщения из $X$, а не новые).
Начальная бивалентная конфигурация
Лемма: существует бивалентная начальная конфигурация.
Доказательство от противного: пусть все начальные конфигурации одновалентны. Из нетривиальности консенсуса мы знаем, что есть как 0-, так и 1-валентные начальные конфигурации. Тогда можно найти две начальные конфигурации разной валентности, которые отличаются только состоянием одного процесса: взяли две произвольные начальные конфигурации разной валентности, начали переводить одну в другую копированием исходных состояний процессов, по одному процессу за шаг.
А раз есть две такие конфигурации разной валентности, то пусть в каждой из них этот процесс (где они отличаются) откажет с самого начала, до отправки и приёма любых сообщений. Тогда мы всё ещё получим консенсус, но решение будет одинаковым, потому что внешняя система никак не может выявить состояние отказавшего процесса. А они исходно были разной валентности, противоречие.
