Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 71
Текст из файла (страница 71)
Новым именем становится вес (pq), а статус find заставляет каждый процесс приступить к поиску исходящего ребра наименьшеговеса (см. действие (3)). Сообщение hinitiate, L + 1, N, Si поступает в каждыйузел нового фрагмента. Если же ранг процесса p был ниже, чем ранг процессаq, то p должен был отправить сообщение hconnect, Li по ребру e и должен былполучить в ответ сообщение hinitiate, L0 , N, Si от процесса q (см. действие (2)).Это означает, что L0 и N — текущий ранг и текущее имя процесса q. Это имяи этот ранг остаются неизменными у всех процессов, расположенных по ту жесторону от нашего ребра, что и узел q.
Полученное от процесса q сообщениераспространяется среди всех процессов, расположенных по ту же сторону отстержня, что и узел p, и вынуждает каждый такой процесс переменить имя иранг фрагмента (см. действие (3)). Если q пребывает в поиске исходящего ребранаименьшего веса (S = find), то процессы в той части фрагмента, где расположенпроцесс p, присоединяются к поиску, вызывая процедуру test.Каждый процесс в рассматриваемом фрагменте проводит поиск по всем исходящим из него ребрам (если таковые имеются, см.
действия (4), (5), (6), и (7)),стремясь отыскать такое ребро, которое выводит за пределы данного фрагмента, и если такие ребра будут обнаружены, то процесс выбирает среди них ребронаименьшего веса. Информация о ребре наименьшего веса передается каждо-268Гл. 7. Алгоритмы избрания лидера(8) procedure report:begin if recp = #{q : stachp [q] = branch ∧ q 6= fatherp }and testchp = udef thenbegin statep := found ; send hreport, bestwtp i to fatherp endend(9) После получения сообщения hreport, i от q:begin if q 6= fatherpthen (* ответить на сообщение initiate *)begin if < bestwtp thenbegin bestwtp := ; bestchp := q end;recp := recp + 1 ; reportendelse (* ребро pq — стержень *)if statep = findthen process this message laterelse if > bestwtpthen changerootelse if = bestwtp = ∞ then stopend(10) procedure changeroot:begin if stachp [bestchp ] = branchthen send hchangerooti to bestchpelse begin send hconnect, levelp i to bestchp ;stachp [bestchp ] := branchendend(11) После получения сообщения hchangerooti:begin changeroot endАлгоритм 7.12.
Алгоритм Галладжера—Хамблета—Спиры (Часть 3)му поддереву при помощи сообщения hreport, i (см. действие (8)). В узле pподсчитывается число полученных сообщений hreport, i, с использованием переменной recp . Этой переменной присваивается значение 0, когда начинается поиск (см.
действие (3)), и ее значение увеличивается на единицу при поступлениикаждого очередного сообщения hreport, i (см. действие (9)). Каждый процессотправляет сообщение hreport, i в родительский узел, как только он получиттакого рода сообщения от всех своих преемников и завершит свой собственныйлокальный поиск исходящего ребра.Сообщения hreport, i отправляются каждым процессом в направлении ребрастержня, и сообщения от обоих стержневых узлов пойдут навстречу друг другупо этому ребру; оба узла получат сообщения от своих родительских узлов father(см.
действие (9)). Каждый стержневой процесс не обрабатывает сообщение, полученное от его напарника, до тех пор пока он сам не отправит ему сообщениеhreport, i. Как только оба сообщения hreport, i от стержневых узлов пройдутнавстречу друг другу, стержневые узлы будут осведомлены о том, каков наименьший вес исходящего из фрагмента ребра. Здесь алгоритм и завершает работу,7.3. Произвольные сети269если не будет обнаружено ни одного исходящего ребра (в обоих сообщениях будет фигурировать значение ∞).Если же исходящее ребро наименьшего веса имеется, то отыскать это ребро можно, следуя в каждом узле по указателю bestch и начиная движение изстержневого узла, расположенного на той же стороне данного фрагмента, на которой располагается искомое ребро. По этому ребру должно быть отправленосообщение hconnect, Li, и указатели father во всех узлах данного фрагмента должны указывать в этом направлении.
Чтобы осуществить это, используется сообщение hchangerooti. Стержневой узел, расположенный в той частифрагмента, где находится исходящее ребро наименьшего веса, отправляет сообщение hchangerooti, которое следует по дереву к ребру наименьшего веса(см. действия (10) и (11)). Когда сообщение hchangerooti достигает узла, инцидентного исходящему ребру наименьшего веса, этот узел отправляет сообщениеhconnect, Li по указанному ребру.Проверка ребер. Узел p, стремясь отыскать исходящее из него ребро наименьшего веса, просматривает один за другим в порядке возрастания веса всехпримыкающих к нему ребер, имеющих статус basic(см.
действие (4)). Локальныйпоиск ребра завершается в том случае, когда либо не найдется ни одного такогоребра (все ребра имеют статус rejectили branch, см. действие (4)), либо одно изребер идентифицируется как исходящее (см. действие (6)). Порядок, в которомпроцесс p просматривает ребра, гарантирует, что первое обнаруженное им исходящее из фрагмента ребро будет иметь наименьший вес среди всех исходящих изp ребер, выводящих за пределы данного фрагмента.Для анализа ребра pq процесс p отправляет сообщение htest, level p , namep iпроцессу q и ожидает ответа, каковым может быть одно из трех сообщенийhrejecti, haccepti или htest, L, Fi.
Процесс q отправляет сообщение hrejecti(см. действие (5)), если он обнаружит, что имя того фрагмента, в котором расположен узел q, совпадает с именем того фрагмента, в котором расположен узел p;в этом случае процесс q также придаст этому ребру статус hrejecti. После получения сообщения hrejecti процесс p также будет считать ребро pq отвергнутыми продолжит локальный поиск (см. действие (7)). Сообщение hrejecti может бытьопущено, если ребро pq было только что так же задействовано процессом q дляотправления сообщения htest, L, F i. В этом случае сообщение htest, L, F i, полученное от q, истолковывается как отклик на сообщение, отправленное процессомp (см.
действие (5)). Если имя фрагмента, к которому относится узел q, отличается от имени фрагмента, в котором расположен узел p, то в ответ отправляетсясообщение haccepti. При получении сообщения haccepti, процесс p завершаетсвой локальный поиск исходящего из фрагмента ребра, имея в качестве результата ребро pq (см. (6)).Обработка сообщения htest, L, F i процессом p откладывается, если L >> levelp . Причина этого заключается в том, что узлы p и q могут на самом делепринадлежать одному и тому же фрагменту, но сообщение hinitiate, L + 1, N, Siеще не достигло узла p.
Тогда узел p мог бы ошибочно отправить узлу q сообщение haccepti.270Гл. 7. Алгоритмы избрания лидераСоединение фрагментов. Как только будет определено исходящее из фрагмента F = (name, level) ребро наименьшего веса, по нему отправляется сообщение hconnect, leveli, которое будет получено узлом, принадлежащим фрагменту F 0 = (name0 , level0). Обозначим символом p процесс, отправивший указанное сообщение, а символом q процесс, который принял это сообщение. Узелq ранее уже отправлял сообщение haccepti процессу p в ответ на сообщениеhtest, level, namei, поскольку поиск наилучшего исходящего ребра во фрагменте, к которому относится узел p, был завершен. Ожидание, проходящее передответом на тестовое сообщение (см. действие (5)), позволяет заключить, чтоlevel0 > level.Согласно правилам соединения, которые обсуждались ранее, на запрос hconnect, leveliбудет отправлено ответное сообщение hinitiate, L + 1, N, Si в двух случаях.Вариант A.
Если level0 > level, то фрагмент, содержащий узел p, поглощается; все узлы этого фрагмента оповещаются о новом имени и новом рангефрагмента посредством сообщения hinitiate, level 0 , name0 , Si, которое распространяется по всем узлам фрагмента F. Весь поглощаемый фрагмент F становится поддеревом, присоединенным к узлу q, в остовном дереве фрагмента F 0 , иесли узел q привлечен к поиску наилучшего ребра, исходящего из фрагмента F 0 ,то все процессы, относящиеся к фрагменту F, должны принять участие в этомпоиске. Поэтому процесс q включает свое состояние (findили found) в сообщениеhinitiate, level0 , name0 , Si.Вариант B.
Если два фрагмента имеют одинаковый ранг и наилучшим ребром, исходящим из фрагмента F 0 , также является pq, то образуется новый фрагмент, ранг которого повышается на единицу, а его именем становится вес ребраpq (см. действие (2)). Такой случай возможен, если два ранга равны и сообщение о соединении получено по ребру, имеющему статус branch. Следует обратитьвнимание на то, что ребро приобретает статус branch, если по нему отправляетсясообщение о соединении.Во всех остальных случаях фрагмент F должен пребывать в ожидании того,что либо q отправит сообщение hconnect, Li, либо ранг фрагмента, содержащего q, повысится настолько, чтобы стал осуществим вариант A.Корректность и сложность.
Из подробного описания алгоритма должнобыть ясно, что ребро, по которому из фрагмента отправляется сообщение hconnect, Li,действительно является исходящим из фрагмента ребром наименьшего веса. Отсюда, а также из утверждения 7.19 следует, что MST будет построено правильно,если каждый фрагмент действительно отправляет такое сообщение и соединяетсяс другим фрагментом, несмотря на ожидание, предусмотренное данным алгоритмом. Наиболее сложное сообщение включает в себя информацию о весе одногоребра, информацию о значении одного ранга (не более log N битов) и некотороефиксированное число битов для оповещения о типе сообщения и состоянии узла.Теорема 7.21. Алгоритм Галладжера—Хамблета—Спиры (алгоритм 7.10/7.11/7.12) вычисляет минимальное остовное дерево, используя при этом неболее 5N log N + 2|E| обменов сообщениями.7.3. Произвольные сети271Д о к а з а т е л ь с т в о.
Потенциальная возможность для взаимной блокировки возникает в тех ситуациях, когда узлы или фрагменты должны пребыватьв ожидании того, что определенные условия будут выполнены в другом узле илив другом фрагменте. Ожидание в стержневых узлах, связанное с сообщениямиhreport, i, не приводит к блокировке, потому что каждый стержневой узел раноили поздно получит сводки от всех своих преемников (если только весь фрагмент целиком не пребывает в ожидании другого фрагмента), после чего указанноесообщение будет обработано.Рассмотрим случай, когда сообщение, отправленное из фрагмента F 1 = (level1 , name1достигает какого-то узла фрагмента F2 = (level2 , name2). Сообщение hconnect, level1 iдолжно ожидать обработки, если level1 > level2 и никакое сообщение hconnect, level2 iне было отправлено по тому же самому ребру из фрагмента F 2 (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
