Распределённый алгоритм для WCP

Распределенный алгоритм для WCP – алгоритм для поиска наименьшего (проще говоря, самого левого) согласованного среза в котором выполняется слабый конъюнктивный предикат.

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

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

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

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

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

Работа $i$-го монитор-процесса описана следующим псевдокодом. Гарантируется: когда переменная $detect = true$, мы получим искомый срез.

Псевдокод

 var candidate: array[1..n] of integer initially 0; // vector clock from the candidate state
 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 ([math]\exists j[/math]: color[j] = red) then send token to [math]M_j[/math] ;
 else detect := true;