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

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

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

Отсюда следует, также, что p₀ получил сообщение от каждого соседа и выполнил событие decide, которому предшествуют события в каждом процессе.

Остовное дерево, которое строится в вычислении Алгоритма 6.5, иногда используют в последовательно выполняемых алгоритмах. (Например, алгоритм Мерлина-Сегалла (Merlin-Segall) для вычисления таблиц кратчайших маршрутов предполагает, что изначально дано остовное дерево с корнем в v₀; см. Подраздел 4.2.3. Начальное остовное дерево может быть вычислено с использованием эхо-алгоритма). В последней конфигурации алгоритма каждый процесс (кроме p₀) запомнил, какой сосед в дереве является его родителем, но не запомнил дочерних вершин. В алгоритме одинаковые сообщения принимаются от родителя, через листовые ребра, и от дочерних вершин. Если требуется знание дочерних вершин в дереве, алгоритм может быть слегка изменен, так чтобы отправлять родителю сообщения, отличные от остальных (в последней операции отправления сообщения для не-инициаторов). Дочерними вершинами процесса тогда являются те соседи, от которых были получены эти сообщения.

6.2.4 Алгоритм опроса

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

Теорема 6.18 Алгоритм опроса (Алгоритм 6.6) является волновым алгоритмом.

Доказательство. Алгоритм пересылает по два сообщения через каждый канал, смежный с инициатором. Каждый сосед инициатора отвечает только один раз на первоначальный опрос, следовательно, инициатор получает N-1 ответ. Этого достаточно, чтобы принять решение, следовательно, инициатор принимает решение и ему предшествует событие в каждом процессе.

Опрос может быть использован и в сети с топологией звезда, в которой инициатор находится в центре.

var rec_p : integer init 0 ; (* только для инициатора *)

Для инициатора:

begin forall q  Neigh_p do send <tok> to q ;

while rec_p < # Neigh_p do

begin receive <tok> ; rec_p := rec_p + 1 end ;

decide

end ;

Для не-инициатора:

begin receive <tok> from q ; send <tok> to q end

Алгоритм 6.6 Алгоритм опроса.

6.2.5 Фазовый алгоритм

В этом разделе будет представлен фазовый алгоритм, который является децентрализованным алгоритмом для сетей с произвольной топологией. Алгоритм дан в [Tel91b, Раздел 4.2.3]. Алгоритм может использоваться как волновой для ориентированных сетей.

Алгоритм требует, чтобы процессам был известен диаметр сети, обозначенный в тексте алгоритма как D. Алгоритм остается корректным (хотя и менее эффективным), если процессы вместо D используют константу D > D. Таким образом, для применения алгоритма необязательно точно знать диаметр сети; достаточно, если известна верхняя граница диаметра (например, N-1). Все процессы должны использовать одну и ту же константу D. Пелег [Peleg; Pel90] дополнил алгоритм таким образом, чтобы диаметр вычислялся во время выполнения, но это расширение требует уникальной идентификации.

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

В фазовом алгоритме каждый процесс посылает ровно D сообщений каждому соседу по выходу. Только после того, как i сообщений было получено от каждого соседа по входу, (i+1)-ое сообщение посылается каждому соседу по выходу; см. алгоритм 6.7.

cons D : integer = диаметр сети ;

var rec_p[q] : 0..D init 0, для каждого q  In_p ;

(* Количество сообщений, полученных от q *)

Sent_p : 0..D init 0 ;

(* Количество сообщений, посланных каждому соседу по выходу *)

begin if p - инициатор then

begin forall r  Out_p do send <tok> to r ;

Sent_p := Sent_p + 1

end ;

while min_q Rec_p[q] < D do

begin receive <tok> (от соседа q₀) ;

Rec_p[q₀] := Rec_p[q₀] + 1 ;

if min_q Rec_p[q]  Sent_p and Sent_p < D then

begin forall r  Out_p do send <tok> to r ;

Sent_p := Sent_p + 1

end

end ;

decide

end

Алгоритм 6.7 Фазовый алгоритм.

Действительно, из текста алгоритма очевидно, что через каждый канал проходит не более D сообщений (ниже показано, что через каждый канал проходит не менее D сообщений). Если существует ребро pq, то f_pq⁽ⁱ⁾ - i-е событие, в котором p передает сообщение q, а g_pq⁽ⁱ⁾ - i-е событие, в котором q получает сообщение от p. Если канал между p и q удовлетворяет дисциплине FIFO, эти события соответствуют друг другу и неравенство f_pq⁽ⁱ⁾  g_pq⁽ⁱ⁾ выполняется. Каузальные отношения между f_pq⁽ⁱ⁾ и g_pq⁽ⁱ⁾ сохраняются и в случае, если канал не является FIFO, что доказывается в следующей лемме.

Лемма 6.19 Неравенство f_pq⁽ⁱ⁾  g_pq⁽ⁱ⁾ выполняется, даже если канал не является каналом FIFO.

Доказательство. Определим m_h следующим образом: f_pq^(mh) - событие отправления сообщения, соответствующее g_pq^(h), т.е. в своем h-м событии получения q получает m_h-е сообщение p. Из определения каузальности f_pq^(mh)  g_pq^(h).

Т.к. каждое сообщение в C получают только один раз, все m_h различны, откуда следует, что хотя бы одно из чисел m₁, ..., m_i больше или равно i. Выберем j  i так, чтобы m_j  i. Тогда f_pq⁽ⁱ⁾  f_pq^(mj)  g_pq^(j)  g_pq⁽ⁱ⁾.

Теорема 6.20 Фазовый алгоритм (Алгоритм 6.7) является волновым алгоритмом.

