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;
(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 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 :.= ¥ ;
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 pthen 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ñ основных узлов пересеклись, основные узлы знают вес наименьшего исходящего ребра. Алгоритм закончился бы в этом точке, если никакое исходящее ребро не было бы передано (оба сообщения передают значения ¥).