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

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

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

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

Модификации

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

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

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

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