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

фрагментов.

Вычисление GHS алгоритма происходит согласно следующим шагам.

(1) Множество фрагментов поддерживается таким, что объединение всех

фрагментов содержит все вершины.

(2) Первоначально это множество содержит каждый узел как фрагмент из одного

узла.

(3) Узлы во фрагменте сотрудничают, чтобы найти исходящее ребро фрагмента с

минимальным весом .

(4) Когда исходящее ребро фрагмента с наименьшим весом известно, фрагмент

объединяется с другим фрагментом добавлением исходящего ребра, вместе с

другим фрагментом.

(5) Алгоритм заканчивается, когда остается только один фрагмент.

Эффективное выполнение этих шагов требует представления некоторого

примечания и механизмов.

(1) Имя фрагмента. Чтобы определить исходящее ребро с наименьшим весом ,

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

фрагменте. Для этого каждый фрагмент будет иметь имя, которое будет

известно процессам в этом фрагменте. Процесс проверяет является ли ребро

внутренним или исходящим сравненивая имена фрагментов.

(2) Объединение больших и маленьких фрагментов. Когда объединяются два

фрагмента, имя фрагмента изменяется по крайней мере в одном из фрагментов,

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

двух фрагментов. Чтобы это изменение было эффективным, стратегия

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

объединяется в больший из двух, принимая имя фрагмента большего фрагмента.

(3) Уровни фрагментов. Небольшое размышление показывает, что решение, кто

из двух фрагментов является большим, не должно зависить от числа узлов в

двух фрагментах. Для этого необходимо изменять размер фрагмента в каждом

процессе, и большего и меньшего фрагментов, таким образом портя

желательную свойство, что изменение необходимо только в меньшем. Вместо

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

начального фрагмента с одним узлам. Это позволяется, что фрагмент F1

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

фрагмент F1 ( F2 имеет уровень F2. Новый фрагмент также имеет имя

фрагмента F2, так что никакие изменения не для узлов в F2 не требуются.

Такое объединение также возможно для двух фрагментов одинакового уровня; в

этом случае новый фрагмент имеет новое имя, и уровень - на единицу выше чем

уровень объединяющихся фрагментов. Новое имя фрагмента - вес ребра,

которым объединены два фрагмента, и этот ребро называется основным ребром

нового фрагмента. Два узла, связанные основным ребром называются основными

узлами.

Lemma 7.20. Если эти правила объединения выполняются, процесс изменяет имя

фрагмента, или уровень не более N log N раз.

Доказательство. Уровень процесса никогда не уменьшается, и только, когда он

увеличивается процесс изменяет имя)фрагмента. Фрагмент уровня L содержит по

крайней мере 2L процессов, так что максимальный уровень - logN, что

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

не более чем log N раз. Следовательно, полное общее число изменений имени

