Часть 2 Фундаментальные алгоритмы 2 глава

Из связности сети следует, что (см. Рис.6.4)

T_pq = и P =

 

Рис. 6.4 Поддеревья T_pq.

 

Оператор forall в комментариях в Алгоритме 6.3 будет обсуждаться в конце этого подраздела; в следующей теореме речь идет об алгоритме без этого оператора.

Теорема 6.16 Древовидный алгоритм (Алгоритм 6.3) является волновым алгоритмом.

Доказательство. Т.к. каждый процесс посылает не более одного сообщения, в целом алгоритм использует не более N сообщений. Отсюда следует, что алгоритм достигает заключительной конфигурации ¡ за конечное число шагов; мы покажем, что в ¡ хотя бы один процесс выполняет событие decide.

Пусть F - количество битов rec со значением false в ¡, а K - количество процессов, которые уже послали сообщения в ¡. Т.к. в ¡ не передается ни одно сообщение (иначе ¡ не была бы заключительной), F = (2N-2) - K; общее число битов rec равно 2N-2, а K из них равны true.

Предположим, что ни один процесс в ¡ не принял решения. N-K процессов, которые еще не послали сообщение в ¡, содержат хотя бы по два бита rec, равных false; иначе они бы могли послать сообщение, что противоречит тому, что ¡ - заключительная конфигурация. K процессов, которые послали сообщение в ¡, содержат хотя бы один бит rec, равный false; иначе они могли бы принять решение, что противоречит тому, что ¡ - заключительная конфигурация. Итак, F ³ 2(N-K) + K, а из (2N-2) - K ³ 2(N-K) + K следует, что -2 ³ 0; мы пришли к противоречию, следовательно, хотя бы один процесс в ¡ принимает решение. См. Упражнение 6.5.

 Наконец, нужно показать, что решению предшествует событие в каждом процессе. Пусть f_pq - событие, где p посылает сообщение q, а g_pq - событие, где q получает сообщение от p. Применяя индукцию по событиям получения сообщений, можно доказать, что " s Î T_pq $ e Î C_s: e p g_pq.

Предположим, что это выполняется для всех событий получения сообщений, предшествующих g_pq. Из того, что событию g_pq предшествует f_pq (в процессе p), и из алгоритма p следует, что для всех r Î Neigh_p при r ¹ q, g_rp предшествует f_pq. Из гипотезы индукции следует, что для всех таких r и для всех s Î T_rp существует событие e Î C_s, где e p g_rp, следовательно, e p g_pq.

Решению d_p в p предшествуют g_rp для всех r Î Neigh_p, откуда следует, что " s Î P $ e Î C_s : e p d_p.

Читатель может смоделировать вычисление алгоритма на небольшом дереве (например, см. дерево на Рис.6.4) и самостоятельно убедиться в справедливости следующих замечаний. В Алгоритме 6.3 существует два процесса, которые получают сообщения через все свои каналы и принимают решение; все остальные тем временем ожидают сообщения с счетчиком команд, установленным на x, в заключительной конфигурации. Если к программе добавить оператор forall (в скобках комментария в Алгоритме 6.3), то все процессы принимают решение и в конечной конфигурации каждый процесс находится в конечном состоянии. Модифицированная программа использует 2N-2 сообщений.

 

6.2.3 Эхо-алгоритм

Эхо-алгоритм - это централизованный волновой алгоритм для сетей произвольной топологии. Впервые он был представлен Чангом [Chang; Cha82] и поэтому иногда называется эхо-алгоритмом Чанга. Более эффективная версия, которая и представлена здесь, была предложена Сегаллом [Segall; Seg83].

Алгоритм распространяет сообщения < tok > по всем процессам, таким образом определяя остовное дерево, как определено в Лемме 6.3. Маркеры «отражаются» обратно через ребра этого дерева аналогично потоку сообщений в древовидном алгоритме. Алгоритм обозначен как Алгоритм 6.5.

