Быстрый поиск

Реферат: Распределенные алгоритмы

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).

Узел и статус связи. Узел 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

(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.