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

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

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

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

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

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

Модификации

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

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

• ненадежный канал связи

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