Изменения
Нет описания правки
Суть алгоритма в том, что мы ставим в соответствие каждому процессу белый или красный цвет. Изначально все процессы белые. Когда все процессы станут красными, мы получим согласованный срез.
Есть инициатор (observer) с которого всё начинается. Он становится красным, запоминает свое состояние и посылает маркер всем другим процессам, с которыми у него есть канал. Только после этого он может снова обрабатывать полученные сообщения или же отправлять. Если процесс получил маркер и еще белый, то он обязан стать красным, записать свое локальное состояние и отправить остальным процессам маркеры. Иначе можно ничего делать не делатьнадо. Это гарантирует, что ни один белый процесс не получит сообщение от красного процесса (иначе будет противоречие с идеей согласованного среза).
Чтобы восстановить работу системы из запомненного состояния надо еще запоминать и сообщения, которые оказались в пути, т.е. все такие $m$, что $snd(m) \in G ∧ rcv(m) \notin G$, где $G$ – согласованный срез.
