ref (664672), страница 34

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 34)

Проверка пустоты всех деревьев выполняется отдельной волной. Лес поддерживает дополнительное свойство, что если дерево T_p стало пустым, оно остается пустым и после этого. Обратите внимание, что это не мешает p стать активным; если p становится активным после разрушения дерева, p вставляется в дерево другого инициатора. Каждый процесс участвует в волне только, если его дерево разрушилось; когда волна принимает решение, вызывается алгоритм объявления. (вызов объявления не нужен, если выбранный волновой алгоритм генерирует решение в каждом процессе; в этом случае, процесс просто останавливается после принятия решения и завершения волнового алгоритма.)

Алгоритм дается как Алгоритм 8.4, в котором волновой алгоритм не показан явно. Каждый процесс p имеет переменную father_p , которая не определена, если PV_T, и равна p если p является корнем или равна отцу p, если p не-корень в F. Переменная sс_p содержит число сыновей p в F. Логическая переменная empty истинна, тогда и только тогда, когда дерево p пусто.

Доказательство правильности алгоритма подобно доказательству Dijkstra-Scholten алгоритма. Для любой конфигурации  Алгоритма 8.4, определим

V_F = {p : father_p  udef} U {передается (mes, p) } U {передается (sig,p) }

И

Ep = {(P, father_p ): father_p  udef  father_p  p}

U {((mes, p), p) : (mes, p) передается } U {((sig,p}, p) : (sig,p} передается }.

Безопасность алгоритма будет следовать от утверждения Q, определенный ниже. Это инвариант алгоритма, и доказательство инвариантности подобно доказательству Lemma 8.4. Значение пунктов (1)-(5) из Q такие же как для инварианта алгоритма Dijkstra-Scholten и пункт (6) выражает тот факт, что каждый процесс правильно отслеживает,является ли он все еще корнем дерева в лесе. Конечно, лес пуст, если никакой процесс не является корнем.

Q  state_p = active  p  V_F (1)

 (u, v) E_F  u V_F  v V_F  P (2)

 sc_p = #{ v : (v, p)  Ep } (3)

 V_F  F is a forest (4)

 (state_p = passive A sc_p = 0)  p  Vp (5)

 empty_p  Tp is empty (6)

Lemma 8.6 Q - инвариант Shavit-Francez алгоритма.

Доказательство. Первоначально state_p = passive для каждого не-инициатора p, и father_p = p для каждого инициатора p, что доказывает (1). Также, Ep = , что доказывает (2). Так как sc_p = 0 для каждого p, (3) удовлетворяется. V_F = {p : p -инициатор} и E_F = , так что F - лес, состоящий из деревьев, содержащих один узел для каждого инициатора, что доказывает (4). Процессы в V_F - инициаторы, которые являются активными; это доказывает (5). Первоначально empty_p равны (p - не-инициатор) и T_p действительно пуст, тогда и только тогда, когда p - не инициатор, что доказывает (6).

S_p: Никакой процесс не становится активным в S_p, и никакой процесс не удаляется из V_F, таким образом (1) сохраняется.

Применимость действия означает, что p, отец нового узла, находится в V_F, таким образом (2) сохраняется.

В результате действия, V_F пополняется вершиной (mes, p) и E_F ребром ((mes, p), p), что означает, что F остается лесом, и sc_p правильно увеличивается на единицу, чтобы представить наличие нового сына процесса p, таким образом (3) и (4) сохраняются.

Никакой процесс не становится пассивным листом, и никакой процесс не вставляется в V_F, таким образом (5) сохраняется.

Поскольку новый лист добавлен в не-пустое дерево, никакое дерево не становится непустым, и поскольку ни одна переменная empty не изменяется, (6) сохраняется.

R_p: p уже был в V_F (father_p  udef) или p вставлен после действия, таким образом (1) сохраняется.

Если значение father_p определено, его новое значение - q, и если послан сигнал, его отец также q, и q находится в V_T , таким образом (2) сохраняется.

Число сыновей процесса q не изменяется, потому что сын (mes, q) процесса q заменяется сыном p или сыном (sig, q), таким образом sc_q оставляет правильным (3).

Структура графа не изменяется, таким образом (4) сохраняется. Никакой процесс не становится пассивным листом, и никакой процесс не вставляется в V_F, таким образом (5) сохраняется.

Никакое дерево не становится пустым, следовательно (6) сохраняется.

I_p: Перевод p в пассивное состояние сохраняет (1), (2), (3), и (4). То, что p прежде был активен означает, что p был в V_F. Если sc_p = 0, p удаляется из V_F, таким образом (5) сохраняется.

Затем мы рассмотрим что случится, если p удалить из F, то есть если p окажется, пассивным листом F. Если послан сигнал, отец сигнала - последний отец процесса p, который находится в V_F, следовательно (2) сохраняется. В этом случае, сигнал заменяет p на сына процесса father_p , следовательно sc_{father p} остается правильным, и (3) сохраняется. Структура графа не изменилась, следовательно (4) сохраняется. Никакое дерево не становится пустым, таким образом (6) сохраняется. Иначе, то есть, если father_p = p, p был корнем и то, что p является листом означает, что p единственная иуршина в T_p ,таким образом ее удаление делает T_p пустым и присваивание empty_p сохраняет (6).

var state_p : (active, passive) init if p is initiator then active else passive ;

sc_p : integer init 0 ;

father_p : P init if p is initiator then p else udef ;

empty_p : boolean init if p is initiator then false else true ;

S_p: { state_p = active }

