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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Алгоритм Бен-Ора — алгоритм, который позволяет $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$, которые нам подсунул противник).

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