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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
 
'''Распределенный алгоритм для WCP''' – алгоритм для поиска наименьшего (проще говоря, самого левого) [[Срез, согласованный срез|согласованного среза]] в котором выполняется [[Слабый конъюнктивный предикат (WCP)|слабый конъюнктивный предикат]].
 
'''Распределенный алгоритм для WCP''' – алгоритм для поиска наименьшего (проще говоря, самого левого) [[Срез, согласованный срез|согласованного среза]] в котором выполняется [[Слабый конъюнктивный предикат (WCP)|слабый конъюнктивный предикат]].
  
В распределенном алгоритме используются [[Векторные часы|векторные часы]], как и в [[Централизованный алгоритм для WCP|централизованном]] (они вообще похожи, рекомендуется сначала понять централизованный).
+
В распределенном алгоритме используются [[Векторные часы|векторные часы]].
  
В дополнение к каждому из $N$ процессов заведем еще $N$ координаторов (вместо одного на всех), где каждый процесс связан со своим координатором.
+
В дополнение к каждому из $N$ процессов заведем еще $N$ монитор-процессов, где каждый процесс связан со своим монитор-процессом. Монитор-процессы отправляют друг другу так называемый ''токен'' (его описание ниже) и получают вектор часов от соответствующих процессов.
Каждый процесс отправляет сообщения либо другим процессам, либо своему координатору (каждый раз, когда выполняется локальный предикат и увеличились векторные часы).
 
Каждый координатор отправляет сообщения только другим координаторам.
 
  
В каждый момент времени ровно у одного координатора есть ''токен''.
+
Токен состоит из двух векторов. Первый назовем $G$. $G[i] = k$ означает, что состояние номер $k$ $i$-го процесса входит в срез-кандидат. Важно, что этот срез может не быть согласованным, но все состояния в нем удовлетворяют локальным предикатам. $G$ инициализируется нулями.
Токен у координатора $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$ инициализируется красными.
  
Второй вектор назовем $color$, где $color[i]$ обозначает цвет состояния среза-кандидата для $i$-го процесса. Цвет состояния может быть красным или зеленым. Если $color[i]$ равен красному, то состояние $(i, G [i])$ и все его предшествующие состояния уже красные и никогда не смогут удовлетворить $WCP$ из согласованного среза. Если $color[i]$ зеленый, то нет такого состояния в $G$, что $(i, G[i])$ предшествует ему. $color$ инициализируется красными.
+
Работа $i$-го монитор-процесса описана следующим псевдокодом. Гарантируется: когда переменная $detect = true$, мы получим искомый срез.
 +
=== Псевдокод ===
  
Работа $i$-го монитор-процесса описана следующим псевдокодом. Гарантируется: когда переменная $detect = true$, мы получим искомый срез.
 
  
=== Псевдокод ===
+
 
 
+
    <font color="green"> // vector clock from the candidate state</font>
   '''var''' candidate: array[1..n] of integer initially 0;<font color="green"> // vector clock from the candidate state</font>
+
   '''var''' candidate: array[1..n] of integer initially 0;
 
   Upon receiving the token (G, color)
 
   Upon receiving the token (G, color)
 
   '''while''' (color[i] = red) '''do'''
 
   '''while''' (color[i] = red) '''do'''

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)