Теорема Фишера-Линча-Патерсона (FLP) - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:26:35Z

rollbackEdits.php mass rollback

103.251.167.21 в 04:56, 1 сентября 2022

2022-09-01T04:56:09Z

Ponomarev в 22:00, 20 июня 2020

2020-06-20T22:00:32Z

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

2019-06-04T05:49:43Z

Yeputons в 16:22, 3 июня 2019

2019-06-03T16:22:09Z

Yeputons в 16:21, 3 июня 2019

2019-06-03T16:21:28Z

Yeputons в 14:31, 3 июня 2019

2019-06-03T14:31:14Z

Yeputons: /* Шаг 3: разбор случаев */

2019-06-03T14:28:13Z

‎Шаг 3: разбор случаев

Yeputons: /* Шаг 2: существование соседних разновалентных конфигураций */

2019-06-03T14:15:04Z

‎Шаг 2: существование соседних разновалентных конфигураций

Yeputons: /* Шаг 2: существование соседних разновалентных конфигураций */

2019-06-03T14:13:38Z

‎Шаг 2: существование соседних разновалентных конфигураций

← Предыдущая		Версия 16:26, 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 Майкл Наки].
−	\|}
−
	[[Категория:Параллельное программирование]]		[[Категория:Параллельное программирование]]
	Теорема Фишера, Линча и Патерсона (FLP, 1985 год): невозможно достичь даже необоснованного [[Консенсус в распределённой системе\|консенсуса]] $N>2$ процессами даже на одном бите при следующих условиях:		Теорема Фишера, Линча и Патерсона (FLP, 1985 год): невозможно достичь даже необоснованного [[Консенсус в распределённой системе\|консенсуса]] $N>2$ процессами даже на одном бите при следующих условиях:

← Предыдущая		Версия 04:56, 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 Майкл Наки].
		+	\|}
		+
	[[Категория:Параллельное программирование]]		[[Категория:Параллельное программирование]]
	Теорема Фишера, Линча и Патерсона (FLP, 1985 год): невозможно достичь даже необоснованного [[Консенсус в распределённой системе\|консенсуса]] $N>2$ процессами даже на одном бите при следующих условиях:		Теорема Фишера, Линча и Патерсона (FLP, 1985 год): невозможно достичь даже необоснованного [[Консенсус в распределённой системе\|консенсуса]] $N>2$ процессами даже на одном бите при следующих условиях:

@@ Строка 12: / Строка 12: @@
 При этом даже если разрешить одновременную посылку сообщения сразу нескольким процессам (как в [[Общий порядок сообщений|общем порядке сообщений]]) и тем самым запретить процессу падать при массовой рассылке сообщений, лучше не станет: нет гарантии, в каком порядке и как скоро эти сообщения будут получены и обработаны получателями.
