Реферат: Распределенные алгоритмы
Утверждение 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);
stachp [q] : ( basic, branch, reject) for each q Î Neighp ;
testchp, bestchp, fatherp : Neighp;
(1) Как первое действие каждого процесса, алгоритм должен быть инициализирован:
begin пусть pq канал процесса p с наименьшим весом ;
stachp [q] := branch ; levelp := 0 ;
send á connect, 0 ñ to q
end
(2) При получении á 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 ,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 :.= ¥ ;
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
