Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 70

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 70)

Все узлы фрагмента участву­ют совместно в поиске исходящего из этого фрагмента ребра наименьшего веса,и как только такое ребро будет обнаружено, по нему отправляется сообщениеГл. 7. Алгоритмы избрания лидера266var stateP: (sleep, find, found) ;stachp[q]:(basic, branch, reject) для каждого q € Neighp ;namep, bestwtp:real;levelp:integer;testchp, bestchp,fat herp :Neighp ;recp:integer;(1) Первым действием каждого процесса является инициализация данного алгоритма:begin пусть pq — это канал связи процесса р, имеющий наименьший вес ;stachp[q] := branch ; levelp := 0 ;statep := found ; recp := 0 ;send (connect, 0) to qend(2) После получения сообщения (connect, L) от q:begin if L < levelp then (* Соединить по правилу A *)begin stachp[q] := branch ;send (initiate, levelp, namep, statep) to qendelse if stachp[q] = basicthen (* Правило С *) обработать это сообщение позднееelse (* Правило В *) send (initiate, levelp + 1, ы(pq ), find) to qend(3) После получения сообщения (initiate, L, F , S ) от q:begin levelp := L ; namep := F ; statep := S ; fatherp := q ;bestchp := udef ; bestwtp := oo ;forall r € Neighp : stachp[r] = branch A г Ф q dosend (initiate, L, F, S ) to r ;if statep = find then begin recp := 0 ; test endendА л гор и тм 7.10.Алгоритм Галладжера—Хамблета—Спиры (Часть1).(connect, L), где L — ранг данного фрагмента.

Если фрагмент состоит из един­ственного узла, как это случается после инициализации такого узла, то нужноеребро — это просто инцидентное данному узлу ребро наименьшего веса (см. дей­ствие ( 1 )), и сообщение (connect, 0 ) отправляется по этому ребру.Теперь рассмотрим случай, когда новый фрагмент образовался за счет со­единения двух фрагментов ребром е = pq.

