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