Если исходящее ребро было передано, лучшее ребро находится следуя указателям bestch в каждом узле, начиная с основного узла той стороны, с которой было передано лучшее ребро. Сообщение á connect, L ñ должно быть послано через это ребро, и все указатели отца во фрагменте должны указать в этом направлении; это выполняется с помощью посылки сообщения á changeroot ñ. Основной узел, на чьей стороне расположено исходящее ребро с наименьшим весом, посылает сообщение á changeroot ñ, которое посылается через дерево к исходящему ребру с наименьшим весом; см. (10) и (11). Когда сообщение á changeroot ñ достигает узла инцидентнорго исходящему ребру с наименьшим весом , этот узел посылает сообщениеáconnect ,Lñ через исходящее ребро с наименьшим весом.
Проверка граней. Для нахождения наименьшего исходящего ребра узел p осматривает основные ребра одно за другим в порядке увеличения веса; см. (4). Локальный поиск ребра заканчивается когда либо не остается ребер(все грани - reject или branch ), см. (4), либо один край идентифицирован как исходящий; см. (6). Из-за порядка, в котором p осматривает грани, если p опознает одно ребро как исходящее, оно должно иметь наименьший вес.
Для осметра ребра pq, p посылает сообщение á test, levelp, namepñ к q и ждет ответ, который может сообщениями á reject ñ, á accept ñ или á test, L, F ñ . Сообщение áreject ñ, посылается процессом q (см. (5)) если q обнаруживает, что имя фрагмента p, как в сообщении test, совпадает с именем фрагмента q; узел q также отклоняет ребро в этом случае. При получении сообщения á reject ñ p отклоняет ребро pq и продолжает локальный поиск; см. (7). Сообщение á reject ñ пропускается, если ребро pq только что использовалось q также, чтобы послать сообщение á test,L,Fñ; в этом случае сообщение á test, L, F ñ от q служит как ответ на сообщение p; см. (5). Если имя фрагмента q отличается от p, посылается сообщение á accept ñ. По получении этого сообщения p заканчивает локальный поиск исходящих ребер ребром pq как лучшим локальным выбором; см. (6).
Обработка сообщения á test, L, F ñ p отсрочена если L> levelp. Причина - то, что p и q может фактически принадлежать одному и тому же фрагменту, но сообщение áinitiate, L, F, S ñ еще не достиг p. Узел p мог бы ошибочно отвечать q сообщением á accept ñ .
Объединение фрагментов. После того как исходящее ребро с наименьшим весом фрагмента F = (name, level) было определено, сообщение áconnect, levelñ посылается через это ребро, и получается узлом, принадлежащим к фрагменту F ' - = (name', level'). Назовем процесс, посылающий сообщение áconnect, levelñ p и процесс, получающий его q. Узел q ранее послал сообщение áacceptñ к p в ответ на сообщение á test, level, nameñ, потому что поиск лучшего исходящегоребра во фрагменте p закончился. Ожидание, организованное перед ответом на сообщения test (см. (5)) дает level' £ level.
Согласно правилам объединения, обсужденным ранее, ответ áconnect, levelñ на сообщение áinitiate, L, F, S ñ имеет местов двух случаях.
Случай A: если level' > level, фрагмент p поглощается; узлам в этом фрагменте сообщается новое имя фрагмента и уровень с помощью сообщения á initiate, level', name', S ñ, которое отправляется всем узлам во фрагменте F. Полный поглощенный фрагмент F становится поддеревом q в дереве охватов фрагмента F ' и если q в настоящее время занят в поиске лучшего исходящего ребра фрагмента F', все процессы в F должны участвовать. Вот почему q включает состояние (find или found) в сообщение á initiate, level', name', S ñ.
Случай B: если два фрагмента имеют один и тот же уровень и лучшее исходящее ребро фрагмента F ' также pq, новый фрагмент формируется с уровнем наимбольшим из двух и именем - вес ребра pq: см. (2). Этот случай происходит, если два уровня равны, и сообщение connect получено через ребро branch : заметьте, что статус ребра становится branch, если сообщение connect послано через него.
Если ни один из этих двух случаев не происходит, фрагмент F должен ждать, пока q посылает сообщение áconnect, Lñ, или уровень фрагмента q увеличился достаточно, чтобы делать Случай применимым.
Правильность и сложность. Из детального описания алгоритма должно быть ясно, что ребро через которое фрагмент посылает сообщение áconnect, Lñ является действительно исходящим ребром фрагмента с наименьшим весом. Вместе с Суждением 7.19 это означает, что MST вычислен правильно, если каждый фрагмент действительно посылает такое сообщение и присоединяется к другому фрагменту, несмотря на ожидание, вызванного алгоритмом. Наиболее сложное сообщение содержит вес одного ребра, один уровень (до logN) и постоянное числа бит, чтобы указать тип сообщения и состояние узла.
Теорема 7.21 Gallager-Humblet-Spira алгоритм (7.11/7.12 7.10/ Алгоритма) вычисляет минимальное дерево охватов, используя не более 5 N log N + 2½E½ сообщений.
Доказательство. Тупик потенциально возникает в ситуациях, где узлы или фрагменты должны ждать, пока некоторое условие не происходит в другом узле или фрагменте. Ожидание, вставляное для сообщения á report, wñ на основном ребре не ведет к тупику, потому что каждый основной узел в конечном счете получает сообщения от всех сыновей (если фрагмент в целом не ждет другой фрагмент), после чего сообщение будет обработано.
Рассмотрите случай когда сообщение фрагмента F1 = (level1, name1) достигает узла фрагмента F2 = (level2, name2). Сообщение ( connect, level1 ) должно ждать, если level1 ³ level2 и сообщение ( connect, level2 ) не было послано через то же самое ребро фрагментом F2, см. (2). Сообщение( test, level1, narne1 ) должно ждать, если level1 > level2, см. (5). Во всех случаях, где F1 ждет F2, верно одно из следующих утверждений.
(1) level 1 > level2 ,
(2) level1 = level2 Ù w(eF1) > w(eF2);
(3) level1 = level2Ù w(eF1) = w(eF2) и F2 все еще ищет исходящее ребро с наименьшим весом. (Т.к. eF1 - исходящее ребро F2, не возможно чтобы w (eF2) > w (eF1).)
Таким образом никакой тупиковый цикл не может возникнуть.
Каждое ребро отклоняется не более одного раза, и это требует двух сообщений, который ограничивает число сообщений reject и сообщений test как следствий отклонений к 2½E½. На любом уровне, узел получает не более одного сообщения initiate и accept , и посылает не более одного сообщения report, и одно changeroot или connect сообщение, и одно test сообщение, не ведущее к отклонению. На нулевом уровнени одно сообщение accept не получается и не одно сообщение report или test не посылается. На высшем уровне каждый узел только посылает сообщение report и получает одно сообщение initiate. Общее количество сообщений поэтому ограничено 2½E½ + 5N log N. -
7.3.5 Обсуждения и Варианты GHS Алгоритма
Gallager-Humblet-Spira алгоритм - один из наиболее сложных волновых алгоритмов, требует только локальное знание и имеет оптимальную сложность по сообщениям. Алгоритм может легко быть расширен так, чтобы он выбрал лидера, используя только на два больше сообщений. Алгоритм заканчивает в двух узлах, а именно основных узлах последнего фрагмента (охватывающего полную сеть). Вместо выполнения остановки, основные узлы обменивают их идентификаторами, и меньший из них становится лидером.
Было опубликовано множество разновидностей и родственных алгоритмов. GHS алгоритм может требовать время Ω(N2), если некоторые узлы начинают алгоритм очень поздно. Если используется дополнительная процедура пробуждения (требующая не более ½E½ сообщений) сложность алгоритма по времени 5N log N; см. Упражнение 7.11. Awerbuch [Awe87] показал, что сложность алгоритма по времени может быть улучшена од 0 (N), при сохранение оптимального порядка сложности по сообщениям ,то есть 0 (½E½ + N log N).
Afek и другие [ALSY90] приспособили алгоритм, для вычисления леса охвата с благоприятными свойствами, а именно, что диаметр каждого дерева и количество деревьев - 0 (N1/2). Их алгоритм распределенно вычисляет кластеризацию сети как показано в Lemma 4.47 и дерево охвата и центр каждого кластера.
Читатель может спрасить, могут ли произвольные деревя охватов быть построены более эффективно чем минимальные деревя охватов, но Теорема 7.15 также дает низкую границу Ω(NlogN +½E½) на построение произвольных деревьев охватов. Johansen и другие [JJN ^ 87] дают алгоритм для вычисления произвольного дерева охватов, который использует3N log N + 2½E½ +0(N) сообщений, таким образом улучшая GHS алгоритме на постоянный множитель, если сеть редка. Barllan и Zernik [BIZ89] представили алгоритм, который вычисляет случайные деревья охватов, где каждое возможное дерево охватов выбрано с равной вероятностью. Алгоритм - рандомизирован и использует ожидаемое число сообщений, которое находится в границах между 0 (NlogN +½E½)) и 0 (N3), в зависимости от топологии сети.
В то время как строительство произвольных и минимальных деревьев охватов имеет равную сложность в произвольных сетях, это не так в кликах. Korach, Moran и Zaks [KMZ85] показали, что строительство минимального дерева охватов в взвешенной клике требует обмена Ω(N2) сообщениями. Этот результат указывает, что знание топологии не помогает уменьшать сложность обнаружения MST ниже границы из Теоремы 7.15. Произвольное дерево охватов клики может быть построено в 0 (N log N) сообщения, как мы покажем в следующем разделе; см. также [KMZ84].
7.4 Алгоритм Korach-Kutten-Moran
Много результатов были получены для проблемы выбора, не только для случая кольцевых сетей и произвольных сетей, но также и для случая другой специализированной топологии, типа сетей клик, и т.д. В нескольких случаях лучшие известные алгоритмы имеют сложность по сообщениям 0(N log N) и в некоторых случаях этот результат достигает Ω(NlogN). Korach, Kutten, и Moran [KKM90] показали, что имеется тесная связь между сетеми выбора и обхода. Их главный результат - общее строительство эффективного алгоритма выбора для класса сетей, учитывая алгоритм обхода для этого класса. Они показывают, что когда строительство снабжено лучшим алгоритмом обхода, известным для класса сетей, результирующий алгоритм благоприятно сравним с лучшим алгоритмом выбора, известным для того класса в большинстве случаев. Дело обстоит не так для сложности по времени; Сложность времени алгоритма равняется сложности по сообщениям, и в некоторых случаях известны другие алгоритмы с той же самой сложностью по сообщениям и более низкой сложностью времени.