Алгоритм Бен-Ора

Алгоритм Бен-Ора — алгоритм, который позволяет $N$ процессам в асинхронной системе прийти к недетерминированному консенсусу на одном бите, если у нас не более $f<\frac N 2$ отказов узлов даже при сильном противнике за ожидаемое время $O(2^N)$.

Мы хотим, чтобы процессы пришли к консенсусу. Мы можем разрешить процессам кидать монетку, тем самым добавив недетерминизм и обойдя ограничения FLP на невозможность консенсуса.

Модель

Состояний у нас бесконечно, поэтому надо как-то уточнить требование завершимости: скажем, что мы хотим достигнуть консенсуса не за конечное время, а с вероятностью 1 (см. теорию меры для формальных определений).

Несмотря на то, что в каждой конфигурации мы теперь находимся лишь с какой-то вероятностью, порядок доставки сообщений всё ещё выбирает противник, чтобы нам было посложнее. Бывает принципиально два вида противников:

• Сильный противник знает всё, что происходило в системе и всех процессах, включая полученные случайные биты, но не может предсказать будущее.
• Слабый противник чего-то может и не знать. Например, может видеть только сообщения и не знать ни полученных битов, ни внутренние состояния процессов.

Алгоритм Бен-Ора работает даже с сильным противником.

Алгоритм

Каждый процесс работает бесконечно долго, алгоритм делится на одинаковые раунды, пронумерованные натуральными числами с единицы.

Каждый раунд состоит из двух фаз. В каждой фазе процесс посылает всем остальным сообщение. Важно, что система всё равно асинхронная, поэтому для завершения фазы мы ждём хотя бы $N-f$ ответов (а такое обязательно произойдёт, потому что у нас не более $f$ отказов), а не какое-то "время" (которого нет).

Каждое сообщение содержит в себе номер раунда, так что если пришло сообщение со старого раунда, оно игнорируется. Если пришло с нового — ставится в очередь. Вроде нам даже FIFO не требуется(?).

В каждый момент у процесса есть предпочтение — бит.

Первая фаза: процесс рассылает всем остальным своё предпочтение: сообщение $(1, k, p)$, где $k$ — это номер раунда, а $p$ — предпочтение. После получения $N-f$ ответов фаза завершается:

• Если процесс получил строго больше $\frac N 2$ предпочтений (включая своё) с каким-то значением, то это предложение ратифицируется.

Вторая фаза: если у процесса есть ратифицированное на данном шаге предпочтение, то он рассылает всем остальным сообщение $(2, k, v)$ для ратификации ($v$ — ратифицированное значение). В противном случае рассылает всем сообщение $(2, k, ?)$. После получения $N-f$ ответов фаза завершается:

• Если процесс получил хотя бы одну ратификацию (или сам её отправил), то в следующем раунде предпочтение процесса меняется на полученное ратифицированное кем-то значение (все ратификации совпадают, см. ниже).
• Если процесс получил строго больше $f$ ратификаций, процесс принимает соответствующее ратифицированное решение, но продолжает выполняться в следующих раундах
• Если процесс не получил ни одной ратификации, предпочтение в следующем раунде меняется на случайный бит (это единственное недетерминированное место)

Доказательство

Лемма: в каждом раунде $k$ все ратифицированные значения одинаковы. Это очевидно, так как для ратификации требуется набрать строгое большинство предложений.

Лемма: если в раунде $k$ процесс $P$ принял решение $v$, то раунд $k+1$ все процессы начнут с предпочтением $v$. Доказательство: чтобы принять решение, надо было получить хотя бы $f+1$ ратификацию. Предположим, что какой-нибудь другой процесс $Q$, который начал следующий раунд не с предпочтением $v$. Чтобы это произошло, $Q$ должен был не получить ни одной ратификации, то есть получить $N-f$ сообщений вида $(2, k, ?)$. Но тогда всего в системе было $(f+1)+N-f=N+1>N$ сообщений, противоречие.

Таким образом, если когда-то решение и приняли, то в следующем раунде у нас предпочтение у всех процессов равно этому решению, после чего им остаётся только проголосовать за него, единогласно ратифицировать и решить.

Остановка алгоритма

Когда какой-нибудь процесс принимает решение, он может разослать всем остальным сообщение "Решение принято" и остановиться. Это сообщение дойдёт до всех живых процессов за конечное время, после чего они тоже остановятся. То, что они будут пытаться достучаться до остановившихся процессов или общаться между собой, нам неважно.

Оценки

Без доказательства. Но у нас есть недетерминированный алгоритм в асинхронной системе с сильным противником с вероятностью завершения за конечное число шагов, равной единице. Правда, среднее время работы экспоненциально: $O(2^N)$, потому что нам надо, чтобы случайными флуктуациями получилось достаточно много одинаковых битов. Примерная причина: мы хотим случайно получить ситуацию, в которой есть больше $\frac N 2$ одинаковых битов из каких-то $N - f$, которые нам подсунул противник).

Алгоритм не очень практичный, но интересный: показывает, как использовать монетку.