Доказательство. Т.к. каждый процесс посылает не более D сообщений по каждому каналу, алгоритм завершается за конечное число шагов. Пусть  - заключительная конфигурация вычисления C алгоритма, и предположим, что в C существует, по крайней мере, один инициатор (их может быть больше).

Чтобы продемонстрировать, что в  каждый процесс принял решение, покажем сначала, что каждый процесс хотя бы один раз послал сообщения. Т.к. в  по каналам не передается ни одно сообщение, для каждого канала qp Rec_p[q] = Sent_pq. Также, т.к. каждый процесс посылает сообщения, как только получит сообщение сам, Rec_p[q] > 0  Sent_p > 0. Из предположения, что существует хотя бы один инициатор p₀, для которого Sent_p0 > 0, следует, что Sent_p > 0 для каждого p.

Впоследствии будет показано, что каждый процесс принял решение. Пусть p - процесс с минимальным значением переменной Sent в , т.е. для всех q Sent_q  Sent_p в . В частности, это выполняется, если q - сосед по входу p, и из Rec_p[q] = Sent_q следует, что min_q Rec_p[q]  Sent_p. Но отсюда следует, что Sent_p = D; иначе p послал бы дополнительные сообщения, когда он получил последнее сообщение. Следовательно, Sent_p = D для всех p, и Rec_p[q] = D для всех qp, откуда действительно следует, что каждый процесс принял решение.

Остается показать, что каждому решению предшествует событие в каждом процессе. Если P = p₀, p₁, ..., p_l (l  D) - маршрут в сети, тогда, по Лемме 6.19,

для 0  i < l и, по алгоритму,

для 0  i < l - 1. Следовательно, . Т.к. диаметр сети равен D, для любых q и p существует маршрут q = p₀, p₁, ..., p_l = p длины не более D. Таким образом, для любого q существует l  D и сосед по входу r процесса p, такие, что ; на основании алгоритма, предшествует d_p.

Алгоритм пересылает D сообщений через каждый канал, что приводит в сложности сообщений, равной |E|*D. Однако нужно заметить, что |E| обозначает количество направленных каналов. Если алгоритм используется для неориентированной сети, каждый канал считается за два направленных канала, и сложность сообщений равна 2|E|*D.

var rec_p : 0..N - 1 init 0 ;

(* Количество полученных сообщений *)

Sent_p : 0..1 init 0 ;

(* Количество сообщений, посланных каждому соседу *)

begin if p - инициатор then

begin forall r  Neigh_p do send <tok> to r ;

Sent_p := Sent_p + 1

end ;

while Rec_p < # Neigh_p do

begin receive <tok> ;

Rec_p := Rec_p + 1 ;

if Sent_p = 0 then

begin forall r  Neigh_p do send <tok> to r ;

Sent_p := Sent_p + 1

end

end ;

decide

end

Алгоритм 6.8 Фазовый алгоритм для клики.

Фазовый алгоритм для клики. Если сеть имеет топологию клика, ее диаметр равен 1; в этом случае от каждого соседа должно быть получено ровно одно сообщение, и для каждого процесса достаточно посчитать общее количество полученных сообщений вместо того, чтобы считать сообщения от каждого соседа по входу отдельно; см. Алгоритм 6.8. Сложность сообщений в этом случае равна N(N-1) и алгоритм использует только O(log N) бит оперативной памяти.

6.2.6 Алгоритм Финна

Алгоритм Финна [Fin79] - еще один волновой алгоритм, который можно использовать в ориентированных сетях произвольной топологии. Он не требует того, чтобы диаметр сети был известен заранее, но подразумевает наличие уникальных идентификаторов процессов. В сообщениях передаются множества идентификаторов процессов, что приводит к довольно высокой битовой сложности алгоритма.

Процесс p содержит два множества идентификаторов процессов, Inc_p и NInc_p. Неформально говоря, Inc_p - это множество процессов q таких, что событие в q предшествует последнему произошедшему событию в p, а NInc_p - множество процессов q таких, что для всех соседей r процесса q событие в r предшествует последнему произошедшему событию в p. Эта зависимость поддерживается следующим образом. Изначально Inc_p = {p}, а NInc_p = . Каждый раз, когда одно из множеств пополняется, процесс p посылает сообщение, включая в него Inc_p и NInc_p. Когда p получает сообщение, включающее множества Inc и NInc, полученные идентификаторы включаются в версии этих множеств в процессе p. Когда p получит сообщения от всех соседей по входу, p включается в NInc_p. Когда два множества становятся равны, p принимает решение; см. Алгоритм 6.9. Из неформального смысла двух множеств следует, что для каждого процесса q такого, что событие в q предшествует d_p, выполняется следующее: для каждого соседа r процесса q событие в r также предшествует d_p, откуда следует зависимость алгоритма.

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

Теорема 6.21 Алгоритм Финна (Алгоритм 6.9) является волновым алгоритмом.

Доказательство. Заметим, что два множества, поддерживаемые каждым процессом, могут только расширяться. Т.к. размер двух множеств в сумме составляет не менее 1 в первом сообщении, посылаемом по каждому каналу, и не более 2N в последнем сообщении, то общее количество сообщений ограничено 2N*|E|.

Пусть C - вычисление, в котором существует хотя бы один инициатор, и пусть  - заключительная конфигурация. Можно показать, как в доказательстве Теоремы 6.20, что если процесс p отправил сообщения хотя бы один раз (каждому соседу), а q - сосед p по выходу, то q тоже отправил сообщения хотя бы один раз. Отсюда следует, что каждый процесс переслал хотя бы одно сообщение (через каждый канал).

var Inc_p : set of processes init {p} ;

NInc_p : set of processes init  ;

rec_p[q] : boolean for q  In_p init false ;

(* признак того, получил ли p сообщение от q *)

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

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