Алгоритм Чанди-Лампорта - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:41:19Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:25, 1 сентября 2022

2022-09-01T03:25:27Z

Yeputons: /* Не FIFO */

2019-06-02T18:06:41Z

‎Не FIFO

Yeputons: /* Запоминание сообщений на стороне получателя */

2019-06-02T18:06:08Z

‎Запоминание сообщений на стороне получателя

Yeputons: /* Запоминание сообщений на стороне отправителя */

2019-06-02T17:59:55Z

‎Запоминание сообщений на стороне отправителя

Yeputons: /* Запоминание сообщений на стороне отправителя */

2019-06-02T17:57:50Z

‎Запоминание сообщений на стороне отправителя

Yeputons в 17:56, 2 июня 2019

2019-06-02T17:56:42Z

5.18.249.29 в 16:58, 16 мая 2018

2018-05-16T16:58:44Z

Rgolchin в 20:56, 14 марта 2018

2018-03-14T20:56:20Z

5.18.249.29: /* Модификации */

2018-03-12T17:18:42Z

‎Модификации

← Предыдущая		Версия 16:41, 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 Майкл Наки].
−	\|}
−
	[[Категория: Параллельное программирование]]		[[Категория: Параллельное программирование]]
	'''Алгоритм Чанди-Лампорта''' получения [[Срез, согласованный срез\|согласованного среза]] с запоминанием на стороне получателя с учетом FIFO канала связи.		'''Алгоритм Чанди-Лампорта''' получения [[Срез, согласованный срез\|согласованного среза]] с запоминанием на стороне получателя с учетом FIFO канала связи.

← Предыдущая		Версия 03:25, 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 Майкл Наки].
		+	\|}
		+
	[[Категория: Параллельное программирование]]		[[Категория: Параллельное программирование]]
	'''Алгоритм Чанди-Лампорта''' получения [[Срез, согласованный срез\|согласованного среза]] с запоминанием на стороне получателя с учетом FIFO канала связи.		'''Алгоритм Чанди-Лампорта''' получения [[Срез, согласованный срез\|согласованного среза]] с запоминанием на стороне получателя с учетом FIFO канала связи.

@@ Строка 28: / Строка 28: @@
 === Не FIFO ===
-Не-FIFO можно свести к FIFO (см. билеты дальше).
+Не-FIFO можно свести к FIFO (см. билеты дальше), но это надо делать глобально (с начала времён), иначе можно потерять сообщения, отправленные до работы FIFO-алгоритма.
 Как только белый процесс получил красное сообщение (либо же маркер, как и раньше), он инициирует изменение цвета и т.д. Однако это не решает проблему того, что белое сообщение может прибыть позже красного. Чтобы решить эту проблему, будем вместе с маркером отправлять общее (тотальное) число белых сообщений, отправленных соответствующим процессом через соответствующий канал на конкретный момент. Процесс-получатель отслеживает общее количество полученных белых сообщений и знает, что все белые сообщения будут получены, когда этот счет будет равен тотальному числу.

@@ Строка 21: / Строка 21: @@
 === Запоминание сообщений на стороне получателя ===
 Когда красный процесс получает сообщение от белого процесса (без маркера), то процесс сохраняет его у себя.
-После того, как все процессы стали красными, надо взять их красные состояния и все полученные ими до этого момента сообщения.
+После того, как все процессы стали красными ''и получили маркеры от всех своих соседей'', надо взять их красные состояния и все полученные ими до этого момента сообщения.
 Сообщения, полученные красным от красного, не запоминаются — они будут заново отправлены при восстановлении системы.
 === Не FIFO ===

@@ Строка 14: / Строка 14: @@
 === Запоминание сообщений на стороне отправителя ===
