Изменения

Суть алгоритма в том, что В алгоритме мы ставим в соответствие каждому процессу белый или красный светцвет. Изначально все процессы белые. Когда все процессы станут красными , мы получим согласованный срез.

Есть инициатор (observer) с которого всё начинается. Он становится красным, запоминает свое состояние и посылает маркер всем другим процессам , с которыми у него есть канал. Только после этого он может снова обрабатывать полученные сообщения или же отправлять. Если процесс получил маркер и еще белый, то он обязан стать красным, записать свое локальное состояние и отправить остальным процессам маркеры. Иначе можно ничего делать не делатьнадо. Это гарантируетТаким образом, если процесс только что ни один белый процесс не получит сообщение от красного процесса стал красным (иначе будет противоречие с идеей согласованного срезаи записал своё состояние в согласованный срез), то все сообщения, которые он уже обработал, были посланы остальными процессами в моменты, которые учтены в согласованном срезе из-за FIFO.

Чтобы восстановить работу системы из запомненного состояния надо еще запоминать и Будем называть сообщениякрасными, которые оказались в путиесли они отправлены от красного процесса, таналогично для белого процесса.е все такие $m$С технической точки зрения, что $snd(m) ∈ G ∧ rcv(m) ∈ M$при отправке сообщения или же маркера, где $G$ – согласованный срез, $M$ - все что не вошло в $G$будем добавлять цвет передаваемого сообщения.

Для этого применимЧтобы восстановить работу системы из запомненного состояния надо еще запоминать и сообщения, так называемоекоторые оказались в пути, запоминание на стороне получателят. Когда красный процесс получает сообщение от белого процесса е. все такие $m$, что $snd(m) \in G ∧ rcv(без маркераm)\notin G$, то процесс сохраняет его у себягде $G$ – согласованный срез.

Итого $O(n^2)$ сообщений. ===МодификацииЗапоминание сообщений на стороне отправителя ===* не FIFO канал связиВместо отправки маркера будем отправлять с каждым сообщением цвет текущего процесса. Как только белый процесс получил сообщение от красного, он инициирует изменение цвета.* ненадежный канал связиЕсли сообщения могут теряться, то есть смысл запоминать сообщения на стороне отправителя(впрочем, тогда у нас весь алгоритм может сломаться, потому что он не делает попытки перепослать сообщение-маркер; но это можно пробовать лечить таймаутами). Пусть процесс записывает все исходящие сообщения , пока он белый (т.е. с начала времён). Когда белый процесс получает белое сообщение, он посылает ответный маркер ack. Если процесс-отправитель получил ack на соответствующее сообщение, то его можно больше не станет хранить.Когда все процессы стали красными, надо взять их красные состояния и все исходящие сообщения в качестве состояния системы. При этом при восстановлении, возможно, потребуется обработать некоторые сообщения заново (например, какой-то процесс долго тормозил, а остальные успели обменяться кучей сообщений после того, как стали красными). === Запоминание сообщений на стороне получателя ===Когда красный процесс получает сообщение от белого процесса (без маркера), то процесс сохраняет его у себя.После того, как все процессы стали красными ''и получили маркеры от всех своих соседей'', надо взять их красные состояния и все полученные ими до этого момента сообщения.Сообщения, полученные краснымот красного, не запоминаются — они будут заново отправлены при восстановлении системы. Если просто ждать, пока процессы станут красными, то можно потерять сообщение, если канал между двумя процессами очень сильно тормозит. Поэтому надо ждать именно прохождения всех маркеров. === Не FIFO === Не-FIFO можно свести к FIFO (см. билеты дальше), но это надо делать глобально (с начала времён), иначе можно потерять сообщения, отправленные до работы FIFO-алгоритма.  Как только белый процесс получил красное сообщение (либо же маркер, как и раньше), он стал красныминициирует изменение цвета и т.д. Однако это не решает проблему того, что белое сообщение может прибыть позже красного. Чтобы решить эту проблему, он отправляет маркер во все входящие каналы будем вместе с маркером отправлять общее (в обратном направлениитотальное)число белых сообщений, подтверждающий получение предыдущих сообщенийотправленных соответствующим процессом через соответствующий канал на конкретный момент. Процесс может проверить состояние канала удалением всех -получатель отслеживает общее количество полученных белых сообщенийи знает, что все белые сообщения будут получены, связанных с маркером для данного каналакогда этот счет будет равен тотальному числу.