begin send (mes, p) ; sc_p := sc_p + 1 end

R_p: { Сообщение (mes, q) пришло в p }

begin receive (mes, q) ; state_p := active ;

if father_p = udef then father_p := q else send ( sig, q ) to q

end

I_p: { state_p = active }

begin state_p := passive ;

if sc_p = 0 then (* Delete p from F *)

begin if father_p = p then empty_p := true else send ( sig, father_p } to father_p ;

father_p := udef

end

end

A_p: { Сигнал (sig,p) пришел в p }

begin receive (sig,p) ; sc_p := sc_p - 1;

if sc_p = 0 and state_p = passive then

begin if father_p = p then empty_p := true else send ( sig, father_p ) to father_p ;

father_p := udef

end

end

Процессы одновременно выполняют волновой алгоритм, в котором посылка или принятие решения процессом p разрешается только, если empty_p истина и тогда decide вызывает алгоритм объявления .

Алгоритм 8.4 shavit-francez алгоритм.

A_p: получение сигнала уменьшает число сыновей процесса p на единицу, и присваивание sc_p гарантирует, что (3) сохраняется. То, что p был отцом сигнала означает, что p был в V_F. Если state_p=passive и после получение сигнала sc_p = 0, p удаляется, таким образом (5) сохраняется.

Если p удаляется из V_F, инвариант сохраняется по тем же причинам, что и при действии I_p.

Теорема 8.7 Алгоритм Shavit-Francez (Алгоритм 8.4) - правильный алгоритм обнаружения завершения и использует М + W управляющих сообщени.

Доказательство. Также как в Теореме 8.5 можно показано, что число сигналов не превышает число основных сообщений. Помимо сигналов, управляющий алгоритм только посылает сообщения для одной волны. Из этого следует, что послано не более М + W управляющих сообщений.

Чтобы доказать живость алгоритма предположим, что основное вычисление закончилось. За конечное число шагов алгоритм обнаружения завершения достигает конечной конфигурации, и можно показать, как это было сделано в Теореме 8.5, что в этой конфигурации F пуст. Следовательно, все события волны возможны в каждом процессе, и то, что конфигурация является конечной теперь означает, что все события волны были выполнены, включая по крайней мере одно принятие решения, при котором был вызван алгоритм объявления.

Чтобы доказывать безопасность, обратим внимание на то, что алгоритм объявления вызывается после принятия решения в волновом алгоритме. Это означает, что каждый процесс p послал сообщение волны или принял решение, и из алгоритма следует, что empty_p истина, когда p сделает это. Никакое действие не присваивает переменной empty значение ложь повторно, так что (для каждого p) empty_p истина, когда вызывается алгоритм объявления. Из (6), V_F пусто, что имеет следствием term. 

Число управляющих сообщений, используемых алгоритмом Shavit-Francez имеет тот же порядок, что и нижнии границы, выведенные в Теоремах 8.2 и 8.3. Алгоритм является оптимальным алгоритмом для обнаружения завершения децентрализованных вычислений для худшего случая (если используется оптимальный волновой алгоритм).

Применение алгоритмов, рассматриваемых в этом разделе требует, чтобы каналы связи были двунаправленными; для каждого основного сообщения, посланного от p в q сигнал должен быть послан от q в p. Сложность с средним случаем равняется сложности в худшем случае; каждое выполнение требует одного сигнального сообщения на одно основное сообщение и, в случае Shavit-Francez алгоритма, точно одного выполнение волны.

8.3 Решения, основанные на волнах

По двум причинам полезно рассмотреть некоторые другие алгоритмы для обнаружения завершения кроме двух алгоритмов, данных в Разделе 8.2. Во первых,

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

В этом разделе будут изучаться некоторые алгоритмы, основанные на повторном выполнении алгоритма волны; в конце каждой волны, либо обнаружевается завершение, либо начинается новая волна. Завершение обнаружено, если локальное условие окажется удовлетворенным в каждом процессе.

Сначала мы рассмотрим конкретные примеры алгоритмов, в которых во всех случаях волновой алгоритм является кольцевым алгоритмом. Для этого предположим, что кольцо вложено как подтопология сети ; но обмен основными сообщениями не ограничен каналам, принадлежащими к кольцу. Процессы перенумерованы с p_o до p_{N -1} и кольцевой алгоритм начинается процессом p_o , посылая маркер процессу p_{N -1}. Процесс p_{i + 1} (для i < N -1) передает маркер процессу p_i. Передвижение маркера заканчивается, когда маркер получает процесс p₀.

Первое решение, обсуждаемое в этом классе - алгоритм Dijkstra, Feijen, и Van Gasteren (Подраздел 8.3.1); этот алгоритм обнаруживает завершение вычислений с синхронным прохождением сообщений. Несколько авторов обобщили алгоритм для вычислений с асинхронным прохождением сообщений; главная проблема здесь состоит в том, чтобы проверить, что каналы связи пусты. Мы обсуждаем решение Safra (Подраздел 8.3.2), в котором в каждом процессе подсчитывается число сообщений, которые посланы и получены; сравнивая счетчики можно определить действительно ли каналы являются пустыми. Также возможно использовать подтверждения для этой цели (Подраздел 8.3.3); но это решение снова требует, чтобы каналы были двунаправленными и чтобы число управляющих сообщений равнялось по крайней мере числу, используемому алгоритмом Shavit-Francez.

В Подразделе 8.3.4 принцип обнаружения будет обобщен для использования произвольного волнового алгоритма.

Характеристики

Список файлов реферата