 |
Часть 2 Фундаментальные алгоритмы 7 глава
|
|
|
|
if winp = p then statep:== leader else statep:== lost
End
Алгоритм 7.9 Вырождение примененное к алгоритму эха.
Если q> caw p, сообщение просто игнорируется, эффективно приводя волну q к неудаче. Если с q = caw p, с сообщением поступают в соответствии с волновым алгоритмом. Если q < caw p или caw p = udef, p присоединяется к выполнению волны q, повторно присваивая переменным их начальные значения и присваивая caw p значение q. Когда волна, начатая q выполняет событие решения (в большинстве волновых алгоритмов, это решение всегда имеет место в q), q будет избран. Если волновой алгоритм такой, что решающий узел не обязательно равен инициатору, то решающий узел информирует инициатора через дерево охватов(остовное дерево) как определено в Lemma 6.3. При этом требуется не более N - 1 сообщений; мы игнорируем их в следующей теореме.
Теорема 7.17. Если А - централизованный волновой алгоритм, использующий М сообщений на одну волну, алгоритм Ex(A), выбирает лидера использую не более NM сообщений.
Доказательство. Пусть p 0 самый маленький инициатор. К волне, начатой p 0 немедленно присоединяются все процессы, которые получают сообщение этой волны, и каждый процесс заканчивает эту волну, потому что нет волны с меньшим идентификатором, для которой процесс прервал бы выполнение волны p 0. Следовательно, волна p 0 бежит к завершению, решение будет иметь место, и p 0 становится лидером.
Если p не инициатор, никакая волна с идентификатором p не начнется, следовательно p не станет лидером. Если p ¹ p 0 - инициатор, волна с идентификатором p будет начата, но решению в этой волне будет предшествовать событие посылки от p 0 (для этой волны), или имееть место в p 0 (Lemma 6.4). Так как p 0 никогда не выполняет событие посылки или внутреннее событие волны с идентификатором p, такое решение не имеет место, и p не избран.
|
|
|
Не более N волн начаты, и каждая волна использует по крайней мере М сообщений, что приводит к полной сложности к NM. o
Более тонким вопросом является оценка сложности по времени алгоритма Ex(A). Во многих случаях это будет величина того же порядока, что и сложность по времени алгоритма A, но в некоторых неудачных случаях, может случиться, что инициатор с самым маленьким идентификатором начинает волну очень поздно. В общем случае можно показать сложность по времени O (Nt) (где t - сложность по времени волнового алгоритма), потому что в пределах t единиц времени после того, как инициатор p начинает волну, волна p приходит к решению или начинается другая волна.
Если вырождение применяется к кольцевому алгоритму, получаем алгоритм Chang-Poberts; см. Упражнение 7.9. Алгоритм 7.9 является алгоритмом выбора полученным из алгоритма эха. Чтобы упростить описание, принимается что udef > q для всех q Î P. При исследовании кода, читатель должен обратить внимание, что после получения сообщения á tok,rñ с r < cawp p, оператор If с условием r = caw p также выполняется, вследствие более раннего присваивания caw p. Когда выбирается процесс p (получает á tok, pñ от каждого соседа), p посылает сообщение á ldr, pñ всем процессам, сообщая им, что p - лидер и заставляя их закончить алгоритм.
7.3.2 Алгоритм Gallager-Humblet-Spira
Проблема выбора в произвольных сетях тесно связана с проблемой вычисления дерева охватов с децентрализованным алгоритмом, как выдно из следующего рассуждения. Пусть CE сложность по сообщениям проблемы выбора и CТ сложность вычисления дерева охватов. Теорема 7.2 подразумевает, что CE £CT+O(N), и если лидер доступен, дерево охватов, может быть вычислено используя 2 ½ E ½ сообщений в алгоритме эха, который подразумевает что CT £ CE + 2 ½ E ½. Нижняя граница CE (теорема 7.15) подразумевает, что две проблемы имеют одинаковый порядок сдожности, а именно, что они требуют по крайней мере Ω (N log N + E) сообщений.
|
|
|
Этот подраздел представляет Gallager-Humblet-Spira (GHS), алгоритм для вычисления (минимального) дерева охватов, используя 2 ½ E ½ + 5N log N сообщений. Это показывает, что CE и CТ величины порядка q (N log N + E). Этот алгоритм был опубликован в [GHS83]. Алгоритм может быть легко изменен (как будет показано в конце этого подраздела) чтобы выбрать лидера в ходе вычисления, так, чтобы отдельный выбор как показано в выше не был необходим.
GHS алгоритм полагается на следующие предположения.
(1) Каждое ребро e имеет уникальный вес w (e). Предположим здесь, что w (e) - реальное число, но целые числа также возможны как веса ребер.
Если уникальные веса ребер не доступны априоре, каждому краю можно давать вес, который сформирован из меньшего из двух первых идентификаторов узлов, связанных с ребром. Вычисление веса края таким образом требует, чтобы узел знал идентификаторы соседей, что требует дополнительно 2 ½ E ½ сообщений при инициализации алгоритма.
(2) Все узлы первоначально находятся в спящем состоянии и просыпаются прежде, чем они начинают выполнение алгоритма. Некоторые узлы просыпаются спонтанно (если выполнение алгоритма вызвано обстоятельствами, встречающимися в этих узлах), другие могут получать сообщение алгоритма, в то время как они все еще спят. В последнем случае узел получающий сообщение сначала выполняет локалбную процедуру инициализации, а затем обрабатывает сообщение.
Минимальное дерево охватов. Пусть G = (V, E) взвешенный граф, где w {e) обозначает вес ребра e. Вес дерева охватов T графа G равняется сумме весов N-1 ребер, содержащихся в T, и T называется минимальным деревом охватов, или MST, (иногда минимальным по весу охватывающим деревом) если никакое дерево не имеет меньший вес чем T. В этом подразделе предполагаем, что каждое ребро имеет уникальный вес, то есть, различные ребра имеют различные веса, и это - известный факт что в этом случае имеется уникальное минимальное дерево охватов.
Утверждение 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. o
Утверждение 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, что является противоречием. o
Известные последовательные алгоритмы для вычисления 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. o
Резюме стратегии объединения. Фрагмент 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);
stach p [q] : (basic, branch, reject) for each q Î Neighp;
namep, bestwtp : real;
levelp : integer;
testchp, bestchp, fatherp : Neighp;
re cp : integer;
(1) Как первое действие каждого процесса, алгоритм должен быть инициализирован:
begin пусть pq канал процесса p с наименьшим весом;
stachp [q]:= branch; levelp:= 0;
statep:= found; recp:= 0;
send á connect, 0 ñ to q
end
(2) При получении á connect, L ñ от q:
begin if L < levelp then (* Объединение по правилу А *)
begin stach p[q]:= branch;
send á initiate, levelp,namep,statep ñ to q
end
else if stach p[q] = basic
then (* Правило C *) обработать сообщение позже
else (* Правило B *) send á initiate, levelp +1, w(pq),find ñ to q
end
(3) При получении á 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 w(pq) minimal;
send á test, level p, name p ñ to testch p
end
else begin testch p:= udef; report end
end
(5)При получении á 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 w (pq) < bestwt p
then begin bestwt p:= w (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, w ñ от g:
begin if q ¹ father p
then (* reply for initiate message *)
begin if w < bestwt p then
begin bestwt p:= w; bestch p:= q end;
rec p:= rec p + 1; report
end
else (* pq является основным ребром *)
if state p = find
then обработать это сообщение позже
else if w > bestwt p then changeroot
else if w = 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) При получении á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, wñ; см. (8). Узел p подсчитывает число сообщений á report, wñ, которые получает, используя переменную recp, которой присваивается значение 0 при начале поиска (см. (3)) и увеличивается на единицу при получении сообщения á report, wñ; см. (9). Каждый процесс посылает сообщение á report, wñ отцу, когда он получает такое сообщение от каждого из своих сыновей и заканчивает локальный поиск исходящего ребра.
Сообщения á report, wñ посылаются по направлению к основному ребру каждым процессом, и сообщения двух основных узлов пересекаются на ребре; оба получают сообщение от их отца; см. (9). Каждый основной узел ждет, пока он не пошлет сообщение á report, wñ сам пока он обрабатывает сообщение другого процесса. Когда два сообщения á report, wñ основных узлов пересеклись, основные узлы знают вес наименьшего исходящего ребра. Алгоритм закончился бы в этом точке, если никакое исходящее ребро не было бы передано (оба сообщения передают значения ¥).
Если исходящее ребро было передано, лучшее ребро находится следуя указателям 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 ñ.
|
|
|