фрагмента и уровня ограничено величиной N log N. (

Резюме стратегии объединения. Фрагмент F с именем FN и уровнем L обозначаем

как F = (FN, L); пусть eF обозначает исходящее ребро с наименьшим весом F.

Правило A. Если eF ведет к фрагменту F ' = (FN ', L ') с L < L ', F

объединяется в F ', после чего новый фрагмент имеет имя FN ' и уровень L '.

Эти новые значения посылаются всем процессам в F.

Правило B. Если eF ведет к фрагменту F ' = (FN ', L ') с L = L ' и eF ' =

eF, два фрагмента объединяются в новый фрагмент с уровнем L + 1 и называют

w (ep). Эти новые значения послаются всем процессам в F и F '.

Правило C. Во всех других случаях (то есть, L > L ' или L = L ' и eF ' ( e

F ) фрагмент F, должен ждать, пока применится правило А или B .

var statep : (sleep, find, found);

stachp [q] : ( basic, branch, reject) for each

q ( Neighp ;

namep, bestwtp : real ;

levelp : integer;

testchp, bestchp, fatherp : Neighp;

recp : integer;

ПCчѕР…уaНЦн^З?йнВ¦кжА‚рґАGяХjф

dе?”ШэуПшЕЛ—хКак первое действие каждого процесса, алгоритм должен быть

инициализирован:

begin пусть pq канал процесса p с наименьшим весом ;

stachp [q] := branch ; levelp := 0 ;

statep := found ; recp := 0 ;

send ( connect, 0 ( to q

end

При получении ( connect, L ( от q:

begin if L < levelp then (* Объединение по правилу А *)

begin stachp[q] := branch;

send ( initiate, levelp ,namep ,statep ( to q

end

else if stachp[q] = basic

then (* Правило C *) обработать сообщение позже

else (* Правило B *) send ( initiate, levelp +1

,((pq) ,find ( to q

end

При получении (initiate, L,F,S( от q:

begin level p := L ; name p := F ; state p := S , father p :== q ;

bestch p := udef ; bestwt p :.= ( ;

forall r ( Neigh p : stach p [r] = branch ( r ( q do

send ( initiate, L, F, S( to r ;

if state p = find then begin rec p := 0 ; test end

end

Алгоритм 7.10 gallager-humblet-spira алгоритм (часть 1).

7.3.4 Детальное описания GHS алгоритма

Узел и статус связи. Узел p обслуживает переменные как показано в Алгоритме

7.10, включая статус канала stach p [q] для каждого канала pq. Этот статус

- branch, если ребра, как известно, принадлежит MST, reject, если

известно, что оно не принадлежит MST, и basic, если ребро еще не

использовалось. Связь во фрагменте для определения исходящего ребра с

наименьшим весом происходит через ребра branch во фрагменте. Для процесса

p во фрагменте, отецом является ребро ведущее к основному ребру фрагмента.

Cостояние узла p, state p, - find, еcли p в настоящее время участвует в

поиске исходящего ребра фрагмента с наименьшим весом и found в противном

случае. Алгоритм дается как алгоритмы 7.10/7.11/7.12 . Иногда обработка

сообщения должна быть отсрочена, пока локальное условие не удовлетворено.

(4) procedure test:

begin if (q ( e Neigh p : stach p [q] = basic then

begin testch p := q with stach p [q] = basic and ((pq) minimal;

send (test, level p , name p ( to testch p

end

else begin testch p := udef ; report end

end

(5)Т—э;Х~шCЯ[pic]ц

л•уYхUсиь6рЎяЁп |я}сья щ?R@Ґ

?Ёx[pic]?#ь?

щк[3]mшoэ*шfш>ч–фІчZущщЪф=эчч-[pic] ьeяN¬ё |m[4]W

‚я1 у? |%‡«-яY

wыў

TыZ

Рю?»[5]/мO8 |:ґ'.їуЄ

l) |?3[pic]^ўь± |Јчч Dт

tоP

‚оУрАр±плL­иЈи Шз©еЎ VаУяЬ·чRЫЕфkЭцbаэшПри получении ( test, L, F ( от q:

begin if L > level p then (* Отвечающий должен подождать! *)

обработать сообщение позже

else if F = name p then (* внутреннее ребро *)

begin if stach p [q] = basic then stach p [q] := reject ;

if q ( testch p

then send ( reject ( to q

else test

end else send ( accept ( to q

end

(6) При получении ( accept( от q:

begin testch p := udef ;

if ((pq) < bestwt p

then begin bestwt p := ((pq) ; bestch p := q end ;

report

end

(7) Пр получении ( reject ( от q:

begin if stach p [q] = basic then stach p [q] := reject ;

test

end

Алгоритм 7.11 the gallager-humblet-spira алгоритм (часть 2).

Принимается, что в этом случае сообщение сохраняется, и позже

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

что. Если процесс получает сообщение, в то время как он все еще в

состоянии sleep, алгоритм инициализируется в том узле (выполняя действие

(1)) прежде, чем сообщение обработано.

Нахождение исходящго ребра с наименьшим весом. Узлы во фрагменте

сотрудничают, чтобы найти исходящее ребро фрагмента с наименьшим весом, и

когда ребро найдено через него посылается сообщение ( connect, L ( ; L -

уровень фрагмента. Если фрагмент состоит из единственного узла, как имеет

место после инициализации этого узла, требуемое ребро - просто ребро с

наименьшим весом смежное с этим узлом.Смотри (1). Сообщение A ( connect, 0

( посылается через это ребро.

(8) procedure report:

begin if rec p = #{q : stach p [q] = branch ( q ( father p }

and testch p = udef then

begin state p := found ; send ( report, bestwt p ) to father p end

end

(9) При получении ( report, ( ( от g:

begin if q( father p

then (* reply for initiate message *)

begin if ( < bestwt p then

begin bestwt p := ( ; bestch p := q end ;

rec p := rec p + 1 ; report

end

else (* pq является основным ребром *)

if state p = find

then обработать это сообщение позже

else if ( > bestwt p then changeroot

else if ( = bestwt p = ( then stop

end

(10) procedure changeroot;

begin if stach p [bestch p] = branch

then send ( changeroot ( to bestch p

else begin send ( connect, level p ( to bestch p ;

stach p [bestch p] := branch

end

end

(11) ¦[6]цьGqЎ |† Ьw

¬ ‘му8лл„^f“в?X2«э?коa)При получении (changeroot(:

begin changeroot end

Алгоритм 7.12 gallager-humblet-spira алгоритм (часть 3).

Затем рассмотрите случай, когда новый фрагмент сформирован, объединяя два

фрагмента, соединяя их ребром e = pq. Если два объединенных фрагмента имели

одинаковый уровень, L, p и q пошлют сообщение ( connect, 1( через e, и

получат в ответ сообщение ( connect, L( , в то время как статус e - branch,

см. действие (2). Ребро pq становится основным ребром фрагмента, p и q

обменивают сообщением (initiate, L + 1, N, S (, присваивая новый уровень и

имя фрагменту. Имя - w (pq), и статус find приводит к тому, что каждый

процесс начинает искать исходящее ребро с наименьшим весом; см. действие

(3). Сообщение ( initiate, L + 1, N, S( посылается каждому узлу в новом

фрагменте. Если уровень p был меньше чем уровень q, p пошлет сообщение (

connect, L ( через e, и получит сообщение (initiate, L' , N, S ( в ответ от

q; см. действие (2). В этом случае, L ' и N - текущий уровень и имя

фрагмента q, а имя и уровень узлов на стороне q ребра не изменяется. На

стороне p ребра сообщение инициализации отправляется к всем узлам (см.

действие (3)), заставляя каждый процесс изменять имя фрагмента и уровень.

Если q в настоящее время ищет исходящее ребро с наименьшим весом (S = find)

процессы во фрагменте p присоединяются к поиску с помощью вызова test.

Каждый процесс во фрагменте осуществляет поиск по все его ребрам (если

такие существуют, см. (4), (5), (6), и (7)) для того, что определить

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

наименьшее по весу. Исходящее ребро с наименьшим весом сообщается всем

поддеревьям, с помощью сообщения (report, ((; см. (8). Узел p подсчитывает

число сообщений (report, ((, которые получает, используя переменную recp,

которой присваивается значение 0 при начале поиска (см. (3)) и

увеличивается на единицу при получении сообщения (report, ((; см. (9).

Каждый процесс посылает сообщение (report, (( отцу, когда он получает такое

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

исходящего ребра.

Сообщения (report, (( посылаются по направлению к основному ребру каждым

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

получают сообщение от их отца; см. (9). Каждый основной узел ждет, пока он

не пошлет сообщение (report, (( сам пока он обрабатывает сообщение другого

процесса. Когда два сообщения (report, (( основных узлов пересеклись,

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

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

сообщения передают значения ().

Если исходящее ребро было передано, лучшее ребро находится следуя

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

которой было передано лучшее ребро. Сообщение ( connect, L ( должно быть

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

этом направлении; это выполняется с помощью посылки сообщения ( changeroot

(. Основной узел, на чьей стороне расположено исходящее ребро с наименьшим

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

исходящему ребру с наименьшим весом; см. (10) и (11). Когда сообщение (

changeroot ( достигает узла инцидентнорго исходящему ребру с наименьшим

весом , этот узел посылает сообщение(connect ,L( через исходящее ребро с

наименьшим весом.

Проверка граней. Для нахождения наименьшего исходящего ребра узел p

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

(4). Локальный поиск ребра заканчивается когда либо не остается ребер(все

грани - reject или branch ), см. (4), либо один край идентифицирован как

исходящий; см. (6). Из-за порядка, в котором p осматривает грани, если p

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

Для осметра ребра pq, p посылает сообщение ( test, levelp, namep ( к q и

ждет ответ, который может сообщениями ( reject (, ( accept ( или ( test,

L, F ( . Сообщение (reject (, посылается процессом q (см. (5)) если q

обнаруживает, что имя фрагмента p, как в сообщении test, совпадает с именем

фрагмента q; узел q также отклоняет ребро в этом случае. При получении

сообщения ( reject ( p отклоняет ребро pq и продолжает локальный поиск;

см. (7). Сообщение ( reject ( пропускается, если ребро pq только что

использовалось q также, чтобы послать сообщение ( test,L,F(; в этом случае

сообщение ( test, L, F ( от q служит как ответ на сообщение p; см. (5).

Если имя фрагмента q отличается от p, посылается сообщение ( accept (. По

получении этого сообщения p заканчивает локальный поиск исходящих ребер

ребром pq как лучшим локальным выбором; см. (6).

Обработка сообщения ( test, L, F ( p отсрочена если L> levelp. Причина -

то, что p и q может фактически принадлежать одному и тому же фрагменту, но

сообщение (initiate, L, F, S ( еще не достиг p. Узел p мог бы ошибочно

отвечать q сообщением ( accept ( .

Объединение фрагментов. После того как исходящее ребро с наименьшим весом

фрагмента F = (name, level) было определено, сообщение (connect, level(

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

' - = (name', level'). Назовем процесс, посылающий сообщение (connect,

level( p и процесс, получающий его q. Узел q ранее послал сообщение

(accept( к p в ответ на сообщение ( test, level, name(, потому что поиск

лучшего исходящегоребра во фрагменте p закончился. Ожидание, организованное

перед ответом на сообщения test (см. (5)) дает level' ( level.

Согласно правилам объединения, обсужденным ранее, ответ (connect, level(

на сообщение (initiate, L, F, S ( имеет местов двух случаях.

Случай A: если level' > level, фрагмент p поглощается; узлам в этом

фрагменте сообщается новое имя фрагмента и уровень с помощью сообщения (

initiate, level', name', S (, которое отправляется всем узлам во фрагменте

F. Полный поглощенный фрагмент F становится поддеревом q в дереве охватов

фрагмента F ' и если q в настоящее время занят в поиске лучшего исходящего

ребра фрагмента F', все процессы в F должны участвовать. Вот почему q

включает состояние (find или found) в сообщение ( initiate, level', name',

S (.

Случай B: если два фрагмента имеют один и тот же уровень и лучшее исходящее

ребро фрагмента F ' также pq, новый фрагмент формируется с уровнем

наимбольшим из двух и именем - вес ребра pq: см. (2). Этот случай

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

branch : заметьте, что статус ребра становится branch, если сообщение

connect послано через него.

Если ни один из этих двух случаев не происходит, фрагмент F должен ждать,

пока q посылает сообщение (connect, L(, или уровень фрагмента q увеличился

достаточно, чтобы делать Случай применимым.

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

ясно, что ребро через которое фрагмент посылает сообщение (connect, L(

является действительно исходящим ребром фрагмента с наименьшим весом.

Вместе с Суждением 7.19 это означает, что MST вычислен правильно, если

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

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

сложное сообщение содержит вес одного ребра, один уровень (до logN) и

постоянное числа бит, чтобы указать тип сообщения и состояние узла.

Теорема 7.21 Gallager-Humblet-Spira алгоритм (7.11/7.12 7.10/ Алгоритма)

вычисляет минимальное дерево охватов, используя не более 5 N log N + 2(E(

сообщений.

Доказательство. Тупик потенциально возникает в ситуациях, где узлы или

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

или фрагменте. Ожидание, вставляное для сообщения ( report, (( на основном

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

получает сообщения от всех сыновей (если фрагмент в целом не ждет другой

фрагмент), после чего сообщение будет обработано.

Рассмотрите случай когда сообщение фрагмента F1 = (level1, name1)

достигает узла фрагмента F2 = (level2, name2). Сообщение ( connect, level1

) должно ждать, если level1 ( level2 и сообщение ( connect, level2 ) не

было послано через то же самое ребро фрагментом F2, см. (2). Сообщение(

test, level1, narne1 ) должно ждать, если level1 > level2, см. (5). Во всех

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