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

более k раз, т.е. ?€k раз, но не ?€k+1 раз. В результате количество

расположений, где это выполняется, равно [pic], т.е. [pic] ( для k <

i ).

Общее количество передач во всех расположениях равно:

[pic],

что равняется [pic]. Сумма [pic]известна как i-е гармоническое число,

обозначаемое ?i. В качестве Упражнения 7.3 оставлено доказательство

тождества [pic].

Далее мы суммируем по i количество передач маркера, чтобы получить общее

количество передач (исключая передачи ) во всех расположениях. Оно

равно

[pic].

Добавляя N(N-1)! передач маркера для , мы получаем общее количество

передач, равное

[pic].

Т.к. это число выведено для (N-1)! различных расположений, среднее по всем

расположениям, очевидно, равно N(?N, что составляет ?0.69N logN (см.

Упр.7.4).

7.2.2 Алгоритм Petersen / Dolev-Klawe-Rodeh

Алгоритм Чанга-Робертса достигает сложности сообщений O(N logN) в среднем,

но не в наихудшем случае. Алгоритм со сложностью O(N logN) в наихудшем

случае был дан Франклином [Franklin; Fra82], но этот алгоритм требует,

чтобы каналы были двунаправленными. Petersen [Pet82] и Dolev, Klawe, Rodeh

[DKR82] независимо разработали очень похожий алгоритм для однонаправленных

колец, решающий задачу с использованием только O(N logN) сообщений в

наихудшем случае. Алгоритм требует, чтобы каналы подчинялись дисциплине

FIFO.

Сначала алгоритм вычисляет наименьший идентификатор и сообщает его каждому

процессу, затем процесс с этим идентификатором становится лидером, а все

остальные терпят поражение. Алгоритм легче понять, если представить, что он

выполняется идентификаторами, а не процессами. Изначально каждый

идентификатор активен, но на каждом круге некоторые идентификаторы

становятся пассивными, как будет показано позднее. При обходе круга

активный идентификатор сравнивает себя с двумя соседними активными

идентификаторами по часовой стрелке и против нее. Если он является

локальным минимумом, он остается в круге, иначе он становится пассивным.

Т.к. все идентификаторы различны, идентификатор рядом с локальным минимумом

сам не является локальным минимумом, откуда следует, что не менее половины

идентификаторов выбывают из круга при каждом обходе. Следовательно, после

не более чем logN кругов остается только один активный идентификатор,

который и является победителем.

[pic]

Рис.7.6 Процесс p получает текущие идентификаторы q и r.

Этот принцип может быть непосредственно реализован в двунаправленных сетях,

как это сделано в алгоритме Франклина [Fra82]. В ориентированных кольцах

сообщения можно посылать только по часовой стрелке, что затрудняет

получение соседнего активного идентификатора в этом направлении; см. Рис.

7.6. Идентификатор q нужно сравнить с r и p; идентификатор r можно послать

q, но идентификатор p нужно было бы передавать против направления каналов.

Чтобы сравнить q и с r, и с p, идентификатор q передается (в направлении

кольца) процессу, который имеет идентификатор p, а r передается не только

процессу с идентификатором q, но и дальше, процессу с идентификатором p.

Если q является единственным активным идентификатором в начале обхода

круга, первый идентификатор, который q встречает при обходе, равен q (т.е.

в этом случае p = q). Когда это происходит, идентификатор q выигрывает

выборы.

Алгоритм для процессов в однонаправленном кольце обозначен как Алгоритм

7.7. Процесс p является активным в круге, если он в начале круга имеет

активный идентификатор cip. Иначе p является пассивным и просто пропускает

через себя все получаемые сообщения. Активный процесс посылает свой текущий

идентификатор следующему активному процессу, и получает текущий

идентификатор предыдущего активного процесса, используя сообщения .

Полученный идентификатор сохраняется (в переменной acnp), и если он не

выбывает из круга, он будет текущим идентификатором p в следующем круге.

Чтобы определить, остается ли идентификатор acnp в круге, его сравнивают с

cip и активным идентификатором, полученным в сообщении . Процесс p

посылает сообщение , чтобы следующий активный процесс мог

провести такое же сравнение. Исключение возникает, когда acnp = cip; в этом

случае остался один активный идентификатор и об этом сообщается всем

процессам в сообщении .

var cip : P init p ; (* Текущий идентификатор p *)

acnp : P init udef ; (* Идентификатор соседа против часовой

стрелки *)

winp : P init udef ; (* Идентификатор победителя *)

statep : (active, passive, leader, lost) init active ;

begin if p - инициатор then statep := active else statep := passive ;

while winp = udef do

begin if statep = active then

begin send ; receive ; acnp := q ;

if acnp = cip then (* acnp - минимум *)

begin send ; winp := acnp ;

receive

end

else (* acnp - текущий идентификатор соседа *)

begin send ; receive ;

if acnp < cip and acnp < q

then cip := acnp

else statep := passive

end

end

else (* statep = passive *)

begin receive ; send ;

receive m ; send m ;

(* m - либо , либо *)

if m - then winp := q

end

end ;

if p = winp then statep := leader else statep := lost

end

Алгоритм 7.7 Алгоритм Petersen / Dolev-Klawe-Rodeh.

Теорема 7.7 Алгоритм 7.7 решает задачу выбора для однонаправленных сетей с

использованием O(N logN) сообщений.

Доказательство. Будем говорить, что процесс находится на i-м круге, когда

он выполняет основной цикл в i-й раз. Обходы круга не синхронизированы

глобально; возможно, что в различных частях кольца один процесс на

несколько кругов впереди другого. Но, т.к. каждый процесс отправляет и

получает в каждом круге ровно по два сообщения и каналы подчиняются

дисциплине FIFO, то сообщение всегда будет получено в том же круге, в каком

оно было послано. На первом круге все инициаторы активны и все имеют

различные «текущие идентификаторы».

Утверждение 7.8 Если круг i начинается с k (k>1) активными процессами, и

все процессы имеют различные ci, то в круге остаются не меньше 1 и не

больше k/2 процессов. В конце круга снова все текущие идентификаторы

активных процессов различны и включают наименьший идентификатор.

Доказательство. Путем обмена сообщениями , которые пропускаются

пассивными процессами, каждый активный процесс получает текущий

идентификатор своего активного соседа против часовой стрелки, который

всегда отличается от его собственного идентификатора. Далее, каждый

активный процесс продолжает обход круга, передавая сообщения ,

благодаря которым каждый активный процесс получает текущий идентификатор

своего второго активного соседа против часовой стрелки. Теперь все активные

процессы имеют различные значения acn, откуда следует, что в конце круга

все оставшиеся в круге идентификаторы различны. По крайней мере, остается

идентификатор, который был наименьшим в начале круга, т.е. остается хотя бы

один процесс. Идентификатор рядом с локальным минимумом не является

локальным минимумом, откуда следует, что количество оставшихся в круге не

превышает k/2.

Из Утверждения 7.8 следует, что существует круг с номером ?€?logN?+1,

который начинается ровно с одним активным идентификатором, а именно, с

наименьшим среди идентификаторов инициаторов.

Утверждение 7.9 Если круг начинается ровно с одним активным процессом p с

текущим идентификатором cip, то алгоритм завершается после этого круга с

winq = cip для всех q.

Доказательство. Сообщение пропускается всеми процессами и, в

конце концов, его получает p. Процесс p обнаруживает, что acnp = cip и

посылает по кольцу сообщение , вследствие чего все процессы

выходят из основного цикла с winp = acnp.

Алгоритм завершается в каждом процессе и все процессы согласовывают

идентификатор лидера (в переменной winp); этот процесс находится в

состоянии лидер, а остальные - в состоянии проигравший.

Всего происходит не более ?logN?+1 обходов круга, в каждом из которых

передается ровно 2N сообщений, что доказывает, что сложность сообщений

ограничена 2N logN + O(N). Теорема 7.7 доказана.

Dolev и др. удалось улучшить свой алгоритм до 1.5N logN, после чего

Petersen получил алгоритм, использующий только 1.44N logN сообщений. Этот

алгоритм снова был улучшен Dolev и др. до 1.356N logN. Верхняя граница в

1.356N logN считалась наилучшей для выбора на кольцах более 10 лет, но была

улучшена до 1.271N logN Higham и Przytycka [HP93].

7.2.3 Вывод нижней границы

В этом подразделе будет доказана нижняя граница сложности выбора на

однонаправленных кольцах. Т.к. выбор можно провести за одно выполнение

децентрализованного волнового алгоритма, нижняя граница сложности

децентрализованных волновых алгоритмов для колец будет получена как

заключение.

Результат получен Pachl, Korach и Rotem [PKR84] при следующих

предположениях.

Граница доказывается для алгоритмов, вычисляющих наименьший идентификатор.

Если существует лидер, наименьший идентификатор может быть вычислен с

помощью N сообщений, а если наименьший идентификатор известен хотя бы

одному процессу, процесс с этим идентификатором может быть выбран опять же

за N сообщений. Следовательно, сложность задач выбора и вычисления

наименьшего идентификатора различаются не более чем на N сообщений.

Кольцо является однонаправленным.

Процессам не известен размер кольца.

Предполагается, что каналы FIFO. Это предположение не ослабляет результат,

потому что сложность не-FIFO алгоритмов не лучше сложности FIFO алгоритмов.

Предполагается, что все процессы являются инициаторами. Это предположение

не ослабляет результат, потому что оно описывает ситуацию, возможную для

каждого децентрализованного алгоритма.

Предполагается, что алгоритмы управляются сообщениями; т.е. после

отправления сообщений при инициализации алгоритма, процесс посылает

сообщения в дальнейшем только после получения очередного сообщения. Т.к.

рассматриваются асинхронные системы, общие алгоритмы не достигают лучшей

сложности, чем алгоритмы, управляемые сообщениями. Действительно, если A -

асинхронный алгоритм, то управляемый сообщениями алгоритм B может быть

построен следующим образом. После инициализации и после получения любого

сообщения B посылает максимальное количество сообщений, которое можно

послать в A, не получая при этом сообщений, и только затем получает

следующее сообщение. Алгоритм B не только управляется сообщениями, но кроме

того, каждое вычисление B является возможным вычислением A (возможно, при

довольно пессимистическом распределении задержек передачи сообщений).

Три последних предположения устраняют недетерминизм системы. При этих

предположениях каждое вычисление, начинающееся с данной начальной

конфигурации, содержит одно и то же множество событий.

В этом разделе через s = (s1, ..., sN), t и т.п. обозначаются

последовательности различных идентификаторов процессов. Множество всех

таких последовательностей обозначено через D, т.е. D = {(s1, ..., sk): si ?

P и i ? j ? si ? sj}. Длина последовательности s обозначается через

len(s), а конкатенация последовательностей s и t обозначается st.

Циклическим сдвигом s называется последовательность s's'', где s = s''s' ;

она имеет вид si, ..., sN, s1, ..., si-1. Через CS(s) (cyclic shift -

циклический сдвиг) обозначено множество циклических сдвигов s, и

естественно |CS(s)| = len(s).

Говорят, что кольцо помечено последовательностью (s1, ..., sN), если

идентификаторы процессов с s1 по sN расположены на кольце (размера N) в

таком порядке. Кольцо, помеченное s также называют s-кольцом. Если t -

циклический сдвиг s, то t-кольцо совпадает с s-кольцом.

С каждым сообщением, посылаемым в алгоритме, свяжем последовательность

идентификаторов процессов, называемую следом (trace) сообщения. Если

сообщение m было послано процессом p до того, как p получил какое-либо

сообщение, след m равен (p). Если m было послано процессом p после того,

как он получил сообщение со следом s = (s1, ..., sk), тогда след m равен

(s1, ..., sk, p). Сообщение со следом s называется s-сообщением. Нижняя

граница будет выведена из свойств множества всех следов сообщений, которые

могут быть посланы алгоритмом.

Пусть E - подмножество D. Множество E полно (exhaustive), если

E префиксно замкнуто, т.е. tu ? E ? t ? E ; и

E циклически покрывает D, т.е. ? s ? D: CS(s) ? E ? ?.

Далее будет показано, что множество всех следов алгоритма полно. Для того,

чтобы вывести из этого факта нижнюю границу сложности алгоритма, определены

две меры множества E. Последовательность t является последовательной

цепочкой идентификаторов в s-кольце, если t - префикс какого-либо r (

CS(s). Обозначим через M(s,E) количество последовательностей в E, которые

удовлетворяют этому условию в s-кольце, а через Mk(s,E) - количество таких

цепочек длины k;

M(s,E) = |{ t ? E : t - префикс некоторого r ? CS(s) }| и

Mk(s,E) = |{ t ? E : t - префикс некоторого r ? CS(s) и len(t) = k}|.

В дальнейшем, допустим, что A - алгоритм, который вычисляет наименьший

идентификатор, а EA - множество последовательностей s таких, что s-

сообщение посылается, когда алгоритм A выполняется на s-кольце.

Лемма 7.10 Если последовательности t и u содержат подстроку s и s-

сообщение посылается, когда алгоритм A выполняется на t-кольце, то s-

сообщение также посылается, когда A выполняется на u-кольце.

Доказательство. Посылка процессом sk s-сообщения, где s = (s1, ..., sk),

каузально зависит только от процессов с s1 по sk. Их начальное состояние в

u-кольце совпадает с состоянием в t-кольце (напоминаем, что размер кольца

неизвестен), и следовательно совокупность событий, предшествующих посылке

сообщения, также выполнима и в u-кольце.

Лемма 7.11 EA - полное множество.

Доказательство. Чтобы показать, что EA циклически замкнуто, заметим, что

если A посылает s-сообщение при выполнении на s-кольце, тогда для любого

префикса t последовательности s A сначала посылает t-сообщение на s-

кольце. По Лемме 7.10 A посылает t-сообщение на t-кольце, следовательно t ?

EA.

Чтобы показать, что EA циклически покрывает D, рассмотрим вычисление A на s-

кольце. Хотя бы один процесс выбирает наименьший идентификатор, откуда

следует (аналогично доказательству Теоремы 6.11), что этот процесс получил

сообщение со следом длины len(s). Этот след является циклическим сдвигом s

и принадлежит E.

Лемма 7.12 В вычислении на s-кольце алгоритм A посылает не менее M(s,EA)

сообщений.

Доказательство. Пусть t ? EA - префикс циклического сдвига r

последовательности s. Из определения EA, A посылает t-сообщение в

вычислении на t-кольце, а следовательно также и на r-кольце, которое

совпадает с s-кольцом. Отсюда, для каждого t из {t ? E: t - префикс

некоторого r ? CS(s)} в вычислении на s-кольце посылается хотя бы одно t-

сообщение, что доказывает, что количество сообщений в таком вычислении

составляет не менее M(s,E).

Для конечного множества I идентификаторов процессов обозначим через Per(I)

множество всех перестановок I. Обозначим через aveA(I) среднее количество

сообщений, используемых A во всех кольцах, помеченных идентификаторами из

I, а через worA(I) - количество сообщений в наихудшем случае. Из предыдущей

леммы следует, что если I содержит N элементов, то

[pic]; и

[pic].

Теперь нижнюю границу можно вывести путем анализа произвольных полных

множеств.

Теорема 7.13 Средняя сложность однонаправленного алгоритма поиска

наименьшего идентификатора составляет не менее N*?N.

Доказательство. Усредняя по всем начальным конфигурациям, помеченным

множеством I, мы находим

[pic]

Зафиксируем k и отметим, что для любого s ( Per(I) существует N префиксов

циклических сдвигов s длины k. N! перестановок в Per(I) увеличивают

количество таких префиксов до N*N!. Их можно сгруппировать в N*N!/k групп,

каждая из которых содержит по k циклических сдвигов одной

последовательности. Т.к. EA циклически покрывает D, EA пересекает каждую

группу, следовательно [pic].

Отсюда следует[pic][pic].

Этот результат означает, что алгоритм Чанга-Робертса оптимален, когда

рассматривается средний случай. Сложность в наихудшем случае больше или

равна сложности в среднем случае, откуда следует, что наилучшая достижимая

сложность для наихудшего случая находится между N*?N ? 0.69N logN и ?

0.356N logN.

Доказательство, данное в этом разделе, в значительной степени полагается на

предположения о том, что кольцо однонаправленное и его размер неизвестен.

Нижняя граница, равная 0.5N*?N была доказана Bodlaender [Bod88] для средней

сложности алгоритмов выбора на двунаправленных кольцах, где размер кольца

неизвестен. Чтобы устранить недетерминизм из двунаправленного кольца,

рассматриваются вычисления, в которых каждый процесс начинается в одно и то

же время и все сообщения имеют одинаковую задержку передачи. Для случая,

когда размер кольца известен, Bodlaender [Bod91a] вывел нижнюю границу,

равную 0.5N logN для однонаправленных колец и (1/4-?)N*?N для

двунаправленных колец (обе границы для среднего случая).

В итоге оказывается, что сложность выбора на кольце не чувствительна

практически ко всем предположениям. Независимо от того, известен или нет

размер кольца, однонаправленное оно или двунаправленное, рассматривается ли

средний или наихудший случай, - в любом случае сложность составляет

?(N logN). Существенно важно, что кольцо асинхронно; для сетей, где

доступно глобальное время, сложность сообщений ниже, как будет показано в

Главе 11.

Т.к. лидер может быть выбран за одно выполнение децентрализованного

волнового алгоритма, из нижней границы для выбора следует нижняя граница

для волновых алгоритмов.

Заключение 7.14 Любой децентрализованный волновой алгоритм для кольцевых

сетей передает не менее ?(N logN) сообщений, как в среднем, так и в

наихудшем случае.

[pic]

Рис.7.8

7.3 Произвольные Сети

Теперь изучим проблему выбора для сетей произвольной, неизвестной

топологии без знания о соседях. Нижняя граница ?(N logN+(E() сообщений

будет показана ниже. Доказательство объединяет идею Теоремы 6.6 и

результаты предыдущего подраздела. В Подразделе 7.3.1 будет представлен

простой алгоритм, который имеет низкую сложность по времени, но высокую

сложность по сообщениям в худшем случае. В Подразделе 7.3.2 будет

представлен оптимальный алгоритм для худшего случая.

Теорема 7.15 Любой сравнительный алгоритма выбора для произвольных сетей

имеет (в худшем и среднем случае) сложность по сообщения по крайней мере

?(Nlog N + (E().

Рисунок 7.8 вычисление с двумя ЛИДЕРАМИ.

Доказательство. Граница ?(N log N + (E() является нижней, потому что

произвольные сети включают кольца, для которых нижняя граница ?(N logN).

Чтобы видеть, что (E( сообщений является нижней границей, даже в лучшем из

всех вычислений, предположим что, алгоритм выбора имеет вычисление С на

сети G, в котором обменивается менее чем (E( сообщений ; см. Рисунок 7.8.

Построим сеть G ', соединяя две копии G одним ребром между узлами,

связанными ребром , которое не используется в C. Тождественные части сети

имеют тот же самый относительный порядок как и в G. Вычисление С может

моделироваться одновременно в обеих частях G ', выдавая вычисление, в

котором два процесса станут избранными. (

Заключение 7.16 Децентрализованный волновой алгоритм для произвольных сетей

без знания о соседях имеет сложность по сообщения по крайней мере ?(NlogN +

(E().

7.3.1 Вырождение и Быстрый Алгоритм

Алгоритм для выбора лидера может быть получен из произвольного

централизованного волнового алгоритма применением преобразования

называемого вырождением. В полученном алгоритме выбора каждый инициатор

начинает отдельную волну; все сообщения волны, начатой процессом p должны

быть помечены идентификатором p, чтобы отличить их от сообщений различных

волн. Алгоритм гарантирует, что, независимо от того, сколько волн начато,

только одна волна будет бежать к решению, а именно, волна самого маленького

инициатора. Все другие волны будут прерваны прежде, чем решение может иметь

место.

Для волнового алгоритма A, алгоритм выбора Ex(A) следующий. В каждый момент

времени каждый процесс активен не более чем в одной волне ; эта волна -

текущая активная волна, обозначенная caw , с начальным значением udef.

Инициаторы выбора действуют, как будто они начинают волну и присваивают caw

их собственный идентификатор . Если сообщение некоторой волны, скажем

волны, которую начал q, достигает p, p обрабатывает сообщение следующим

образом.

var cawp : P init udef ; (* текущая активная волна *)

recp : integer init 0 ; (* число полученных (tok, cawp (

*)

fatherp : P init udef ; (* отец в волне cawp *)

lrecp : integer init 0 ; (* число полученных (ldr, . ( *)

winp : P init udef; (* идентификатор лидера*)

begin if p is initiator then

begin cawp := p;

forall q ( Neighp do send ( tok, p( to q

end;

while lrecp < #Neighp do

begin receive msg from q ;

if msg = ( ldr, r ( then

begin if lrecp = 0 then

forall q (. Neighp do send ( ldr,

r ( to q ;

lrecp := lrecp + 1 ; winp := r

end

else (*—9Y(=ЈS?У'ѕ?Ў.??Ѕ2~>3K cawp сообщение

игнорируется*)

end

end;

if winp = p then statep :== leader else statep :== lost

end

Алгоритм 7.9 Вырождение примененное к алгоритму эха.

Если q> cawp, сообщение просто игнорируется, эффективно приводя волну q к

неудаче. Если с q = cawp, с сообщением поступают в соответствии с волновым

алгоритмом. Если q < cawp или cawp = udef, p присоединяется к выполнению

волны q, повторно присваивая переменным их начальные значения и

присваивая cawp значение q. Когда волна, начатая q выполняет событие

решения (в большинстве волновых алгоритмов, это решение всегда имеет место

в q), q будет избран. Если волновой алгоритм такой, что решающий узел не

обязательно равен инициатору, то решающий узел информирует инициатора через

дерево охватов(остовное дерево) как определено в Lemma 6.3. При этом

требуется не более N - 1 сообщений; мы игнорируем их в следующей теореме.

Теорема 7.17. Если А - централизованный волновой алгоритм, использующий М

сообщений на одну волну, алгоритм Ex(A), выбирает лидера использую не более

NM сообщений.

Доказательство. Пусть p0 самый маленький инициатор. К волне, начатой p0

немедленно присоединяются все процессы, которые получают сообщение этой

волны, и каждый процесс заканчивает эту волну, потому что нет волны с

меньшим идентификатором, для которой процесс прервал бы выполнение волны

p0. Следовательно, волна p0 бежит к завершению, решение будет иметь место,

и p0 становится лидером.

Если p не инициатор, никакая волна с идентификатором p не начнется,

следовательно p не станет лидером. Если p ( p0 - инициатор, волна с

идентификатором p будет начата, но решению в этой волне будет

предшествовать событие посылки от p0 (для этой волны) , или имееть место в

p0 (Lemma 6.4). Так как p0 никогда не выполняет событие посылки или

внутреннее событие волны с идентификатором p, такое решение не имеет

место, и p не избран.

Не более N волн начаты, и каждая волна использует по крайней мере М

сообщений, что приводит к полной сложности к NM. (

Более тонким вопросом является оценка сложности по времени алгоритма Ex(A).

Во многих случаях это будет величина того же порядока , что и сложность по

времени алгоритма A, но в некоторых неудачных случаях, может случиться, что

инициатор с самым маленьким идентификатором начинает волну очень поздно. В

общем случае можно показать сложность по времени O (Nt) (где t - сложность

по времени волнового алгоритма ), потому что в пределах t единиц времени

после того, как инициатор p начинает волну, волна p приходит к решению или

начинается другая волна.

Если вырождение применяется к кольцевому алгоритму, получаем алгоритм Chang-

Poberts; см. Упражнение 7.9. Алгоритм 7.9 является алгоритмом выбора

полученным из алгоритма эха. Чтобы упростить описание, принимается что

udef > q для всех q( P. При исследовании кода, читатель должен обратить

внимание, что после получения сообщения (tok, r( с r < cawpp, оператор If

с условием r = cawp также выполняется, вследствие более раннего

присваивания cawp. Когда выбирается процесс p (получает (tok, p( от

каждого соседа), p посылает сообщение (ldr, p( всем процессам, сообщая им,

что p - лидер и заставляя их закончить алгоритм.

7.3.2 Алгоритм Gallager-Humblet-Spira

Проблема выбора в произвольных сетях тесно связана с проблемой вычисления

дерева охватов с децентрализованным алгоритмом, как выдно из следующего

рассуждения. Пусть CE сложность по сообщениям проблемы выбора и CТ

сложность вычисления дерева охватов. Теорема 7.2 подразумевает, что

CE(CT+O(N), и если лидер доступен, дерево охватов, может быть вычислено

используя 2((( сообщений в алгоритме эха, который подразумевает что CT ( CE

+ 2(((. Нижняя граница CE (теорема 7.15) подразумевает, что две проблемы

имеют одинаковый порядок сдожности, а именно, что они требуют по крайней

мере ?(N log N + E) сообщений.

Этот подраздел представляет Gallager-Humblet-Spira (GHS), алгоритм для

вычисления (минимального) дерева охватов, используя 2((( + 5N log N

сообщений. Это показывает, что CE и CТ величины порядка ( (N log N + E).

Этот алгоритм был опубликован в [GHS83]. Алгоритм может быть легко изменен

(как будет показано в конце этого подраздела) чтобы выбрать лидера в ходе

вычисления, так, чтобы отдельный выбор как показано в выше не был

необходим.

GHS алгоритм полагается на следующие предположения.

(1) Каждое ребро e имеет уникальный вес w (e). Предположим здесь, что w (e)

- реальное число, но целые числа также возможны как веса ребер.

Если уникальные веса ребер не доступны априоре, каждому краю можно давать

вес, который сформирован из меньшего из двух первых идентификаторов узлов,

связанных с ребром. Вычисление веса края таким образом требует, чтобы узел

знал идентификаторы соседей, что требует дополнительно 2((( сообщений при

инициализации алгоритма.

(2) Все узлы первоначально находятся в спящем состоянии и просыпаются

прежде, чем они начинают выполнение алгоритма. Некоторые узлы просыпаются

спонтанно (если выполнение алгоритма вызвано обстоятельствами,

встречающимися в этих узлах), другие могут получать сообщение алгоритма, в

то время как они все еще спят. В последнем случае узел получающий сообщение

сначала выполняет локалбную процедуру инициализации, а затем обрабатывает

сообщение.

Минимальное дерево охватов. Пусть G = (V, E) взвешенный граф, где w {e)

обозначает вес ребра e. Вес дерева охватов T графа G равняется сумме весов

N-1 ребер, содержащихся в T, и T называется минимальным деревом охватов,

или MST, (иногда минимальным по весу охватывающим деревом) если никакое

дерево не имеет меньший вес чем T. В этом подразделе предполагаем, что

каждое ребро имеет уникальный вес, то есть, различные ребра имеют

различные веса, и это - известный факт что в этом случае имеется уникальное

минимальное дерево охватов.

Утверждение 7.18 Если все веса ребер различны, то существует только одно

MST.

Доказательство. Предположим обратное, т.е. что T1 и T2 (где T1 ( T2) -

минимальные деревья охватов. Пусть e ребро с самым маленьким весом,

который находится в одном из деревьев, но не в обоих; такой край существует

потому что T1 ( T2. Предположим, без потери общности, что e находится в T1,

но не в T2. Граф T2 ( {e} содержит цикл, и поскольку T1 не содержит никакой

цикл, по крайней мере одно ребро цикла, скажем e', не принадлежит T1. Выбор

e подразумевает что w (e) < w (e '), но тогда дерево T2 ( {e} \ {e '}

имеет меньший вес чем T2, который противоречит тому, что T2 - MST. (

Утверждение 7.18 - важное средство распределенного построения

минимального дерева охватов, потому что не нужно делать

выбор(распределенно) из множества законных ответов. Напротив каждый узел,

который локально выбирает ребра, которые принадлежат любому минимальному

дереву охватов таким образом, вносит вклад в строительство глобально

уникального MST.

Все алгоритмы, для вычисления минимальное дерево охватов основаны на

понятии фрагмента, который является поддеревом MST. Ребро e - исходящее

ребро фрагмента F, если один конец e находится в F, и другой - нет.

Алгоритмы начинают с фрагментов, состоящих из единственного узла и

увеличивают фрагменты, пока MST не полон, полагаясь на следующее

наблюдение.

Утверждение 7.19 Если F - фрагмент и e - наименьшее по весу исходящее ребро

F, то F ( {e} - фрагмент

Доказательство. Предположите, что F ( {e} - не часть MST; тогда е

формирует цикл с некоторыми ребрами MST, и одно из ребер MST в этом цикле,

скажем f, - исходящее ребро F. Из выбора e - w (e) < w (f), но тогда удаляя

f из MST и вставляя e получим дерево с меньшим весом чем MST, что является

противоречием. (

Известные последовательные алгоритмы для вычисления MST - алгоритмы Prim и

Kruskal. Алгоритм Prim [CLR90, Раздел 24.2] начинается с одного фрагмента и

увеличивает его на каждом шаге включая исходящее ребротекущего фрагмента с

наименьшим весом. Алгоритм Kruskal [CLR90, Раздел 24.2] начинается с

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18