Изменения

'''Алгоритм Чанди-Лампорта''' получения [[Срез, согласованный срез|согласованного среза]]с запоминанием на стороне получателя с учетом FIFO канала связи.

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

Процесс меняет цвет как только записал Есть инициатор (observer) с которого всё начинается. Он становится красным, запоминает свое локальное состояниеи посылает маркер всем другим процессам, с которыми у него есть канал. После Только после этого он отсылает всем процессам специальное сообщение - маркерможет снова обрабатывать полученные сообщения или же отправлять. Если процесс получил маркер и еще белый, то он обязан стать красным, записать свое локальное состояние, стать красным и оправить отправить остальным процессам маркеры. Иначе можно ничего делать не делатьнадо.Таким образом, если процесс только что стал красным (и записал своё состояние в согласованный срез), то все сообщения, которые он уже обработал, были посланы остальными процессами в моменты, которые учтены в согласованном срезе из-за FIFO. Будем называть сообщения красными, если они отправлены от красного процесса, аналогично для белого процесса. С технической точки зрения, при отправке сообщения или же маркера, будем добавлять цвет передаваемого сообщения. Чтобы восстановить работу системы из запомненного состояния надо еще запоминать и сообщения, которые оказались в пути, т.е. все такие $m$, что $snd(m) \in G ∧ rcv(m) \notin G$, где $G$ – согласованный срез. Итого $O(n^2)$ сообщений. Это гарантирует === Запоминание сообщений на стороне отправителя ===Если сообщения могут теряться, то есть смысл запоминать сообщения на стороне отправителя (впрочем, тогда у нас весь алгоритм может сломаться, потому что ни один он не делает попытки перепослать сообщение-маркер; но это можно пробовать лечить таймаутами). Пусть процесс записывает все исходящие сообщения, пока он белый (т.е. с начала времён). Когда белый процесс получает белое сообщение, он посылает ответный маркер ack. Если процесс-отправитель получил ack на соответствующее сообщение, то его можно больше не получит хранить.Когда все процессы стали красными, надо взять их красные состояния и все исходящие сообщения в качестве состояния системы. При этом при восстановлении, возможно, потребуется обработать некоторые сообщения заново (например, какой-то процесс долго тормозил, а остальные успели обменяться кучей сообщений после того, как стали красными). === Запоминание сообщений на стороне получателя ===Когда красный процесс получает сообщение от белого процесса (без маркера), то процесс сохраняет его у себя.После того, как все процессы стали красными ''и получили маркеры от всех своих соседей'', надо взять их красные состояния и все полученные ими до этого момента сообщения.Сообщения, полученные красным от красного, не запоминаются — они будут заново отправлены при восстановлении системы. Если просто ждать, пока процессы станут красными, то можно потерять сообщение, если канал между двумя процессами очень сильно тормозит. Поэтому надо ждать именно прохождения всех маркеров. === Не FIFO === Не-FIFO можно свести к FIFO (см. билеты дальше), но это надо делать глобально (с начала времён), иначе можно потерять сообщения, отправленные до работы FIFO-алгоритма. Как только белый процесс получил красное сообщение (либо же маркер, как и раньше), он инициирует изменение цвета и т.д. Однако это не решает проблему того, что белое сообщение может прибыть позже красного процесса. Чтобы решить эту проблему, будем вместе с маркером отправлять общее (тотальное) число белых сообщений, отправленных соответствующим процессом через соответствующий канал на конкретный момент. Процесс-получатель отслеживает общее количество полученных белых сообщений и знает, что все белые сообщения будут получены, когда этот счет будет равен тотальному числу.