Инициатор посылает сообщения всем своим соседям. После получения первого сообщения не-инициатор пересылает сообщения всем своим соседям, кроме того, от которого было получено сообщение. Когда не-инициатор получает сообщения от всех своих соседей, эхо пересылается родителю (father). Когда инициатор получает сообщения от всех своих соседей, он принимает решение.

 

var rec_p    : integer init 0; (* Счетчик полученных сообщений *)

  father_p: P       init udef;

 

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

     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 neighbor q; father_p:= q; rec_p:= rec_p + 1;

                 forall q Î Neigh_p, q ¹ father_p do send < tok > to q;

                 while rec_p < # Neigh_p do

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

                 send < tok > to father_p

     end

 

Алгоритм 6.5 Эхо-алгоритм.

Теорема 6.17 Эхо-алгоритм (Алгоритм 6.5) является волновым алгоритмом.

Доказательство. Т.к. каждый процесс посылает не более одного сообщения по каждому инцидентному каналу, количество сообщений, пересылаемых за каждое вычисление, конечно. Пусть ¡ - конечная конфигурация, достигаемая в вычислении C с инициатором p₀.

Для этой конфигурации определим (подобно определению в лемме 6.3) граф T = (P,E_T), где pq Î E_T Û father_p = q. Чтобы показать, что этот граф является деревом, нужно показать, что количество ребер на единицу меньше, чем количество вершин (Лемма 6.3 утверждает, что T - дерево, но предполагается, что алгоритм является волновым, что нам еще нужно доказать). Отметим, что каждый процесс, участвующий в C, посылает сообщения всем своим соседям, кроме соседа, от которого он получил первое сообщение (если процесс - не-инициатор). Отсюда следует, что все его соседи получают хотя бы одно сообщение в C и также участвуют в C. Из этого следует, что father_p ¹ udef для всех p ¹ p₀. Что T не содержит циклов, можно показать, как в доказательстве Леммы 6.3.

В корне дерева находится p₀; обозначим через T_p множество вершин в поддереве p. Ребра сети, не принадлежащие T, называются листовыми ребрами (frond edges). В ¡ каждый процесс p, по крайней мере, послал сообщения всем своим соседям, кроме родителя father_p, следовательно, каждое листовое ребро передавало в C сообщения в обоих направлениях. Пусть f_p - событие, в котором p посылает сообщение своему родителю (если в C это происходит), а g_p - событие, в котором родитель p получает сообщение от p (если это происходит). С помощью индукции по вершинам дерева можно показать, что

(1) C содержит событие f_p для любого p ¹ p₀;

(2) для всех s Î T_p существует событие e Î C_s такое, что e p g_p.

Мы рассмотрим следующие два случая.

p - лист. p получил в C сообщение от своего родителя и от всех других соседей (т.к. все остальные каналы - листовые). Таким образом, посылка < tok > родителю p была возможна, и, т.к. ¡ - конечная конфигурация, это произошло. T_p содержит только p, и, очевидно, f_p p g_p.

p - не лист. p получил в C сообщение от своего родителя и через все листовые ребра. По индукции, C содержит f_p¢ для каждой дочерней вершины p¢ вершины p, и, т.к. ¡ - конечная конфигурация, C также содержит g_p¢. Следовательно, посылка < tok > родителю p была возможна, и, т.к. ¡ - конечная конфигурация, это произошло. T_p состоит из объединения T_p¢ по всем дочерним вершинам p и из самого p. С помощью индукции можно показать, что в каждом процессе этого множества существует событие, предшествующее g_p.

Отсюда следует, также, что 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⁽ⁱ⁾ p g_pq⁽ⁱ⁾ выполняется. Каузальные отношения между f_pq⁽ⁱ⁾ и g_pq⁽ⁱ⁾ сохраняются и в случае, если канал не является FIFO, что доказывается в следующей лемме.

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

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

