Изменения

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

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

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

Для этого применим, так называемое, запоминание на стороне получателя. Когда красный процесс получает сообщение от белого процесса (без маркера), то процесс сохраняет его у себя.

Как только белый процесс получил красное сообщение (либо же маркер, как и раньше), он инициирует изменение цвета и т.д. Однако это не решает проблему того, что белое сообщение может прибыть позже красного. Чтобы решить эту проблему, будем вместе с маркеом маркером отправлять общее (тотальное) число белых сообщений, отправленных соответствующим процессом через соотвествующий соответствующий канал на конкретный момент. Процесс-получатель отслеживает общее количество полученных белых сообщений и знает, что все белые сообщения будут получены, когда этот счет будет равен тотальному числу.

Если сообщения могут теряться, то есть смысл запоминать сообщения на стороне отправителя. Пусть процесс записывает все исходящие сообщения , пока он белый. Когда процессы-получатели становятся краснымибелый процесс получает белое сообщение, они высылают он посылает ответный маркеры маркер ack сигнализирующие о том, что получили сообщения. Если процесс-отправитель получил ack на соответствующее сообщение, то его можно больше не хранить.