Изменения

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

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

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

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