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

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

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

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

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

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

Модификации

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

• не FIFO канал связи

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

• ненадежный канал связи (запоминание на стороне отправителя)

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