292
правки
Изменения
Нет описания правки
'''Распределенный алгоритм для WCP''' – алгоритм для поиска наименьшего (проще говоря, самого левого) [[Срез, согласованный срез|согласованного среза]] в котором выполняется [[Слабый конъюнктивный предикат (WCP)|слабый конъюнктивный предикат]].
В распределенном алгоритме используются [[Векторные часы|векторные часы]], как и в [[Централизованный алгоритм для WCP|централизованном]] (они вообще похожи).
В дополнение к каждому из $N$ процессов заведем еще $N$ монитор-процессовкоординаторов (вместо одного на всех), где каждый процесс связан со своим монитор-процессомкоординатором. Монитор-процессы отправляют друг другу так называемый ''токен'' (его описание ниже) и получают вектор часов от соответствующих процессов.
Токен состоит из двух векторов. Первый назовем $G$. $G[i] = k$ означает, что состояние номер $k$ $i$-го процесса входит в срез-кандидат. Важно, что этот срез может не быть согласованным, но все состояния в нем удовлетворяют локальным предикатам. $G$ инициализируется нулями.
