Алгоритм для синхронного порядка
| НЕТ ВОЙНЕ |
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Этот алгоритм берёт систему с асинхронным(?) порядком и начинает гарантировать в ней синхронный порядок.
Алгоритм для синхронного порядка основан на иерархии процессов (точнее, произвольном DAG процессов, отправлять сообщения могут только соединённые ребром), мы рассмотрим полный линейный порядок. Упорядочим процессы по номеру, назовем сообщение большим, если номер отправителя больше номера получателя, и малым иначе. Процесс может быть в активном или пассивном состоянии. Изначально все активны. В пассивном состоянии процесс не может ни отправлять, ни получать сообщения, он их складывает в очередь и ждёт, пока не станет активным.
Если процесс хочет отправить большое сообщение, то он его отправляет и ждёт подтверждения. А пока ждёт — становится пассивным.
Чтобы отправить сообщение большему процессу , процесс сначала посылает служебное сообщение, запрос. В ответ отправляет разрешение; он может сделать это только в активном состоянии. Разрешив, он становится пассивным и остается в этом состоянии, пока не получает сообщение, которое разрешил.
Таким образом, сообщения по факту "передаются" только от больших к маленьким и тогда можно нарисовать стрелочки. Взаимная блокировка наступить не может: мы ждём только меньших процессов, а транзитивность у нас есть и циклов быть не может. Если маленький хочет отправить сообщение большому, то он отсылает запрос и продолжает работать (посылать большие и маленькие сообщения, менять своё состояние). Ничего страшного, что по факту сообщение "отправится" только через какое-то время — с точки зрения процесса оно просто долго было в пути.
Разумеется, надо аккуратно доказать, что функцию $T$ можно придумать. Это делается на странице 200 в Gaarg, там происходит что-то вроде логических часов.
Итого на $m$ сообщений нам требуется послать не больше $3m$ сообщений (худший случай — все сообщения маленькие).
