Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 60
Текст из файла (страница 60)
По каждому ребру дерева передаются два сообщения tok, одно сообщение vis (от родительской вершины к ее преемнику) и одно сообщение аск (кродительской вершине от ее преемника). Следовательно, происходит обмен 4|£]сообщениями.□Отправление сообщения vis тем соседям, которым процесс собирается передать маркер, может быть опущено. Это улучшение (оно не приведено в алгоритме 6.14) позволяет сэкономить по два сообщения на каждом ребре дерева и,следовательно, сокращает сложность по числу обменов сообщениями на 2 N —2сообщения.var usedp[q\fat herрmrsp: boolin it false for each q € Neighp ;(* Указывает, отправлял ли p маркер процессу q *): process in it u d e f;: process in it u d e f;Только для инициатора, выполнить один раз:b egin fatherр := р ; choose q € Neighp ;forall r e Neighp do send vis to r ;usedp[q] := true ; mrsp := q ; send to k to qendДля каждого процесса после получения vis от q(,\b egin usedp[qo\ := true ;if <7o = mrsp th en (* Истолковывать как сообщение tok *)forward tok m essage as upon receipt of tok messageendАлгоритм 6.15.
Алгоритм Сидон поиска в глубину (Часть 1)Решение Сидона. В алгоритме Сидона [53], в отличие от алгоритма Авербаха, не отправляются сообщения аск, и за счет этого улучшается сложность повремени. В модифицированном алгоритме Сидона маркер отправляется немедленно, т. е. без той задержки на две единицы времени, которая введена в алгоритме Авербаха для ожидания подтверждений. Тот же самый алгоритм былпредложен Лакшмананом и др. [123]. В алгоритме Сидона возможно возникновение следующей ситуации.
В процессе р уже побывал маркер, и этот процессуже отправил сообщение vis своему соседу г. Позднее маркер достается процессу г, но в тот момент, когда г получает маркер, сообщение vis от р еще не6.4. Сложность по времени: поиск в глубину227Для каждого процесса после получения tok от qо:b egin if mrsp A udef and mrsp / qo(* Это стягивающее ребро, истолковывать как сообщение vis *)th en usedp[qo\ := trueelse(* Поступать, как в предыдущем алгоритме *)b egin if fatherp = udef th enb egin fatherp := <70 ;forall t € Neighp \ {fatherp} dosend vis to ren d ;if p — инициатор and V<7 € Neighp : usedp[q\th en decidee ls e if 3<7 € Neighp : (q / fatherp A ->usedp[q\)then b egin if fatherp / <70 A ->usedP[qo]th en q := <70e ls e choose q € Neighp \ {fatherp}with -lusedplq] ;usedp[q] := true ; mrsp := q ;send tok to qendelse b egin usedp[fatherp] := true ;send tok to fatherpen dendendАлгоритм 6.16.Алгоритм Сидона поиск в глубину (Часть 2)достигло г.
В таком случае г может передать маркер процессу р, отправляя его,таким образом, по стягивающему ребру. (Обратите внимание на то, как сообщения аск в алгоритме Авербаха предотвращают подобный сценарий развитиясобытий.)Чтобы справиться с такой ситуацией, процесс р записывает (в переменнуюmrsp) тех соседей, которым он в последнюю очередь отправлял маркер. Когдамаркер проходит только по ребрам дерева, процесс р получает в очередной размаркер от того самого соседа mrsp. А в том сценарии, который был описан выше,р получает сообщение tok от другого соседа, а именно от г; в таком случае саммаркер просто игнорируется, но р помечает ребро гр как использованное,точно так же, как если бы было получено сообщение vis от г.
Процесс г получаетот р сообщение vis, после того как он передал маркер процессу р, т. е. г получаетсообщение vis от своего соседа mrsr. В этом случае процесс г ведет себя так,как если бы он вообще не передавал маркер процессу р, а именно, г выбираетследующего соседа и передает ему маркер (см. алгоритм 6.15/6.16).Теорема 6.35. Алгоритм Сидона (алгоритм 6.15/6.16) строит DFS дерево за 2N - 2 единицы времени, используя 4|£| обменов сообщениями.228Гл. 6.Волновые алгоритмы и алгоритмы обходаД о к а з а т е л ь с т в о . И вновь перемещение маркера будет подобно томудвижению, которое задается алгоритмом 6.13. Либо его передача по стягивающимребрам отменяется (как и в алгоритме 6.14), либо маркер идет навстречу сообщению vis по стягивающему ребру.
В последнем случае процесс, получающийсообщение vis, продолжает передавать маркер, что вызывает такой же эффект,как если бы маркер немедленно вернулся обратно по стягивающему ребру.Промежуток времени между двумя последовательными передачами маркерапо ребру дерева ограничен одной единицей. Если маркер отправлен по ребру дерева процессу р в момент времени t, то к моменту времени t все сообщения visот тех соседей q процесса р, в которых маркер побывал ранее, были отправлены,и, следовательно, эти сообщения получены самое позднее в момент времени t + 1.Так что, хотя процесс р мог к моменту времени t + 1 передавать маркер по стягивающему ребру несколько раз, самое позднее в момент / + 1 он уже исправилвсе эти ошибки и передал маркер по ребру дерева.
Коль скоро необходимо совершить 2N —2 прохождений по ребрам дерева, наш алгоритм завершает работуспустя 2N —2 единиц времени.По каждому каналу передаются не более двух сообщений vis и двух сообщений tok, и это служит обоснованием тому, что верхняя оценка числа обменовсообщениями равна 4|£|.□Во многих случаях наш алгоритм будет отправлять меньшее количество сообщений, нежели алгоритм Авербаха. Проведенный анализ числа сообщений в алгоритме Сидона проведен в предположении о наихудшем случае, а именно когдамаркер передается по стягивающим ребрам в обоих направлениях.
Можно ожидать, что сообщения vis позволят с успехом предотвратить многие нежелательныепередачи, и в таком случае по каждому каналу может передаваться только дваили три сообщения.Сидон отмечает, что, хотя в алгоритме маркер может передаваться тем вершинам, в которых он уже побывал, сам алгоритм имеет лучшую сложность повремени (равно как и по числу обменов сообщениями), нежели алгоритм 6.14,и это приводит к предотвращению таких нежелательных передач. Это наводит намысль о том, что для исправления ненужных действий требуется меньше времении сообщений, нежели для предотвращения этих действий.
Сидон оставил открытым вопрос о том, существует ли алгоритм поиска в глубину, который достигаеттой же сложности по числу обменов сообщениями, что и классический алгоритм,т. е. 2\Е\, и при этом укладывается в 0(N) единиц времени.6.4.3. Поиск в глубину с учетом сведений о соседяхЕсли процессы осведомлены об отличительных признаках своих соседей, топередачу маркера по стягивающим ребрам можно предотвратить, включив список пройденных вершин в состав маркера. Процесс р, получив маркер, в который вложен список L, не будет передавать маркер процессам из L. Переменнуюusedp[q] можно изъять, потому что если процесс р ранее уже передавал маркерпроцессу q, то q <Е L (см.
алгоритм 6.17).6.5. Прочие вопросыvar fatherp: процесс229in itu d e f;Только для инициатора, выполнить один раз:begin fatherp := р ; choose q € Neighp-,send (tlist, {p}) to qendДля каждого процесса после получения (tlist, L) от q0:begin if fatherp = udef then fatherp := qo ;if 3q € Neighp \ Lthen begin choose q € Neighp \ L ;send (tlist, L U {p }) to qendelse if p is initiatorthen decideelse send (tlist, L U { p } ) to fatherpendАлгоритм 6.17. Поиск в глубину с учетом сведений о соседях.Теорема 6.36. DFS-алгоритм с учетом сведений о соседях является алгоритмом обхода, вычисляющим дерево обхода в глубину с использованием2N - 2 обменов сообщениями за 2N —2 единиц времени.Битовая сложность этого алгоритма велика: если w — это число битов, необходимых для задания отличительного признака, то для списка L может потребоваться до Nw битов (см.
упражнение 6.14).6.5. Прочие вопросы6.5.1. Обзор волновых алгоритмовВ таблице 6.18 приведен список волновых алгоритмов, рассмотренных в этойглаве.В колонке, озаглавленной «номер», приведен тот номер алгоритма, которыйиспользуется для его обозначения в этой главе; в колонке, озаглавленной «Ц/Д»указано, является ли алгоритм централизованным (Ц) или децентрализованным(D); в колонке, помеченной «О», указано, является ли данный алгоритм алгоритмом обхода; в колонке, озаглавленной «С», приведена сложность алгоритмапо числу обменов сообщениями; в колонке, озаглавленной «В», приведена сложность алгоритма по времени. Здесь N обозначает количество процессов, |£| —количество каналов, a D — диаметр сети (измеряемый по числу переходов).Сложность образования волны в сетях с наиболее распространенной топологией существенно зависит от того, требуется ли, чтобы алгоритм был централизованным или децентрализованным.
В таблице 6.19 перечислены оценки сложности по числу сообщений для централизованных и децентрализованных волновыхалгоритмов для колец, произвольных сетей и деревьев. Подобным же образом230Гл. 6.Алгоритм|| НомерТопология |Ц /Д |оL L Jпроизвольная д§6.6.4.
Алгоритмы поиска впроизвольная6.136.14произвольная6.15/6.16 произвольная6.17 произвольнаянетьц6.8§6.6 .3 . Алгоритмы обходаПоследовательного6.9кликацопросаТора6.10торцгиперкубГиперкуба6.11цТарри6.12произвольная цКлассическийАвербахаСидонас учетомсоседейСSection 6.6.2. Общие алгоритмыNNкольцоелц даN0(D)дерево6.2д нетпроизвольная ц нет т6.40(N)2клика6.5ц нет 2 N - 2произвольная д нет 2D\E\2D6.66.7кликад нет N( N- 1) 2V/КольцевойДревесныйЭхаОпросаФазовыйФазовыйна кликахФиннаВолновые алгоритмы и алгоритмы обхода0(D)да 2 N - 2 2 N - 2дададаNN2\Е\NN2\Е\глубину2\Е\2\Е\ц дац нет 4\Е\ iN —2ц нет 4\Е\ 2 N - 2ц да 2 N - 2 2 N - 2Примечание: фазовый алгоритм (6.6) и алгоритм Финна (6.8) пригодны для ориентированных сетей.Таблица 6.18.Волновые алгоритмы, рассмотренные в настоящей главеможно проанализировать зависимость сложности от других параметров, такихкак осведомленность о соседях или восприятие направления (см.
§Б.4.3).6.5.2. Вычисление суммКак было показано в §6.1.5, при помощи одиночной волны можно вычислятьточную нижнюю грань по входным данным всех процессов. Вычисление точнойнижней грани можно применять для выполнения коммутативных, ассоциативныхи идемпотентных операций над входными данными, наподобие вычисления минимума, максимума, и т.
п. (см. следствие 6.14). Однако большое число функций,наподобие суммирования, так вычислять нельзя, потому что они не идемпотентны.Суммирование можно применять для подсчета количества процессов, обладающих определенными свойствами (полагая, что на вход подается 1 , если процессобладает нужным свойством, и 0 в противном случае), но результаты этого параграфа можно также применять и для других операций, являющихся коммутативными и ассоциативными, таких как произведение целых чисел или объединениемультимножеств.6.5. Прочие вопросыТопологияЦ /ДКольцоЦДПроизвольная ЦДеревоДЦДСложность231СсылкаN0(7Vlog,/V)алгоритм 6.1алгоритм 7.7алгоритм 6.4т0 ( N \ o g N + |£ |) раздел 7.5.32{N — 1)алгоритм 6.4O(N)алгоритм 6.2Таблица 6.19.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