Т.к. каждое сообщение в C получают только один раз, все m_h различны, откуда следует, что хотя бы одно из чисел m₁,..., m_i больше или равно i. Выберем j £ i так, чтобы m_j ³ i. Тогда f_pq⁽ⁱ⁾ p f_pq^(mj) p g_pq^(j) p 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 *)

 

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

            forall r Î Out_p do send < sets, Inc_p, NInc_p> to r;

       while Inc_p ¹ NInc_p do

                begin receive < sets, Inc, NInc> from q₀;

                            Inc_p:= Inc_p È Inc; NInc_p:= NInc_p È NInc;

                            rec_p[q₀]:= true;

                            if "q Î In_p: rec_p[q] then NInc_p:= NInc_p È {p};

                            if  Inc_p или NInc_p изменились then

                                 forall r Î Out_p do send < sets, Inc_p, NInc_p> to r

                end;

       decide

End

 

Алгоритм 6.9 Алгоритм Финна.

Сейчас мы покажем, что в ¡ каждый процесс принял решение. Во-первых, если существует ребро pq, то Inc_p Í Inc_q в ¡. Действительно, после последнего изменения Inc_p процесс p посылает сообщение < sets, Inc_p, NInc_p>, и после его получения в q выполняется Inc_q:= Inc_q È Inc_p. Из сильной связности сети следует, что Inc_p = Inc_q для всех p и q. Т.к. выполняется p Î Inc_p и каждое множество Inc содержит только идентификаторы процессов, для каждого p Inc_p = P.

Во-вторых, подобным же образом может быть показано, что NInc_p = Ninc_q для любых p и q. Т.к. каждый процесс отправил хотя бы одно сообщение по каждому каналу, для каждого процесса p выполняется: " q Î In_p: rec_p[q], и следовательно, для каждого p выполняется: p Î NInc_p. Множества NInc содержат только идентификаторы процессов, откуда следует, что NInc_p = P для каждого p. Из Inc_p = P и NInc_p = P следует, что Inc_p = NInc_p, следовательно, каждый процесс p в ¡ принял решение.

Теперь нужно показать, что решению d_p в процессе p предшествуют события в каждом процессе. Для события e в процессе p обозначим через Inc^(e) (или, соответственно, NInc^(e)) значение Inc_p (NInc_p) сразу после выполнения e (сравните с доказательством Теоремы 6.12). Следующие два утверждения формализуют неформальные описания множеств в начале этого раздела.

Утверждение 6.22  Если существует событие e Î C_q: e p f, то q Î Inc^(f).

Доказательство. Как в доказательстве Теоремы 6.12, можно показать, что e p f Þ Inc^(e) Í Inc^(f), а при e Î C_q Þ q Î Inc^(e), что и требовалось доказать.

Утверждение 6.23  Если q Î NInc^(f), тогда для всех  r Î In_q существует событие e Î C_r: e p f.

Доказательство. Пусть a_q - внутреннее событие q, в котором впервые в q выполняется присваивание NInc_q:= NInc_q È {q}. Событие a_q - единственное событие с q Î NInc^(aq), которому не предшествует никакое другое событие a¢, удовлетворяющее условию q Î NInc^(a¢); таким образом, q Î NInc^(f) Þ a_q p f.

Из алгоритма следует, что для любого r Î In_q существует событие e Î C_r, предшествующее a_q. Отсюда следует результат.

Процесс p принимает решение только когда Inc_p = NInc_p; можно записать, что Inc^(dp) = NInc^(dp). В этом случае

(1) p Î Inc^(dp) ; и

(2) из q Î Inc^(dp) следует, что q Î NInc^(dp), откуда следует, что In_q Í Inc^(dp).

Из сильной связности сети следует требуемый результат: Inc^(dp) = P.

6.3 Алгоритмы обхода

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

Предыдущая567891011121314151617181920Следующая

Поделиться:

Воспользуйтесь поиском по сайту: