1632
правки
Изменения
м
rollbackEdits.php mass rollback
[[Категория:Параллельное программирование]]
Алгоритм Бен-Ора — алгоритм, который позволяет $N$ процессам в асинхронной системе прийти к недетерминированному консенсусу на одном бите, если у нас не более $f<\frac N 2$ отказов узлов даже при ''сильном противнике'' за ожидаемое время $O(2^N)$.
В противном случае рассылает всем сообщение $(2, k, ?)$.
После получения $N-f$ ответов фаза завершается:
* Если процесс получил хотя бы одну ратификацию (или сам её отправил), то в следующем раунде предпочтение процесса меняется на полученное ратифицированное кем-то значение(все ратификации совпадают, см. ниже).
* Если процесс получил строго больше $f$ ратификаций, процесс принимает соответствующее ратифицированное решение, но продолжает выполняться в следующих раундах
* Если процесс не получил ни одной ратификации, предпочтение в следующем раунде меняется на случайный бит (это единственное '''недетерминированное место''')
Без доказательства.
Но у нас есть недетерминированный алгоритм в асинхронной системе с сильным противником с вероятностью завершения за конечное число шагов, равной единице.
Правда, среднее время работы экспоненциально: $O(2^N)$, потому что нам надо, чтобыслучайными флуктуациями получилось достаточно много одинаковых битов.Примерная причина: мы хотим случайно получить ситуацию, в которой есть больше $\frac N 2$ одинаковых битов из каких-то $N - f$, которые нам подсунул противник). Алгоритм не очень практичный, но интересный: показывает, как использовать монетку.
