Алгоритм Чанди-Лампорта

Алгоритм Чанди-Лампорта получения согласованного среза с запоминанием на стороне получателя с учетом FIFO канала связи.

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

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

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

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

Итого $O(n^2)$ сообщений.

Запоминание сообщений на стороне отправителя

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

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

Запоминание сообщений на стороне получателя

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

Не FIFO

Не-FIFO можно свести к FIFO (см. билеты дальше).

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