Алгоритм Бен-Ора - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:36:10Z

rollbackEdits.php mass rollback

185.220.100.254 в 04:07, 1 сентября 2022

2022-09-01T04:07:06Z

Yeputons в 05:57, 4 июня 2019

2019-06-04T05:57:49Z

Yeputons: /* Оценки */

2019-06-03T17:00:41Z

‎Оценки

Yeputons: /* Алгоритм */

2019-06-03T16:54:01Z

‎Алгоритм

Yeputons: Новая страница: «Категория:Параллельное программирование Алгоритм Бен-Ора — алгоритм, который позвол…»

2019-06-03T16:51:34Z

Новая страница: «Категория:Параллельное программирование Алгоритм Бен-Ора — алгоритм, который позвол…»

Новая страница

[[Категория:Параллельное программирование]]

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

← Предыдущая		Версия 16:36, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	[[Категория:Параллельное программирование]]		[[Категория:Параллельное программирование]]
	Алгоритм Бен-Ора — алгоритм, который позволяет $N$ процессам в асинхронной системе прийти к недетерминированному консенсусу на одном бите, если у нас не более $f<\frac N 2$ отказов узлов даже при ''сильном противнике'' за ожидаемое время $O(2^N)$.		Алгоритм Бен-Ора — алгоритм, который позволяет $N$ процессам в асинхронной системе прийти к недетерминированному консенсусу на одном бите, если у нас не более $f<\frac N 2$ отказов узлов даже при ''сильном противнике'' за ожидаемое время $O(2^N)$.

← Предыдущая		Версия 04:07, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	[[Категория:Параллельное программирование]]		[[Категория:Параллельное программирование]]
	Алгоритм Бен-Ора — алгоритм, который позволяет $N$ процессам в асинхронной системе прийти к недетерминированному консенсусу на одном бите, если у нас не более $f<\frac N 2$ отказов узлов даже при ''сильном противнике'' за ожидаемое время $O(2^N)$.		Алгоритм Бен-Ора — алгоритм, который позволяет $N$ процессам в асинхронной системе прийти к недетерминированному консенсусу на одном бите, если у нас не более $f<\frac N 2$ отказов узлов даже при ''сильном противнике'' за ожидаемое время $O(2^N)$.

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

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

@@ Строка 40: / Строка 40: @@
 В противном случае рассылает всем сообщение $(2, k, ?)$.
 После получения $N-f$ ответов фаза завершается:
-* Если процесс получил хотя бы одну ратификацию (или сам её отправил), то в следующем раунде предпочтение процесса меняется на полученное ратифицированное кем-то значение.
+* Если процесс получил хотя бы одну ратификацию (или сам её отправил), то в следующем раунде предпочтение процесса меняется на полученное ратифицированное кем-то значение (все ратификации совпадают, см. ниже).
 * Если процесс получил строго больше $f$ ратификаций, процесс принимает соответствующее ратифицированное решение, но продолжает выполняться в следующих раундах
 * Если процесс не получил ни одной ратификации, предпочтение в следующем раунде меняется на случайный бит (это единственное '''недетерминированное место''')