Предыдущая страница реферата | 26  27  28  29  30  31  32  33  34  35  36 | Следующая страница реферата

Утверждение 7.18 Если все веса ребер различны, то существует только одно
MST.

Доказательство. Предположим обратное, т.е. что T1 и T2 (где T1 ( T2) - минимальные деревья охватов. Пусть e ребро с самым маленьким весом, который находится в одном из деревьев, но не в обоих; такой край существует потому что T1 ( T2. Предположим, без потери общности, что e находится в T1, но не в T2. Граф T2 ( {e} содержит цикл, и поскольку T1 не содержит никакой цикл, по крайней мере одно ребро цикла, скажем e', не принадлежит T1. Выбор e подразумевает что w (e) < w (e '), но тогда дерево T2 ( {e} {e '} имеет меньший вес чем T2, который противоречит тому, что T2 - MST. (

Утверждение 7.18 - важное средство распределенного построения минимального дерева охватов, потому что не нужно делать выбор(распределенно) из множества законных ответов. Напротив каждый узел, который локально выбирает ребра, которые принадлежат любому минимальному дереву охватов таким образом, вносит вклад в строительство глобально уникального MST.
Все алгоритмы, для вычисления минимальное дерево охватов основаны на понятии фрагмента, который является поддеревом MST. Ребро e - исходящее ребро фрагмента F, если один конец e находится в F, и другой - нет.
Алгоритмы начинают с фрагментов, состоящих из единственного узла и увеличивают фрагменты, пока MST не полон, полагаясь на следующее наблюдение.

Утверждение 7.19 Если F - фрагмент и e - наименьшее по весу исходящее ребро
F, то F ( {e} - фрагмент

Доказательство. Предположите, что F ( {e} - не часть MST; тогда е формирует цикл с некоторыми ребрами MST, и одно из ребер MST в этом цикле, скажем f, - исходящее ребро F. Из выбора e - w (e) < w (f), но тогда удаляя f из MST и вставляя e получим дерево с меньшим весом чем MST, что является противоречием. (

Известные последовательные алгоритмы для вычисления MST - алгоритмы Prim и
Kruskal. Алгоритм Prim [CLR90, Раздел 24.2] начинается с одного фрагмента и увеличивает его на каждом шаге включая исходящее ребротекущего фрагмента с наименьшим весом. Алгоритм Kruskal [CLR90, Раздел 24.2] начинается с множества фрагментов, состоящих из одного узла, и сливает фрагменты, добавляя исходящее ребро некоторого фрагмента с наименьшим весом . Т.к. алгоритм Kruskal позволяет нескольким фрагментам действовать независимо, он более подходит для выполнения в распределенном алгоритме.

7.3.3 Глобальное Описание GHS Алгоритма.
Сначала мы опишем как алгоритм работает глобальным способом, то есть, с точки зрения фрагмента. Тогда мы опишем локальный алгоритм, который должен выполнить каждый узел, чтобы получить это глобальное преобразование фрагментов.
Вычисление 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). Во всех случаях, где 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 алгоритма, покажем, что число маркеров, произведенных на каждом уровне уменьшается до одного, на некотором уровне чей инициатор будет избран. 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. Посещенный процесс представляет волне свой текущий цвет.
Действительно, все основные коммуникации также как деятельность волны сохраняют это утверждение, которое является поэтому инвариантом. Волна заканчивается неудачно, если процессы принимают решение для черной волны, но в этом случае просто начинается новая волна. Новая волна может быть успешной, только если процессы могут стать белыми, и это случается немедленно после посещения волны.
Правило 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

Рекомендуем скачать другие рефераты по теме: педагогические рефераты, реферат машини.

Предыдущая страница реферата | 26  27  28  29  30  31  32  33  34  35  36 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки