Реферат: Распределенные алгоритмы
end
else (* сообщение á tok, rñ *)
begin if r < cawp then (* Переинициализируем алгоритм*)
begin cawp := r , recp := 0 , fatherp :== q ;
forall sÎ Neighp , s ¹ q
do send á tok, r ñ to s
end;
if r = cawp then
if cawp = p
then forall s Î Neighp do send á ldr, p ñ to s
else send á tok, cawpñ to fatherp
end
(* если r > 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. o
Более тонким вопросом является оценка сложности по времени алгоритма 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½E½ сообщений в алгоритме эха, который подразумевает что CT £ CE + 2½E½. Нижняя граница CE (теорема 7.15) подразумевает, что две проблемы имеют одинаковый порядок сдожности, а именно, что они требуют по крайней мере Ω(N log N + E) сообщений.
Этот подраздел представляет Gallager-Humblet-Spira (GHS), алгоритм для вычисления (минимального) дерева охватов, используя 2½E½ + 5N log N сообщений. Это показывает, что CE и CТ величины порядка q (N log N + E). Этот алгоритм был опубликован в [GHS83]. Алгоритм может быть легко изменен (как будет показано в конце этого подраздела) чтобы выбрать лидера в ходе вычисления, так, чтобы отдельный выбор как показано в выше не был необходим.
GHS алгоритм полагается на следующие предположения.
(1) Каждое ребро e имеет уникальный вес w (e). Предположим здесь, что w (e) - реальное число, но целые числа также возможны как веса ребер.
Если уникальные веса ребер не доступны априоре, каждому краю можно давать вес, который сформирован из меньшего из двух первых идентификаторов узлов, связанных с ребром. Вычисление веса края таким образом требует, чтобы узел знал идентификаторы соседей, что требует дополнительно 2½E½ сообщений при инициализации алгоритма.
(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. o
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