Если оба соединенных фрагментаимели одинаковый ранг L, то оба процесса р и q должны были отправить со­общение (connect, L) по ребру е и должны были получить в ответ сообщение(connect, L), и при этом ребро е должно иметь статус branch)см. действие (2 )).Ребро pq становится стержнем нового фрагмента, и процессы р и q обменивают­ся сообщениями (initiate, L + 1, N, S), придавая вновь образованному фрагментуновый ранг и новое имя. Новым именем становится вес oi(pq), а статус find за­ставляет каждый процесс приступить к поиску исходящего ребра наименьшеговеса (см.

действие (3)). Сообщение (initiate, L + 1, N, S) поступает в каждыйузел нового фрагмента. Если же ранг процесса р был ниже, чем ранг процесса7.3. Произвольные сети267(4) procedure testbegin if6 Neighp : stachp[q] = basic thenbegin testchp := q with stachp[q] = basic and <o(pq) minimal ;send (test, levelp, namep) to testchpendelse begin testchp := udef ; report endend(5) После получения сообщения (test, L, F) от q:begin if L > levelp then (* С ответом придется подождать! *)обработать это сообщение позднееelse if F = патер then (* внутреннее ребро *)begin if stachp[q\ = basic then stachp[q] := reject ;if q Ф testchpthen send (reject) to qelse testendelse send (accept) to qend(6) После получения сообщения (accept) от q:begin testchp := udef ;if co(pq) < bestwtpthen begin bestwtp := u(pq) ; bestchp := q end;reportend(7) После получения сообщения (reject) от q:begin if stachp[q] = basic then stachp[q] := reject,testendАлгоритм 7.11.

Алгоритм Галладжера— Хамблета— Спиры (Часть 2).q, то р должен был отправить сообщение (connect, L) по ребру е и должен былполучить в ответ сообщение (initiate, L ', N, S ) от процесса q (см. действие (2 )).Это означает, что L' и N — текущий ранг и текущее имя процесса q. Это имяи этот ранг остаются неизменными у всех процессов, расположенных по ту жесторону от нашего ребра, что и узел q.

Полученное от процесса q сообщениераспространяется среди всех процессов, расположенных по ту же сторону отстержня, что и узел р, и вынуждает каждый такой процесс переменить имя иранг фрагмента (см. действие (3)). Если q пребывает в поиске исходящего ребранаименьшего веса (S = find), то процессы в той части фрагмента, где расположенпроцесс р, присоединяются к поиску, вызывая процедуру test.Каждый процесс в рассматриваемом фрагменте проводит поиск по всем ис­ходящим из него ребрам (если таковые имеются, см. действия (4), (5), (6 ), и (7)),стремясь отыскать такое ребро, которое выводит за пределы данного фрагмен­та, и если такие ребра будут обнаружены, то процесс выбирает среди них ребронаименьшего веса. Информация о ребре наименьшего веса передается каждо-Гл.

7. Алгоритмы избрания лидера268(8) p roced u re reportb egin if recp = # { q : stachp[q\ = branch Aq / fatherp}and testchp = udef th enb egin state,, := found ; send (report, bestwtp) to fatherp en dend(9) После получения сообщения (report, со) от q:b egin if q ф fatherpth en (* ответить на сообщение in itia te *)begin if со < bestwtp th enb egin bestwtp := со ; bestchp := q end;recp := recp + 1 ; reportendelse (* ребро pq — стержень *)if statep = findth en process this m essage latere ls e if to > bestwtpth en changerootelse if со = bestwtp = oo th en sto pend(10) p rocedure changerootbegin if stachp[bestchp] = branchth en send (ch a n g ero o t) to bestchpelse b egin send (co n n ect, levelp) to bestchp ;stachp[bestchp\ := branchendend(11) После получения сообщения (ch an geroot):b egin changeroot endАлгоритм 7.12.Алгоритм Галладжера— Хамблета— Спиры (Часть 3)му поддереву при помощи сообщения (report, со) (см.

действие (8 )). В узле рподсчитывается число полученных сообщений (report, со), с использованием пе­ременной recp. Этой переменной присваивается значение 0, когда начинается по­иск (см. действие (3)), и ее значение увеличивается на единицу при поступлениикаждого очередного сообщения (report, со) (см. действие (9)). Каждый процессотправляет сообщение (report, со) в родительский узел, как только он получиттакого рода сообщения от всех своих преемников и завершит свой собственныйлокальный поиск исходящего ребра.Сообщения (report, со) отправляются каждым процессом в направлении ребрастержня, и сообщения от обоих стержневых узлов пойдут навстречу друг другупо этому ребру; оба узла получат сообщения от своих родительских узлов father(см.

действие (9)). Каждый стержневой процесс не обрабатывает сообщение, по­лученное от его напарника, до тех пор пока он сам не отправит ему сообщение(report, со). Как только оба сообщения (report, со) от стержневых узлов пройдутнавстречу друг другу, стержневые узлы будут осведомлены о том, каков наимень­ший вес исходящего из фрагмента ребра. Здесь алгоритм и завершает работу,7.3. Произвольные сети269если не будет обнаружено ни одного исходящего ребра (в обоих сообщениях бу­дет фигурировать значение оо).Если же исходящее ребро наименьшего веса имеется, то отыскать это реб­ро можно, следуя в каждом узле по указателю bestch и начиная движение изстержневого узла, расположенного на той же стороне данного фрагмента, на ко­торой располагается искомое ребро.

По этому ребру должно быть отправленосообщение (connect, L), и указатели father во всех узлах данного фрагмен­та должны указывать в этом направлении. Чтобы осуществить это, использу­ется сообщение (changeroot). Стержневой узел, расположенный в той частифрагмента, где находится исходящее ребро наименьшего веса, отправляет со­общение (changeroot), которое следует по дереву к ребру наименьшего веса(см. действия (10) и (11)). Когда сообщение (changeroot) достигает узла, инци­дентного исходящему ребру наименьшего веса, этот узел отправляет сообщение(connect, L) по указанному ребру.Проверка ребер.

Узел р, стремясь отыскать исходящее из него ребро наи­меньшего веса, просматривает один за другим в порядке возрастания веса всехпримыкающих к нему ребер, имеющих статус basic(см. действие (4)). Локальныйпоиск ребра завершается в том случае, когда либо не найдется ни одного такогоребра (все ребра имеют статус rejectvum branch, см. действие (4)), либо одно изребер идентифицируется как исходящее (см. действие (6 )). Порядок, в которомпроцесс р просматривает ребра, гарантирует, что первое обнаруженное им исхо­дящее из фрагмента ребро будет иметь наименьший вес среди всех исходящих изр ребер, выводящих за пределы данного фрагмента.Для анализа ребра pq процесс р отправляет сообщение (test, levelp, патер)процессу q и ожидает ответа, каковым может быть одно из трех сообщений(reject), (accept) или (test, L, F).

Процесс q отправляет сообщение (reject)(см. действие (5)), если он обнаружит, что имя того фрагмента, в котором распо­ложен узел q, совпадает с именем того фрагмента, в котором расположен узел р\в этом случае процесс q также придаст этому ребру статус (reject). После полу­чения сообщения (reject) процесс р также будет считать ребро pq отвергнутыми продолжит локальный поиск (см.

действие (7)). Сообщение (reject) может бытьопущено, если ребро pq было только что так же задействовано процессом q дляотправления сообщения (test, L, F). В этом случае сообщение (test, L, F), полу­ченное от q, истолковывается как отклик на сообщение, отправленное процессомр (см. действие (5)). Если имя фрагмента, к которому относится узел q, отлича­ется от имени фрагмента, в котором расположен узел р, то в ответ отправляетсясообщение (accept). При получении сообщения (accept), процесс р завершаетсвой локальный поиск исходящего из фрагмента ребра, имея в качестве резуль­тата ребро pq (см.

Характеристики

Список файлов книги