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

8.3.3 Использование Подтверждений

Алгоритм Сафра подсчитывает основные сообщения, которые посланы и получены, чтобы знать есть ли основные сообщения, находящиесы в процессе передачи. Также возможно гарантировать это используя подтверждения; несколько авторов предложили такое усовершенствование алгоритма Dijkstra-Feijen-Van Gasteren, см., например, Naimi [Nai88]. Это разновидность принципа обсуждается лишь кратко, потому что результирующий алгоритм не во всех смыслах является  усовершенствованием алгоритма Shavit-Francez, и поэтому устарел.

Сначала, заметим, что никакое сообщение не находится в процессе передачи  эквивалентено для всех p никакое сообщение, посланное p не находится в процессе передачи. Каждый процесс ответственен за сообщения, которые он послало, то есть, он должен позабититься о том, чтобы алгоритм объявления не был вызван, пока не будет уверенности в том, что все основные сообщения, посланные им получены. Метод обнаружения определяет для каждого процесса p локальное условие quiet(p) таким образом, что

quiet(p) Þ (statep = passive Ù никакие основный сообщения, посланные процессом р не находятся в процессе передачи)

удовлетворен. Тогда ("p : quiet(p)) Þ term.

Чтобы устанавить, что никакое сообщение, посланное p не находится в процессе передачи, каждое сообщение подтверждается, и каждый процесс поддерживает счетчик числа подтверждений, которые он должен еще получить. Формально, утверждение Pa определяется как

Pa = " p : (unackp =   # (передается сообщение,посланное p) + # (передается подтверждение для p))

и поддерживается инвариант в соответствии с следующим правилом.

var statep   : (active, passive) ;

      colorp   : (white, black) ;

      unackp : integer      init 0 ;

Sp: { statep = active }

      begin send (mes) ; unackp:= unackp + 1 :   (* Правило A *)

                colorp := black  (*Правило B *)

      end

Rp: { сообщение ( mes ) из q прибыло в p }

     begin receive (mes) ; statep := active ;

               send (ack) to q (*Правило A*)

     end

Ip: { statep = active }

     begin statep := passive end

Ap: { подтверждение (ack) прибыло в p }

      begin receive (ack) ; unackp := unackp – 1  end   (* Rule A *)

Начало определения, исполняется один раз процессом p0:

      begin send ( tok, white ) to pN -1 end

Tp: (* Процесс p обрабатывает маркер (tok,c) *)

      { statep = passive Ù unackp = 0 }

       begin if p = p0

                      then if c = white Ù colorp = white

                                 then Announce

                                 else send (tok, white ) to pN -1

                      else if (colorp = white)

                                then send ( tok, c ) to Nextp

                                else send ( tok, black ) to Nextp ;

              colorp := white  (*Правило B *)

      end

Алгоритм 8.8 обнаружения завершения, использующие подтверждения.

Правило A. При посылке сообщения, p увеличивает unackp, при получение сообщения от q, p посылает подтверждение q ; при получении подтверждения, p уменьшает на 1 unackp.

Требования для quiet (а именно, что из quiet(p) следует, что p пассивен и никакое основное сообщение, посланное p не находится  в процессе передачи) будут удовлетворены, если quiet определить как

quiet(p) º (statep= passive Ù unackp = 0).

Начало алгоритма обнаружения похоже на начало алгоритма Dijkstra-Feijea-Van Gasteren. Начинаем с рассмотрения утверждение P0 ,определенного как

P0   º   " i (N > i> t) : quiet(p).

Представление P1 нужно выбирать осторожно, потому что активация процесса pj с j> t процессом pi с i £ t не имеет место в том же самом событии,что и  посылка сообщения процессом pi. Это имеет место, однако, что, когда pj активизирован (таким образом, что P0 ложь ), unackPi > 0. Следовательно, если утверждение Pb  определенное как

Pb   º " p  : (unackp > 0 Þ colorp = black),

Поддерживается  наблюдением

Правило B. Когда процесс посылает сообщение, он становится черным; процесс становится белым только, когда он quiet.

Заключение снова подтветждает, что когда P0 обращается в ложь, P1 сохраняется, следовательно (P0 Ú P1) не обращается в ложь.

Результируещий алгоритм дается как Алгоритм 8.8, и инварианта - Pa Ú Pb Ú (P0 Ù P1 ÙP2 ) , где

Pa  º" p : (unackp =:  #(передается сообщение посланное p)

                                 + #(передается подтверждение для p))

Pb   º" p : (unackp > 0 Þ colorp = black)

P0   º" i (N > i> t) : quiet(p)

P1   º$  i (t ³ i ³ O): colorPi , = black

P2  º   маркер черный.

Теорема 8.10 Алгоритма 8.8 - правильный алгоритм обнаружения завершения для вычислений с асинхронным прохождением сообщений.

Доказательство. Завершение объявляется, когда p0 quiet и обрабатывает белый маркер. Из этих условий следует, что ØP2 и ØP1, а следовательно Pa Ù Pb ÙP0  сохраняются. Вместе с quiet(p0) (p0) это означает, что все процессы quiet, следовательно сохраняется term.

Когда основное вычисление заканчивается, через некоторое время получены все подтверждения, и все процессы становятся quiet. Когда заканчивается первая волна, которая начинается, когда все процессы quiet, все процессыокрашены в белый цвет, и завершение объявляется в конце следующей волны. o

Решение, основанное на ограниченной задержке сообщений. В [Tel91b, Раздел 4.1,3] классе решений обнаружения завершения (и других проблем) описывается решение основанное на предположении, что задержка сообщений ограничена

постоянной m. (См. также Раздел 3.2). В этих решениях, процесс не является quiet промежуток времяни m после отправления последнего сообщения, также процесс остается черным, пока он не quiet, как описано в решении основанном на использовании подтверждений. Процесс p становится quiet если (1) прошло по крайней мере m времяни после того как прцесс p посылал последний раз сообщения и р пассивен. Полный формальный вывод алгоритма предоствлен читателю.

8.3.4 Обнаружение завершения с помощью волн

Все алгоритмы обнаружения завершения, обсужденные пока в этом разделе используют кольцевую подтопологию для управляющих коммуникаций; все алгоритмы основаны на алгоритме волны для колец. Подобные решения были предложены для другой топологии; например, Francez и Rodeh [FR82] и Topor [Top84] предложили алгоритм, использующий корневое дерево охватов управляющих соммуникаций. Tan и Van Leeuwen [TL86] предложили децентрализованные решения к кольцевым сетям, для сетей деревьев, и для произвольных сетей. Изучение этих решений показывает, что они очень похожи друг на друга, за исклющением алгоритма волны, на который они опираются.

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

Этот подраздел представляет вывод только для случая синхронного прохождения сообщений основного вычисления (как для вывода в Подразделе 8.3.1). Этот вывод можно обобщить для асинхронного случая, подобно тому как это сделано в Подразделе 8.3.2 и 8.3.3.

Инвариант алгоритма должен позволить обнаружить завершение, когда волна принимает решение; поэтому, сначала мы устанавливаем P = P0, где

P0 º  все посещенные процессы пассивны.

Действительно, поскольку все процессы были посещены, когда произошло принятие решения, это утверждение позволяет обнаружение завершения, когда волна принимает решение. Кроме того, P0 устанавливается когда волна начинается (нет еще посещенных процессов). При работе алгоритма волны P0 сохраняется по правилу 1, представленному ниже.

Правило 1. Только пассивные процессы посещаются волной. К сожалению, P0 принимает значение ложь, когда посещенный процесс активизируется непосещенным процессом. Поэтому, каждый процесс обеспечивается цветом, и P ослаблляется до (P0 Ú P1), где

P1 º  имеется непосещенный черный процесс.

Более слабый инвариант сохраняется согласно правилу 2.

Правило 2. Процесс посылающий сообщение становится черным.

Волна может изменить значение более слабого утверждение, если посещен единственный непосещенной черный процесс. Ситуация исправляется дальнейшим ослаблением P. Каждый процесс представляет цвет, белый или черный, как входное данное для волну. Волна измененяется так, чтобы вычислить самый темный из представленных цветов; вспомним, что волны могут вычислять infirna, и " самый темный " является infirnum. Когда волна принимает решение, будет вычислен самый темный из всех представленных цветов; это будет белый цвет, если все процессы представляют белый и черный, если по крайней мере один процесс представляет черный. В время волны, волна будет называться белой, если ни один  процесс еще не представляет черный цвет; и черной, если по крайней мере один процесс уже представляет черный цвет. Таким образом процесс, когда он посещается, либо представляет белый цвет, что не изменяет цвет волны,  либо представляет черный цвет,что окрашивает волну в черный цвет. P ослабляется до (P0 Ú P1 Ú P2), где

P2  º   волна черная.

 Это утверждение сохраняется по следующему правилу.

Правило 3. Посещенный процесс представляет волне свой текущий цвет.

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

Правило 4. Решающий узел в черной волне начинает новую волну.

Правило 5. Процессы немедленно становятся белыми после каждого посещения волны.

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

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

8.4 Другие Решения

Еще два решения проблемы обнаружения завершения будут обсуждены в этом разделе: алгоритм восстановления кредита и алгоритм временных пометок.

8.4.1 Алгоритм восстановления кредита

Mattern [Mat89a] предложил алгоритм, который обнаруживает завершение очень быстро, а именно, за одну единицу времени после возникновения (при принятии предположений идеализации времени из Определения 6.31). Алгоритм обнаруживает завершение централизованного вычисления и предполагает, что каждый процесс может послать сообщение инициатору вычисления непосредственно (то есть, сеть содержит звезду с инициатором в центре).

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

S1. Сумма всех кредитов (в сообщениях и процессах) равняется 1.

S2. Основное сообщение имеет положительный кредит.

S3. Активный процесс имеет положительный кредит.

Процессы имеют положительный кредит, когда правилами не предписано (то есть, пассивным процессам) посылать их кредиты инициатору. Инициатор действует как банк, собирая все кредиты, посланные ему, в переменной ret .

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

Правило 1. Когда ret = 1, инициатор вызывает алгоритм объявления.

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

var statep   : (active, passive) init if p = p0 then active else passive ;

      credp   : fraction               init if p = p0 then I else 0 ;

      ret       : fraction               init 0 ;   for p0 only

Sp: { statep = active }   (* Праволо 3 *)

     begin send (mes,credp / 2) : credp := credp / 2 end

Rp: { Сообщение (mes,c) прибыло в p }

      begin receive (mes,c) ; statep := active;

               credp := credp + c  (* Правила 4 and 5b *)

      end

Ip:   { statep = active }

       begin statep := passive ;

                 send ( ret, credp ) to p0 ; credp :== 0  (* Правило 2 *)

      end

AP0: { Сообщение (ret, c) прибыло в p0 }

        begin receive ( ret, c ) ; ret := ret + c ;

                  if ret = 1 then Announce (* Правило I *)

       end

Алгоритм 8.9 Алгоритм восстановления кредита.

Правило 2. Когда процесс становится пассивным, он посылает свой кредит инициатору.

В начальной конфигурации только инициатор активен и имеет положительный кредит, а именно 1, и ret = 0, что означает, что S1- S3 удовлетворz.ncz. Инвариант должен поддержаться в течение вычисления; об этом заботятся следующие правила. Сначала, каждому основному сообщению при посылке нужно дать положительный кредит; к счастью, отправитель активен, и следовательно имеет положительный кредит.

Правило 3. Когда активный процесс p посылает сообщение, кредит разделяется между p и сообщением.

Процессу при его активизации нужно дать положительный кредит; к счастью, сообщение, которое он получает при этом, содержит положительный кредит.

Правило 4. При активизации процесса ему дается кредит активизирующего сообщения.

Единственная ситуация, не охваченная этими правилами - получение основного сообщения уже активным процессом. Процесс уже имеет положительный кредит, следовательно не нуждается в кредите сообщения, чтобы удовлетворить S3; однако, кредит не может быть разрушен, поскольку это привело бы вело бы к нарушению S1 . Процесс получающий сообщение может обращаться с кредитом двумя различными способами, оба порождают правильные алгоритмы.

Правило 5a. Когда активный процесс получает основное сообщение, кредит этого

сообщения посылается инициатору.

Правило 5b. Когда активный процесс получает основное сообщение, кредит того сообщения добавляется к кредиту процесса.

Алгоритм дается как Алгоритм 8.9. В этом алгоритме, принимается, что каждый процесс знает имя инициатора (по крайней мере, когда он сначала становится пассивным) и алгоритм использует правило 5b. Когда инициатор становится пассивным, он посылает сообщение самому себе.

Теорема 8.11 Алгоритм восстановления кредита (Алгоритм 8.9) - правильный алгоритм обнаружения завершения.

Доказательство. Алгоритм осуществляет правила 1-5, из чего следует, что S1 Ù S2 Ù S3 инвариант, где

S1 º 1 = ( S(mes, c) c )+ (SpÎP credp )+ ( S(ret, c) c )+ret

Страницы: 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