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 ;
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
else if stachp[q] = basic
then (* Правило C *) обработать сообщение позже
else (* Правило B *) send á initiate, levelp +1 ,w(pq) ,find ñ to q
(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
Алгоритм 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
else begin testch p := udef ; report 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
(6) При получении á acceptñ от q:
begin testch p := udef ;
if w(pq) < bestwt p
then begin bestwt p := w(pq) ; bestch p := q end ;
report
(7) Пр получении á reject ñ от q:
test
Алгоритм 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 }
Страницы: 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