-Если сообщения могут теряться, то есть смысл запоминать сообщения на стороне отправителя (впрочем, тогда у нас весь алгоритм может сломаться, потому что он не делает попытки перепослать сообщение-маркер; но это можно пробовать лечить таймаутами). Пусть процесс записывает все исходящие сообщения, пока он белый. Когда белый процесс получает белое сообщение, он посылает ответный маркер ack. Если процесс-отправитель получил ack на соответствующее сообщение, то его можно больше не хранить.
+Если сообщения могут теряться, то есть смысл запоминать сообщения на стороне отправителя (впрочем, тогда у нас весь алгоритм может сломаться, потому что он не делает попытки перепослать сообщение-маркер; но это можно пробовать лечить таймаутами). Пусть процесс записывает все исходящие сообщения, пока он белый (т.е. с начала времён). Когда белый процесс получает белое сообщение, он посылает ответный маркер ack. Если процесс-отправитель получил ack на соответствующее сообщение, то его можно больше не хранить.
 Когда все процессы стали красными, надо взять их красные состояния и все исходящие сообщения в качестве состояния системы.

@@ Строка 2: / Строка 2: @@
 '''Алгоритм Чанди-Лампорта''' получения [[Срез, согласованный срез|согласованного среза]] с запоминанием на стороне получателя с учетом FIFO канала связи.
-Суть алгоритма в том, что мы ставим в соответствие каждому процессу белый или красный цвет. Изначально все процессы белые. Когда все процессы станут красными, мы получим согласованный срез.
+В алгоритме мы ставим в соответствие каждому процессу белый или красный цвет. Изначально все процессы белые. Когда все процессы станут красными, мы получим согласованный срез.
-Есть инициатор (observer) с которого всё начинается. Он становится красным, запоминает свое состояние и посылает маркер всем другим процессам, с которыми у него есть канал. Только после этого он может снова обрабатывать полученные сообщения или же отправлять. Если процесс получил маркер и еще белый, то он обязан стать красным, записать свое локальное состояние и отправить остальным процессам маркеры. Иначе ничего делать не надо. Это гарантирует, что ни один белый процесс не получит сообщение от красного процесса (иначе будет противоречие с идеей согласованного среза).
+Есть инициатор (observer) с которого всё начинается. Он становится красным, запоминает свое состояние и посылает маркер всем другим процессам, с которыми у него есть канал. Только после этого он может снова обрабатывать полученные сообщения или же отправлять. Если процесс получил маркер и еще белый, то он обязан стать красным, записать свое локальное состояние и отправить остальным процессам маркеры. Иначе ничего делать не надо.
 Чтобы восстановить работу системы из запомненного состояния надо еще запоминать и сообщения, которые оказались в пути, т.е. все такие $m$, что $snd(m) \in G ∧ rcv(m) \notin G$, где $G$ – согласованный срез.
-Для этого применим, так называемое запоминание на стороне получателя. Когда красный процесс получает сообщение от белого процесса (без маркера), то процесс сохраняет его у себя.
+Итого $O(n^2)$ сообщений.
-==Модификации==
+Не-FIFO можно свести к FIFO (см. билеты дальше).
 Как только белый процесс получил красное сообщение (либо же маркер, как и раньше), он инициирует изменение цвета и т.д. Однако это не решает проблему того, что белое сообщение может прибыть позже красного. Чтобы решить эту проблему, будем вместе с маркером отправлять общее (тотальное) число белых сообщений, отправленных соответствующим процессом через соответствующий канал на конкретный момент. Процесс-получатель отслеживает общее количество полученных белых сообщений и знает, что все белые сообщения будут получены, когда этот счет будет равен тотальному числу.

@@ Строка 2: / Строка 2: @@
 '''Алгоритм Чанди-Лампорта''' получения [[Срез, согласованный срез|согласованного среза]] с запоминанием на стороне получателя с учетом FIFO канала связи.
