Просмотр исходного текста страницы Алгоритм Бен-Ора

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

Мы хотим, чтобы процессы пришли к консенсусу.
Мы можем разрешить процессам кидать монетку, тем самым добавив недетерминизм и обойдя ограничения [[Теорема Фишера-Линча-Патерсона (FLP)|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$, которые нам подсунул противник).

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