скачать рефераты
  RSS    

Меню

Быстрый поиск

скачать рефераты

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

Получение и отправка <tok> каждым процессом p ¹ p0 предшествует получению маркера процессом p0, следовательно, условие зависимости выполнено.

6.2.2  Древовидный алгоритм

В этом разделе представлен алгоритм для древовидной сети. Этот же алгоритм может быть использован для сетей произвольной топологии, если доступно остовное дерево сети. Предполагается, что алгоритм инициируют все листья дерева. Каждый процесс в алгоритме посылает ровно одно сообщение. Если процесс получил сообщение по всем инцидентным каналам, кроме одного (это условие изначально выполняется для листьев), процесс отправляет сообщение по оставшемуся каналу. Если процесс получил сообщения через все инцидентные каналы, он принимает решение; см. Алгоритм 6.3.

var recp[q]  for each q Î Neighp :    boolean     init false ;

       (* recp[q]  = true, если p получил сообщение от q *)

begin   while  # {q : recp[q]  is  false} > 1 do

                 begin  receive <tok> from q ;  recp[q] := true  end ;

            (* Теперь остался один q0, для которого recp[q0] = false *)

            send  <tok>  to q0  with recp[q0]  is false ;

       x : receive <tok>  from q0 ;  recp[q0] := true ;

            decide

            (* Сообщить другим процессам о решении:

                  forall  q Î Neighp, q ¹ q0  do send <tok>  to q *)

end

Алгоритм 6.3 Древовидный алгоритм.

Чтобы показать, что этот алгоритм является волновым, введем некоторые обозначения. Пусть fpq - событие, где p посылает сообщение q, а gpq - событие, где q получает сообщение от p. Через Tpq обозначим подмножество процессов, которые достижимы из p без прохождения по дуге pq (процессы на стороне p дуги pq); см. Рис.6.4.

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

Tpq =     и     P =

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

Оператор 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.

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

Предположим, что это выполняется для всех событий получения сообщений, предшествующих gpq. Из того, что событию gpq предшествует fpq (в процессе p), и из алгоритма p следует, что для всех r Î Neighp при r ¹ q, grp предшествует fpq. Из гипотезы индукции следует, что для всех таких r и для всех s Î Trp существует событие e Î Cs, где e p grp, следовательно, e p gpq.

Решению dp в p предшествуют grp для всех r Î Neighp, откуда следует, что " s Î P $ e Î Cs : e p dp.

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

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

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

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

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

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, что доказывается в следующей лемме.

Страницы: 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, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62


Новости

Быстрый поиск

Группа вКонтакте: новости

Пока нет

Новости в Twitter и Facebook

  скачать рефераты              скачать рефераты

Новости

скачать рефераты

© 2010.