-Суть алгоритма в том, что мы ставим в соответствие каждому процессу белый или красный свет. Изначально все процессы белые. Когда все процессы станут красными мы получим согласованный срез.
+Суть алгоритма в том, что мы ставим в соответствие каждому процессу белый или красный цвет. Изначально все процессы белые. Когда все процессы станут красными, мы получим согласованный срез.
-Есть инициатор (observer) с которого всё начинается. Он становится красным, запоминает свое состояние и посылает маркер всем другим процессам с которыми у него есть канал. Только после этого он может снова обрабатывать полученные сообщения или же отправлять. Если процесс получил маркер и еще белый, то он обязан стать красным, записать свое локальное состояние и отправить остальным процессам маркеры. Иначе можно ничего не делать. Это гарантирует, что ни один белый процесс не получит сообщение от красного процесса (иначе будет противоречие с идеей согласованного среза).
+Есть инициатор (observer) с которого всё начинается. Он становится красным, запоминает свое состояние и посылает маркер всем другим процессам, с которыми у него есть канал. Только после этого он может снова обрабатывать полученные сообщения или же отправлять. Если процесс получил маркер и еще белый, то он обязан стать красным, записать свое локальное состояние и отправить остальным процессам маркеры. Иначе можно ничего не делать. Это гарантирует, что ни один белый процесс не получит сообщение от красного процесса (иначе будет противоречие с идеей согласованного среза).
-Чтобы восстановить работу системы из запомненного состояния надо еще запоминать и сообщения, которые оказались в пути, т.е все такие $m$, что $snd(m) ∈ G ∧ rcv(m) ∈ M$, где $G$ – согласованный срез, $M$ - все что не вошло в $G$.
+Чтобы восстановить работу системы из запомненного состояния надо еще запоминать и сообщения, которые оказались в пути, т.е. все такие $m$, что $snd(m) \in G ∧ rcv(m) \notin G$, где $G$ – согласованный срез.
-Для этого применим, так называемое, запоминание на стороне получателя. Когда красный процесс получает сообщение от белого процесса (без маркера), то процесс сохраняет его у себя.
+Для этого применим, так называемое запоминание на стороне получателя. Когда красный процесс получает сообщение от белого процесса (без маркера), то процесс сохраняет его у себя.
 ==Модификации==
@@ Строка 14: / Строка 14: @@
 * не FIFO канал связи
-Как только белый процесс получил красное сообщение (либо же маркер, как и раньше), он инициирует изменение цвета и т.д. Однако это не решает проблему того, что белое сообщение может прибыть позже красного. Чтобы решить эту проблему, будем вместе с маркеом отправлять общее (тотальное) число белых сообщений, отправленных соответствующим процессом через соотвествующий канал на конкретный момент. Процесс-получатель отслеживает общее количество полученных белых сообщений и знает, что все белые сообщения будут получены, когда этот счет будет равен тотальному числу.
+Как только белый процесс получил красное сообщение (либо же маркер, как и раньше), он инициирует изменение цвета и т.д. Однако это не решает проблему того, что белое сообщение может прибыть позже красного. Чтобы решить эту проблему, будем вместе с маркером отправлять общее (тотальное) число белых сообщений, отправленных соответствующим процессом через соответствующий канал на конкретный момент. Процесс-получатель отслеживает общее количество полученных белых сообщений и знает, что все белые сообщения будут получены, когда этот счет будет равен тотальному числу.
 * ненадежный канал связи (запоминание на стороне отправителя)
-Если сообщения могут теряться, то есть смысл запоминать сообщения на стороне отправителя. Пусть процесс записывает все исходящие сообщения пока он белый. Когда процессы-получатели становятся красными, они высылают ответный маркеры ack сигнализирующие о том, что получили сообщения. Если процесс-отправитель получил ack на соответствующее сообщение, то его можно больше не хранить.
+Если сообщения могут теряться, то есть смысл запоминать сообщения на стороне отправителя. Пусть процесс записывает все исходящие сообщения, пока он белый. Когда белый процесс получает белое сообщение, он посылает ответный маркер ack. Если процесс-отправитель получил ack на соответствующее сообщение, то его можно больше не хранить.