Инициатор посылает сообщения всем своим соседям. После получения первого сообщения не-инициатор пересылает сообщения всем своим соседям, кроме того, от которого было получено сообщение. Когда не-инициатор получает сообщения от всех своих соседей, эхо пересылается родителю (father). Когда инициатор получает сообщения от всех своих соседей, он принимает решение.
var recp : integer init 0 ; (* Счетчик полученных сообщений *)
fatherp : P init udef ;
Для инициатора:
begin forall q Î Neighpdo send <tok> to q ;
while recp < # Neighpdo
begin receive <tok> ; recp := recp + 1 end ;
decide
end ;
Для не-инициатора:
begin receive <tok> from neighbor q ; fatherp := q ; recp := recp + 1 ;
forall q Î Neighp, q ¹ fatherpdo send <tok> to q ;
while recp < # Neighpdo
begin receive <tok> ; recp := recp + 1 end ;
send <tok> to fatherp
end
Алгоритм 6.5 Эхо-алгоритм.
Теорема 6.17 Эхо-алгоритм (Алгоритм 6.5) является волновым алгоритмом.
Доказательство. Т.к. каждый процесс посылает не более одного сообщения по каждому инцидентному каналу, количество сообщений, пересылаемых за каждое вычисление, конечно. Пусть ¡ - конечная конфигурация, достигаемая в вычислении C с инициатором p0.
Для этой конфигурации определим (подобно определению в лемме 6.3) граф T = (P,ET), где pq Î ET Û fatherp = q. Чтобы показать, что этот граф является деревом, нужно показать, что количество ребер на единицу меньше, чем количество вершин (Лемма 6.3 утверждает, что T - дерево, но предполагается, что алгоритм является волновым, что нам еще нужно доказать). Отметим, что каждый процесс, участвующий в C, посылает сообщения всем своим соседям, кроме соседа, от которого он получил первое сообщение (если процесс - не-инициатор). Отсюда следует, что все его соседи получают хотя бы одно сообщение в C и также участвуют в C. Из этого следует, что fatherp ¹ udef для всех p ¹ p0. Что T не содержит циклов, можно показать, как в доказательстве Леммы 6.3.
В корне дерева находится p0; обозначим через Tp множество вершин в поддереве p. Ребра сети, не принадлежащие T, называются листовыми ребрами (frond edges). В ¡ каждый процесс p, по крайней мере, послал сообщения всем своим соседям, кроме родителя fatherp, следовательно, каждое листовое ребро передавало в C сообщения в обоих направлениях. Пусть fp - событие, в котором p посылает сообщение своему родителю (если в C это происходит), а gp - событие, в котором родитель p получает сообщение от p (если это происходит). С помощью индукции по вершинам дерева можно показать, что
(1) C содержит событие fp для любого p ¹ p0;
(2) для всех s Î Tp существует событие e Î Cs такое, что e p gp.
Мы рассмотрим следующие два случая.
p - лист. p получил в C сообщение от своего родителя и от всех других соседей (т.к. все остальные каналы - листовые). Таким образом, посылка <tok> родителю p была возможна, и, т.к. ¡ - конечная конфигурация, это произошло. Tp содержит только p, и, очевидно, fpp gp.
p - не лист. p получил в C сообщение от своего родителя и через все листовые ребра. По индукции, C содержит fp¢ для каждой дочерней вершины p¢ вершины p, и, т.к. ¡ - конечная конфигурация, C также содержит gp¢. Следовательно, посылка <tok> родителю p была возможна, и, т.к. ¡ - конечная конфигурация, это произошло. Tp состоит из объединения Tp¢ по всем дочерним вершинам p и из самого p. С помощью индукции можно показать, что в каждом процессе этого множества существует событие, предшествующее gp.
Отсюда следует, также, что p0 получил сообщение от каждого соседа и выполнил событие decide, которому предшествуют события в каждом процессе.
Остовное дерево, которое строится в вычислении Алгоритма 6.5, иногда используют в последовательно выполняемых алгоритмах. (Например, алгоритм Мерлина-Сегалла (Merlin-Segall) для вычисления таблиц кратчайших маршрутов предполагает, что изначально дано остовное дерево с корнем в v0; см. Подраздел 4.2.3. Начальное остовное дерево может быть вычислено с использованием эхо-алгоритма). В последней конфигурации алгоритма каждый процесс (кроме p0) запомнил, какой сосед в дереве является его родителем, но не запомнил дочерних вершин. В алгоритме одинаковые сообщения принимаются от родителя, через листовые ребра, и от дочерних вершин. Если требуется знание дочерних вершин в дереве, алгоритм может быть слегка изменен, так чтобы отправлять родителю сообщения, отличные от остальных (в последней операции отправления сообщения для не-инициаторов). Дочерними вершинами процесса тогда являются те соседи, от которых были получены эти сообщения.
В сетях с топологией клика между каждой парой процессов существует канал. Процесс может определить, получил ли он сообщение от каждого соседа. В алгоритме опроса, обозначенном как Алгоритм 6.6, инициатор запрашивает у каждого соседа ответ на сообщение и принимает решение после получения всех ответных сообщений.
Теорема 6.18 Алгоритм опроса (Алгоритм 6.6) является волновым алгоритмом.
Доказательство. Алгоритм пересылает по два сообщения через каждый канал, смежный с инициатором. Каждый сосед инициатора отвечает только один раз на первоначальный опрос, следовательно, инициатор получает N-1 ответ. Этого достаточно, чтобы принять решение, следовательно, инициатор принимает решение и ему предшествует событие в каждом процессе.
Опрос может быть использован и в сети с топологией звезда, в которой инициатор находится в центре.
var recp : integer init 0 ; (* только для инициатора *)
Для инициатора:
begin forall q Î Neighpdo send <tok> to q ;
while recp < # Neighpdo
begin receive <tok> ; recp := recp + 1 end ;
decide
end ;
Для не-инициатора:
begin receive <tok> from q ; send <tok> to q end
Алгоритм 6.6 Алгоритм опроса.
В этом разделе будет представлен фазовый алгоритм, который является децентрализованным алгоритмом для сетей с произвольной топологией. Алгоритм дан в [Tel91b, Раздел 4.2.3]. Алгоритм может использоваться как волновой для ориентированных сетей.
Алгоритм требует, чтобы процессам был известен диаметр сети, обозначенный в тексте алгоритма как D. Алгоритм остается корректным (хотя и менее эффективным), если процессы вместо D используют константу D¢ > D. Таким образом, для применения алгоритма необязательно точно знать диаметр сети; достаточно, если известна верхняя граница диаметра (например, N-1). Все процессы должны использовать одну и ту же константу D¢. Пелег [Peleg; Pel90] дополнил алгоритм таким образом, чтобы диаметр вычислялся во время выполнения, но это расширение требует уникальной идентификации.
Общий случай. Алгоритм может использоваться в ориентированных сетях произвольной топологии, где каналы могут передавать сообщения только в одном направлении. В этом случае, соседи p являются соседями по входу (процессы, которые могут посылать сообщения p) и соседями по выходу (процессы, которым p может посылать сообщения). Соседи по входу p содержатся в множестве Inp, а соседи по выходу - в множестве Outp.
В фазовом алгоритме каждый процесс посылает ровно D сообщений каждому соседу по выходу. Только после того, как i сообщений было получено от каждого соседа по входу, (i+1)-ое сообщение посылается каждому соседу по выходу; см. алгоритм 6.7.
cons D : integer = диаметр сети ;
var recp[q] : 0..D init 0, для каждого q Î Inp ;
(* Количество сообщений, полученных от q *)
Sentp : 0..D init 0 ;
(* Количество сообщений, посланных каждому соседу по выходу *)
begin if p - инициатор then
begin forall r Î Outpdo send <tok> to r ;
Sentp := Sentp + 1
end ;
while minq Recp[q] < D do
begin receive <tok> (от соседа q0) ;
Recp[q0] := Recp[q0] + 1 ;
if minq Recp[q] ³ Sentpand Sentp < D then
begin forall r Î Outpdo send <tok> to r ;
Sentp := Sentp + 1
end
end ;
decide
end
Алгоритм 6.7 Фазовый алгоритм.
Действительно, из текста алгоритма очевидно, что через каждый канал проходит не более D сообщений (ниже показано, что через каждый канал проходит не менее D сообщений). Если существует ребро pq, то fpq(i) - i-е событие, в котором p передает сообщение q, а gpq(i) - i-е событие, в котором q получает сообщение от p. Если канал между p и q удовлетворяет дисциплине FIFO, эти события соответствуют друг другу и неравенство fpq(i)p gpq(i) выполняется. Каузальные отношения между fpq(i) и gpq(i) сохраняются и в случае, если канал не является FIFO, что доказывается в следующей лемме.
Лемма 6.19 Неравенство fpq(i)p gpq(i) выполняется, даже если канал не является каналом FIFO.
Доказательство. Определим mh следующим образом: fpq(mh) - событие отправления сообщения, соответствующее gpq(h), т.е. в своем h-м событии получения q получает mh-е сообщение p. Из определения каузальности fpq(mh)p gpq(h).
Т.к. каждое сообщение в C получают только один раз, все mh различны, откуда следует, что хотя бы одно из чисел m1, ..., mi больше или равно i. Выберем j £ i так, чтобы mj ³ i. Тогда fpq(i)p fpq(mj)p gpq(j)p gpq(i).