Изменения

В распределенном алгоритме используются [[Векторные часы|векторные часы]], как и в [[Централизованный алгоритм для WCP|централизованном]] (они вообще похожи, рекомендуется сначала понять централизованный).

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

В каждый момент времени ровно у одного координатора есть ''токен''.Токен состоит из двух векторов. Первый назовем $Gу координатора $. $G[i] = k$ означает, что состояние $k$ в централизованном алгоритме процесс $i$-го процесса входит в был бы красным и мы бы ждали от него сообщений, чтобы обновить срез-кандидат. ВажноКогда процесс становится зелёным, что этот срез может не быть согласованнымтокен передаётся координатору другого красного процесса.Итого мы распределяем очереди для процессов (сообщения от процесса хранятся только на координаторе): всё ещё требуется $O(N^2m)$ времени и памяти в сумме, но все состояния в нем удовлетворяют локальным предикатам. каждый процесс выполняет $O(Nm)$ работы ($N$ — количество процессов, $Gm$ инициализируется нулями— количество сообщений от одного процесса).

Формально токен состоит из двух векторов. Первый содержит срез-кандидат, назовем $G$. $G[i] = k$ означает, что состояние номер $k$ $i$-го процесса входит в срез-кандидат. Важно, что этот срез может не быть согласованным, но все состояния в нем удовлетворяют локальным предикатам. $G$ инициализируется нулями. Второй вектор назовем $color$, где $color[i] $ обозначает цвет состояния среза-кандидата для $i$-го процесса. Цвет состояния может быть красным или зеленым. Если $color[i] $ равен красному, то состояние $(i, G [i])$ и все его предшествующие состояния уже красные и никогда не смогут удовлетворить $WCP$из согласованного среза. Если $color [i] $ зеленый, то нет такого состояния в $G$, что $(i, G[i])$ предшествует ему. $color$ инициализируется красными.

'''var''' candidate: array[[Файл:https://pp1.userapi.comn] of integer initially 0;<font color="green"> /c846120/v846120267vector clock from the candidate state</1099bfont> Upon receiving the token (G, color) '''while''' (color[i] = red) '''do''' receive candidate from application process P '''if''' (candidate[i] > G [i]) '''then''' G [i] := candidate[i]; color[i] := green; '''for''' j := 1 '''to''' n, (j != i) '''do''' '''if''' (candidate[j] >= G [j]) '''then''' G [j] := candidate[j]; color[j]:= red; '''if''' (<tex>\exists j</Y98QwD2teI0.jpg]tex>: color[j]= red) '''then''' send token to <tex>M_j</tex> ; '''else''' detect := '''true''';