Реферат: Распределенные алгоритмы

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

       fatherp  :  P            init  udef ;

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

          begin  forall  q Î Neighp  do  send <tok>  to q ;

                      while  recp < # Neighp  do

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

                      decide

          end ;

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

          begin  receive <tok>  from neighbor q ;  fatherp := q ;  recp := recp + 1 ;

                      forall  q Î Neighp,  q ¹ fatherp  do  send <tok>  to q ;

                      while  recp < # Neighp  do

                                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, и, очевидно, fp p 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.2.4  Алгоритм опроса

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

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

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

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

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

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

          begin  forall  q Î Neighp  do  send <tok>  to q ;

                      while  recp < # Neighp  do

                                begin  receive <tok> ;  recp := recp + 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 содержатся в множестве 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 Î Outp  do  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] ³ Sentp  and  Sentp < D  then

                                      begin  forall  r Î Outp do  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).

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

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

Чтобы продемонстрировать, что в ¡ каждый процесс принял решение, покажем сначала, что каждый процесс хотя бы один раз послал сообщения. Т.к. в ¡ по каналам не передается ни одно сообщение, для каждого канала qp  Recp[q] = Sentpq. Также, т.к. каждый процесс посылает сообщения, как только получит сообщение сам, Recp[q] > 0 Þ Sentp > 0. Из предположения, что существует хотя бы один инициатор p0, для которого Sentp0 > 0, следует, что Sentp > 0 для каждого p.

Впоследствии  будет показано, что каждый процесс принял решение. Пусть p - процесс с минимальным значением переменной Sent в ¡, т.е. для всех q  Sentq ³ Sentp в ¡. В частности, это выполняется, если q - сосед по входу p, и из Recp[q] = Sentq следует, что  minq Recp[q] ³ Sentp. Но отсюда следует, что Sentp = D; иначе p послал бы дополнительные сообщения, когда он получил последнее сообщение. Следовательно, Sentp = D для всех p, и Recp[q] = D для всех qp, откуда действительно следует, что каждый процесс принял решение.

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

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

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

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

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

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

         Sentp      : 0..1           init  0 ;

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

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

              begin   forall  r Î Neighp  do  send <tok>  to r ;

                          Sentp := Sentp + 1 

              end ;

            while  Recp < # Neighp  do

                     begin  receive  <tok> ;

                                 Recp := Recp + 1 ;

                                 if  Sentp = 0  then

                                      begin  forall  r Î Neighp do  send <tok>  to r ;

                                                  Sentp := Sentp + 1

                                      end

                     end ;

            decide

end            

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

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

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

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

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

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

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

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

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

var    Incp       : set of processes         init  {p} ;

             NIncp   : set of processes         init  Æ ;

          recp[q] : boolean  for q Î Inp  init  false ;

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

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

                 forall  r Î Outp  do  send <sets, Incp, NIncp>  to r ;

            while  Incp ¹ NIncp  do

                     begin   receive <sets, Inc, NInc>  from q0 ;

                                 Incp := Incp È Inc ; NIncp := NIncp È NInc ;

                                 recp[q0] := true ;

                                 if  "q Î Inp : recp[q]  then  NIncp := NIncp È {p} ;

                                 if  Incp  или  NIncp  изменились  then

                                      forall  r Î Outp  do  send <sets, Incp, NIncp>  to r

                     end ;

            decide

end

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

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

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

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

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

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

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

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

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

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

(1) p Î Inc(dp) ; и

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

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

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

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

Определение 6.24  Алгоритмом обхода называется алгоритм, обладающий следующими тремя свойствами.

(1) В каждом вычислении один инициатор, который начинает выполнение алгоритма, посылая ровно одно сообщение.

(2) Процесс, получая сообщение, либо посылает одно сообщение дальше, либо принимает решение.

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

(3) Алгоритм завершается в инициаторе и к тому времени, когда это происходит, каждый процесс посылает сообщение хотя бы один раз.

В каждой достижимой конфигурации алгоритма обхода либо передается ровно одно сообщение, либо ровно один процесс получил сообщение и еще не послал ответное сообщение. С более абстрактной точки зрения, сообщения в вычислении, взятые вместе, можно рассматривать как единый объект (маркер), который передается от процесса к процессу и, таким образом, «посещает» все процессы. В Разделе 7.4 алгоритмы обхода используются для построения алгоритмов выбора и для этого важно знать не только общее количество переходов маркера в одной волне, но и сколько переходов необходимо для того, чтобы посетить первые x  процессов.

Определение 6.25  Алгоритм называется алгоритмом f-обхода (для класса сетей), если

(1) он является алгоритмом обхода (для этого класса); и

(2) в каждом вычислении после f(x) переходов маркера посещено не менее min (N, x+1) процессов.

Кольцевой алгоритм (Алгоритм 6.2) является алгоритмом обхода, и, поскольку x+1 процесс получил маркер после x шагов (для x < N), а все процессы получат его после N шагов, это алгоритм x-обхода для кольцевой сети.

6.3.1  Обход клик

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42