-А вот если какую-нибудь гарантию дадим, то получаем [[Переформулировки консенсуса в распределённой системе#Terminating Reliable Broadcast (TRB)|TLB]], из которого сразу выводится консенсус.
+А вот если какую-нибудь гарантию дадим, то получаем [[Переформулировки консенсуса в распределённой системе#Terminating Reliable Broadcast (TRB)|TRB]], из которого сразу выводится консенсус.
 == Доказательство ==

@@ Строка 6: / Строка 6: @@
 * Алгоритм должен быть детерминирован.
 Если отказов нет, есть [[Консенсус в распределённой системе#Решение при отсутствии отказов|простой алгоритм]].
 Если система синхронна, то есть [[консенсус в синхронных системах]].

← Предыдущая		Версия 16:22, 3 июня 2019
Строка 1:		Строка 1:
		+	[[Категория:Параллельное программирование]]
	Теорема Фишера, Линча и Патерсона (FLP, 1985 год): невозможно достичь даже необоснованного [[Консенсус в распределённой системе\|консенсуса]] $N>2$ процессами даже на одном бите при следующих условиях:		Теорема Фишера, Линча и Патерсона (FLP, 1985 год): невозможно достичь даже необоснованного [[Консенсус в распределённой системе\|консенсуса]] $N>2$ процессами даже на одном бите при следующих условиях:
	* Алгоритм должен завершиться за конечное время.		* Алгоритм должен завершиться за конечное время.

@@ Строка 1: / Строка 1: @@
-Теорема Фишера, Линча и Патерсона (FLP, 1985 год) невозможно достичь даже необоснованного [[Консенсус в распределённой системе|консенсуса]] $N>2$ процессами даже на одном бите при следующих условиях:
+Теорема Фишера, Линча и Патерсона (FLP, 1985 год): невозможно достичь даже необоснованного [[Консенсус в распределённой системе|консенсуса]] $N>2$ процессами даже на одном бите при следующих условиях:
 * Алгоритм должен завершиться за конечное время.
 * Один из узлов [[Иерархия ошибок в распределённых системах|может отказать]]

@@ Строка 111: / Строка 111: @@
 ==== Шаг 3: разбор случаев ====
 == Ссылки ==
 * http://bailonga.es/tpmtp/lecture09.pdf
 * https://github.com/volhovm/study-notes/blob/master/parallel_programming/parallel_programming.org

@@ Строка 107: / Строка 107: @@
 По предыдущему шагу найдём в $D$ 1-валентную конфигурацию $D_1=e(C_1)\in D$.
 Конфигурация $C_1$ получена какой-то конечной непустой цепочкой сообщений $x_1, x_2, \dots, x_k$.
-Будем по очереди убирать по одному сообщения с конца и смотреть на валентность конфигурации $e(x_{k-1}(\dots(x_1(G))\dots))$ — в какой-то момент она станет нулём (например, при пустой цепочке, т.е. при рассмотрении $e(G)\in D$).
+Будем по очереди убирать по одному сообщения с конца и смотреть на валентность конфигураций $e(x_{k-1}(\dots(x_1(G))\dots))$, $e(x_{k-2}(\dots(x_1(G))\dots))$, \dots — в какой-то момент она сменится с единицы на ноль (например, при пустой цепочке, т.е. при рассмотрении $e(G)\in D$).
 Тогда мы как раз нашли искомую пару соседей $C_0$ и $C_1$ таких, что $e(C_0)$ и $e(C_1)$ разной валентности.

← Предыдущая		Версия 14:13, 3 июня 2019
Строка 100:		Строка 100:

	==== Шаг 2: существование соседних разновалентных конфигураций ====		==== Шаг 2: существование соседних разновалентных конфигураций ====
		+
		+	Теперь мы хотим найти такие две соседние конфигурации $C_0, C_1 \in C$ (отличающиеся переходом $e'(C_0)=C_1$), что $D_0=e(C_0) \in D$ является 0-валентной, а $D_1=e(C_1)$ — 1-валентной (или наоборот).
		+	Это можно сделать, если взять в $D$ конфигурацию $e(C_1)$, отличающуюся от валентности $e(G)$, а дальше посмотреть на цепочку конфигураций между $G$ и $e(C_1)$ и найти момент смены валентности.
		+
		+	Начнём искать, более строго. Не теряя общности можем сказать, что $e(G)\in D$ является 0-валентной (иначе повторим доказательство шага).
		+	По предыдущему шагу найдём в $D$ 1-валентную конфигурацию $D_1=e(C_1)\in D$.
		+	Конфигурация $C_1$ получена какой-то конечной непустой цепочкой сообщений $x_1, x_2, \dots, x_k$.
		+	Будем по очереди убирать по одному сообщения с конца и смотреть на валентность конфигурации $e(x_{k-1}(\dots(x_1(G))\dots))$ — в какой-то момент она станет нулём (например, при пустой цепочке, т.е. при рассмотрении $e(G)\in D$).
		+	Тогда мы как раз нашли искомую пару соседей $C_0$ и $C_1$ таких, что $e(C_0)$ и $e(C_1)$ разной валентности.

	==== Шаг 3: разбор случаев ====		==== Шаг 3: разбор случаев ====