Изменения

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

Есть инициатор (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 (см. билеты дальше), они высылают ответный маркеры ack сигнализирующие о томно это надо делать глобально (с начала времён), что получили иначе можно потерять сообщения, отправленные до работы FIFO-алгоритма. Если  Как только белый процесс-отправитель получил ack на соответствующее красное сообщение(либо же маркер, как и раньше), то его можно больше он инициирует изменение цвета и т.д. Однако это не хранитьрешает проблему того, что белое сообщение может прибыть позже красного. Чтобы решить эту проблему, будем вместе с маркером отправлять общее (тотальное) число белых сообщений, отправленных соответствующим процессом через соответствующий канал на конкретный момент. Процесс-получатель отслеживает общее количество полученных белых сообщений и знает, что все белые сообщения будут получены, когда этот счет будет равен тотальному числу.