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

случаях, где F1 ждет F2, верно одно из следующих утверждений.

(1) level 1 > level2 ,

(2) level1 = level2 ( ((eF1( > ((eF2(;

(3) level1 = level2 ( ((eF1( = ((eF2( и F2 все еще ищет исходящее ребро с

наименьшим весом. (Т.к. eF1 - исходящее ребро F2, не возможно чтобы w

(eF2) > w (eF1).)

Таким образом никакой тупиковый цикл не может возникнуть.

Каждое ребро отклоняется не более одного раза, и это требует двух

сообщений, который ограничивает число сообщений reject и сообщений test

как следствий отклонений к 2(E(. На любом уровне, узел получает не более

одного сообщения initiate и accept , и посылает не более одного сообщения

report, и одно changeroot или connect сообщение, и одно test сообщение, не

ведущее к отклонению. На нулевом уровнени одно сообщение accept не

получается и не одно сообщение report или test не посылается. На высшем

уровне каждый узел только посылает сообщение report и получает одно

сообщение initiate. Общее количество сообщений поэтому ограничено 2(E( + 5N

log N. (

7.3.5 Обсуждения и Варианты GHS Алгоритма

Gallager-Humblet-Spira алгоритм - один из наиболее сложных волновых

алгоритмов, требует только локальное знание и имеет оптимальную сложность

по сообщениям. Алгоритм может легко быть расширен так, чтобы он выбрал

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

двух узлах, а именно основных узлах последнего фрагмента (охватывающего

полную сеть). Вместо выполнения остановки, основные узлы обменивают их

идентификаторами, и меньший из них становится лидером.

Было опубликовано множество разновидностей и родственных алгоритмов. GHS

алгоритм может требовать время ?(N2), если некоторые узлы начинают алгоритм

очень поздно. Если используется дополнительная процедура пробуждения

(требующая не более (E( сообщений) сложность алгоритма по времени 5N log N;

см. Упражнение 7.11. Awerbuch [Awe87] показал, что сложность алгоритма по

времени может быть улучшена од 0 (N), при сохранение оптимального порядка

сложности по сообщениям ,то есть 0 ((E( + N log N).

Afek и другие [ALSY90] приспособили алгоритм, для вычисления леса охвата с

благоприятными свойствами, а именно, что диаметр каждого дерева и

количество деревьев - 0 (N1/2). Их алгоритм распределенно вычисляет

кластеризацию сети как показано в Lemma 4.47 и дерево охвата и центр

каждого кластера.

Читатель может спрасить, могут ли произвольные деревя охватов быть

построены более эффективно чем минимальные деревя охватов, но Теорема

7.15 также дает низкую границу ?(NlogN +(E() на построение произвольных

деревьев охватов. Johansen и другие [JJN ^ 87] дают алгоритм для вычисления

произвольного дерева охватов, который использует3N log N + 2(E( +0(N)

сообщений, таким образом улучшая GHS алгоритме на постоянный множитель,

если сеть редка. Barllan и Zernik [BIZ89] представили алгоритм, который

вычисляет случайные деревья охватов, где каждое возможное дерево охватов

выбрано с равной вероятностью. Алгоритм - рандомизирован и использует

ожидаемое число сообщений, которое находится в границах между 0 (NlogN

+(E()) и 0 (N3), в зависимости от топологии сети.

В то время как строительство произвольных и минимальных деревьев охватов

имеет равную сложность в произвольных сетях, это не так в кликах. Korach,

Moran и Zaks [KMZ85] показали, что строительство минимального дерева

охватов в взвешенной клике требует обмена ?(N2) сообщениями. Этот

результат указывает, что знание топологии не помогает уменьшать сложность

обнаружения MST ниже границы из Теоремы 7.15. Произвольное дерево охватов

клики может быть построено в 0 (N log N) сообщения, как мы покажем в

следующем разделе; см. также [KMZ84].

7.4 Алгоритм Korach-Kutten-Moran

Много результатов были получены для проблемы выбора, не только для случая

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

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

лучшие известные алгоритмы имеют сложность по сообщениям 0(N log N) и в

некоторых случаях этот результат достигает ?(NlogN). Korach, Kutten, и

Moran [KKM90] показали, что имеется тесная связь между сетеми выбора и

обхода. Их главный результат - общее строительство эффективного алгоритма

выбора для класса сетей, учитывая алгоритм обхода для этого класса. Они

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

известным для класса сетей, результирующий алгоритм благоприятно сравним с

лучшим алгоритмом выбора, известным для того класса в большинстве случаев.

Дело обстоит не так для сложности по времени; Сложность времени алгоритма

равняется сложности по сообщениям, и в некоторых случаях известны другие

алгоритмы с той же самой сложностью по сообщениям и более низкой сложностью

времени.

7.4.1 Модульное Строительство

Korach-Kutten-Moran алгоритм использует идеи преобразования вырождения

(Подраздел 7.3.1) и идеи Peterson/Dolev-Klawe-Rodeh алгоритма (Подраздел

7.2.2). Подобно преобразованию вырождения инициаторы выбора начинают обход

сети с маркера, помеченного их идентификатором. Если обход заканчивается

(разрешается), инициатор обхода становится избранным; алгоритм

подразумевает, что это случается для точно одного обхода. В этом подразделе

алгоритм описан для случая, где каналы удовлетворяют fifo предположение,

но, поддерживая немного больше информации в каждом маркере и в каждом

процессе алгоритм, может быть приспособлен к не - fifo случай; см. [KKM90].

Чтобы иметь дело с ситуацией больше чем одного инициатора, алгоритм

работает на уровнях, которые могут быть сравнены с раундами Peterson/Dolev-

Klawe-Rodeh алгоритма. Если по крайней мере два обхода начаты, маркеры

достигнут процесса, который уже был посещен другим маркером. Если эта

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

теперь становится, чтобы свести вместе два маркера в одном процессе, где

они будут убиты и новый обход будет начат. Сравните это с Peterson/Dolev и

другими алгоритмами, где по крайней мере один из каждых двух

идентификаторов проходит круг и продолжает проходить следующий. Понятие

раундов заменено в Korach-Kutten-Moran алгоритме понятием уровней; два

маркера вызовут новый обход только если они имеют один и тот же уровень, и

вновь произведенный маркер имеет уровень на единицу больше. Если маркер

встречается с маркером более высокого уровня, или достигает узла, уже

посещенного маркером более высокого уровня, прибывающий маркер просто убит

без того, чтобы влиять на маркер на более высоком уровне.

Алгоритм дается как Алгоритм 7.13. Чтобы свести вместе маркеры одного и

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

режимов: annexing, chasing, или waiting. Маркер представляется (q, l), где

q - инициатор маркера и l - уровень. Переменная levp дает уровень процесса

p, и переменная catp дает инициатора последнего маркера annexing ,

отправленного p (в настоящее время активный обход p). Переменная waitp -

udef, если никакой маркер не ожидает в p, и его значение q, если маркер

(q, levp) ожидает в p. Переменная lastp используется для маркеров в режиме

chasing: она дает соседа, которому p отправил маркер annexing уровня levp,

если маркер chasing не был послан сразу после этого; в этом случае lastp =

udef. Алгоритм взаимодействует с алгоритмом обхода запросом к функции trav:

эта функция возвращает соседа, которому маркер должен быть отправлен или

decide, если обход заканчивается.

Маркер (q, l) вводится в режиме annexing и в этом режиме он начинает

исполнять алгоритм обхода (в случае IV Алгоритма 7.13) пока не произойдет

одна из следующих ситуаций.

(1) Алгоритм обхода заканчивается: q становится лидером в этом случае (см.

Случай IV в Алгоритме 7.13).

(2) Маркер достигает узла p уровня levp > l: маркер убит в этом случае,

(Этот случай неявен в Алгоритме 7.13; все условия в том алгоритме требуют

l> levp или l = levp.)

(3) Маркер прибывает в узел, где ожидает маркер уровня l: два маркера убиты

в этом случае, и новый обход начинается с того узла (см. Случай II в

Алгоритме 7.13).

(4) Маркер достигает узла с уровнем l, который был наиболее недавно посещен

маркером с идентификатором catp > q (см. Случай VI) или маркером chasing

(см. Случай III): маркер ожидает в том узле.

(5) Маркер достигает узла уровня l, который был наиболее недавно посещен

маркером annexing с идентификатором catp < q: маркер становится маркером

chasing в этом случае и посылается через тот же самый канал что и

предыдущий маркер (см. Случай V).

Маркер chasing (g, l) отправляется в каждом узле через канал, через который

наиболее недавно переданный маркер был послан, пока одна из следующих

ситуаций не происходит.

(1) Маркер прибывает в процесс уровня levp > l: маркер убит в этом случае.

(2) Маркер прибывает в процесс с маркером waiting уровня l: два маркера

удалены, и новый обход начат этим процессом (см. Случай II ).

(3) Маркер достигает процесса уровня l, где наиболее недавно передан маркер

chasing: маркер становится waiting (см. Случай III).

Маркер waiting находится в процессе, пока одна из следующих ситуаций не

происходит.

(1) Маркер более высокого уровня достигает того же самого процесса: маркер

waiting убит (см. Случай 1).

(2) Маркер равного уровня прибывает: два маркера удалены, и обход более

высокого уровня начат (см. Случай II).

В Алгоритме 7.13 переменные и информация маркеров, используемая алгоритмом

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

levp, это маркер annexing, инициатор которого не p . Если обход

заканчивается в p, p становится лидером и отправляет сообщение всем

процессам, заставляя их закончиться.

Правильность и сложность. Для того чтобы продемонстрировать правильность

Korach-Kutten-Moran алгоритма, покажем, что число маркеров, произведенных

на каждом уровне уменьшается до одного, на некотором уровне чей инициатор

будет избран.

Lemma 7.22 Если произведены k> 1 маркеров на уровне l, по крайней мере один

и не более k/2 маркеров произведены на уровне l + 1.

var levp : integer init – 1;

catp , waitp : P init udef',

lastp : Neighp init udef:

begin if p is initiator then

begin levp := levp + 1 ; lastp := trav(p. levp) ;

catp := p ; send (annex, p, levp ) to lastp

end ;

while . . . (* Условие завершения, смотри текст *) do

begin receive token (q,l) ;

if token is annexing then t := A else t := C ;

if l > levp then (* Case I *)

begin levp := l ; catp := q ;

waitp := udef ; lastp := trav(q, l)

;

send ( annex, q, l ) to lastp

end

else if l == levp and waitp (udef then (* жпюжюмеэЎжЖьшзчь¶йvьMкzъµыHЁb'Е

Е,n"0бЫ0М/A,~-8(Фo$‰І"Є-.$ —'H P*Йг*Ю‡)ґ)&[pic] Ъы%`рЛ

Эз«[7]ХгнъдчRжсц/имщgй мЄ ~р3ВхШ rъУ*Правило 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, все процессыокрашены в

белый цвет, и завершение объявляется в конце следующей волны. (

Решение, основанное на ограниченной задержке сообщений. В [Tel91b, Раздел

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

решение основанное на предположении, что задержка сообщений ограничена

постоянной (. (См. также Раздел 3.2). В этих решениях, процесс не является

quiet промежуток времяни ( после отправления последнего сообщения, также

процесс остается черным, пока он не quiet, как описано в решении основанном

на использовании подтверждений. Процесс p становится quiet если (1) прошло

по крайней мере ( времяни после того как прцесс 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. Посещенный процесс представляет волне свой текущий цвет.

Действительно, все основные коммуникации также как деятельность волны

сохраняют это утверждение, которое является поэтому инвариантом. Волна

заканчивается неудачно, если процессы принимают решение для черной волны,

но в этом случае просто начинается новая волна. Новая волна может быть

успешной, только если процессы могут стать белыми, и это случается

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