ref (664672), страница 29

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

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

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

Каждый процесс во фрагменте осуществляет поиск по все его ребрам (если такие существуют, см. (4), (5), (6), и (7)) для того, что определить имеются ли ребра выходящие из фрагмента, и если такие есть, выбирает наименьшее по весу. Исходящее ребро с наименьшим весом сообщается всем поддеревьям, с помощью сообщения report, ; см. (8). Узел p подсчитывает число сообщений report, , которые получает, используя переменную recp, которой присваивается значение 0 при начале поиска (см. (3)) и увеличивается на единицу при получении сообщения report, ; см. (9). Каждый процесс посылает сообщение report,  отцу, когда он получает такое сообщение от каждого из своих сыновей и заканчивает локальный поиск исходящего ребра.

Сообщения report,  посылаются по направлению к основному ребру каждым процессом, и сообщения двух основных узлов пересекаются на ребре; оба получают сообщение от их отца; см. (9). Каждый основной узел ждет, пока он не пошлет сообщение report,  сам пока он обрабатывает сообщение другого процесса. Когда два сообщения report,  основных узлов пересеклись, основные узлы знают вес наименьшего исходящего ребра. Алгоритм закончился бы в этом точке, если никакое исходящее ребро не было бы передано (оба сообщения передают значения ).

Если исходящее ребро было передано, лучшее ребро находится следуя указателям bestch в каждом узле, начиная с основного узла той стороны, с которой было передано лучшее ребро. Сообщение  connect, L  должно быть послано через это ребро, и все указатели отца во фрагменте должны указать в этом направлении; это выполняется с помощью посылки сообщения  changeroot . Основной узел, на чьей стороне расположено исходящее ребро с наименьшим весом, посылает сообщение  changeroot , которое посылается через дерево к исходящему ребру с наименьшим весом; см. (10) и (11). Когда сообщение  changeroot  достигает узла инцидентнорго исходящему ребру с наименьшим весом , этот узел посылает сообщениеconnect ,L через исходящее ребро с наименьшим весом.

Проверка граней. Для нахождения наименьшего исходящего ребра узел p осматривает основные ребра одно за другим в порядке увеличения веса; см. (4). Локальный поиск ребра заканчивается когда либо не остается ребер(все грани - reject или branch ), см. (4), либо один край идентифицирован как исходящий; см. (6). Из-за порядка, в котором p осматривает грани, если p опознает одно ребро как исходящее, оно должно иметь наименьший вес.

Для осметра ребра pq, p посылает сообщение  test, level_p, name_p  к 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,  на основном ребре не ведет к тупику, потому что каждый основной узел в конечном счете получает сообщения от всех сыновей (если фрагмент в целом не ждет другой фрагмент), после чего сообщение будет обработано.

Рассмотрите случай когда сообщение фрагмента F1 = (level1, name1) достигает узла фрагмента F2 = (level2, name2). Сообщение ( connect, level₁ ) должно ждать, если level1  level2 и сообщение ( connect, level₂ ) не было послано через то же самое ребро фрагментом F2, см. (2). Сообщение( test, level₁, narne₁ ) должно ждать, если level1 > level2, см. (5). Во всех случаях, где F1 ждет F2, верно одно из следующих утверждений.

(1) level ₁ > level₂ ,

(2) level₁ = level₂  e_F1 > e_F2;

(3) level₁ = level₂  e_F1 = e_F2 и F₂ все еще ищет исходящее ребро с наименьшим весом. (Т.к. 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 алгоритм может требовать время Ω(N²), если некоторые узлы начинают алгоритм очень поздно. Если используется дополнительная процедура пробуждения (требующая не более E сообщений) сложность алгоритма по времени 5N log N; см. Упражнение 7.11. Awerbuch [Awe87] показал, что сложность алгоритма по времени может быть улучшена од 0 (N), при сохранение оптимального порядка сложности по сообщениям ,то есть 0 (E + N log N).

Afek и другие [ALSY90] приспособили алгоритм, для вычисления леса охвата с благоприятными свойствами, а именно, что диаметр каждого дерева и количество деревьев - 0 (N^1/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 (N³), в зависимости от топологии сети.

В то время как строительство произвольных и минимальных деревьев охватов имеет равную сложность в произвольных сетях, это не так в кликах. Korach, Moran и Zaks [KMZ85] показали, что строительство минимального дерева охватов в взвешенной клике требует обмена Ω(N²) сообщениями. Этот результат указывает, что знание топологии не помогает уменьшать сложность обнаружения MST ниже границы из Теоремы 7.15. Произвольное дерево охватов клики может быть построено в 0 (N log N) сообщения, как мы покажем в следующем разделе; см. также [KMZ84].

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

Список файлов реферата