Реферат: Распределенные алгоритмы
и поддерживается инвариант в соответствии с следующим правилом.
var statep : (active, passive) ;
begin send (mes) ; unackp:= unackp + 1 : (* Правило A *)
colorp := black (*Правило B *)
end
Rp: { сообщение ( mes ) из q прибыло в p }
begin receive (mes) ; statep := active ;
end
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 }
then if c = white Ù colorp = white
then Announce
else send (tok, white ) to pN -1
else if (colorp = white)
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)
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.1 Алгоритм восстановления кредита
Mattern [Mat89a] предложил алгоритм, который обнаруживает завершение очень быстро, а именно, за одну единицу времени после возникновения (при принятии предположений идеализации времени из Определения 6.31). Алгоритм обнаруживает завершение централизованного вычисления и предполагает, что каждый процесс может послать сообщение инициатору вычисления непосредственно (то есть, сеть содержит звезду с инициатором в центре).
В алгоритме каждому сообщению и каждому процессу назначается значение кредита, которое всегда находится между 0 и 1 (включая границы), и алгоритм поддерживает следующие утверждения как инварианты.
S1. Сумма всех кредитов (в сообщениях и процессах) равняется 1.
S2. Основное сообщение имеет положительный кредит.
S3. Активный процесс имеет положительный кредит.
Процессы имеют положительный кредит, когда правилами не предписано (то есть, пассивным процессам) посылать их кредиты инициатору. Инициатор действует как банк, собирая все кредиты, посланные ему, в переменной ret .
Когда инициатор имеет все кредиты, требование для активных процессов и основных сообщений иметь положительный кредит означает, что не имеется никаких таких процессов и никаких таких сообщений; следовательно term сохраняется.
Правило 1. Когда ret = 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, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62
