Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 61
Текст из файла (страница 61)
Когдамаркер проходит только по ребрам дерева, процесс p получает в очередной размаркер от того самого соседа mrsp . А в том сценарии, который был описан выше,p получает сообщение tok от другого соседа, а именно от r; в таком случае саммаркер просто игнорируется, но p помечает ребро rp как использованное,точно так же, как если бы было получено сообщение vis от r.
Процесс r получаетот p сообщение vis, после того как он передал маркер процессу p, т. е. r получаетсообщение vis от своего соседа mrsr . В этом случае процесс r ведет себя так,как если бы он вообще не передавал маркер процессу p, а именно, r выбираетследующего соседа и передает ему маркер (см.
алгоритм 6.15 /6.16).Теорема 6.35. Алгоритм Сидона (алгоритм 6.15/6.16) строит DFS дерево за 2N − 2 единицы времени, используя 4|E| обменов сообщениями.228Гл. 6.6.5. Прочие вопросыВолновые алгоритмы и алгоритмы обходаД о к а з а т е л ь с т в о. И вновь перемещение маркера будет подобно томудвижению, которое задается алгоритмом 6.13.
Либо его передача по стягивающимребрам отменяется (как и в алгоритме 6.14), либо маркер идет навстречу сообщению vis по стягивающему ребру. В последнем случае процесс, получающийсообщение vis, продолжает передавать маркер, что вызывает такой же эффект,как если бы маркер немедленно вернулся обратно по стягивающему ребру.Промежуток времени между двумя последовательными передачами маркерапо ребру дерева ограничен одной единицей. Если маркер отправлен по ребру дерева процессу p в момент времени t, то к моменту времени t все сообщения visот тех соседей q процесса p, в которых маркер побывал ранее, были отправлены,и, следовательно, эти сообщения получены самое позднее в момент времени t + 1.Так что, хотя процесс p мог к моменту времени t + 1 передавать маркер по стягивающему ребру несколько раз, самое позднее в момент t + 1 он уже исправилвсе эти ошибки и передал маркер по ребру дерева.
Коль скоро необходимо совершить 2N − 2 прохождений по ребрам дерева, наш алгоритм завершает работуспустя 2N − 2 единиц времени.По каждому каналу передаются не более двух сообщений vis и двух сообщений tok, и это служит обоснованием тому, что верхняя оценка числа обменовсообщениями равна 4|E|.Во многих случаях наш алгоритм будет отправлять меньшее количество сообщений, нежели алгоритм Авербаха.
Проведенный анализ числа сообщений в алгоритме Сидона проведен в предположении о наихудшем случае, а именно когдамаркер передается по стягивающим ребрам в обоих направлениях. Можно ожидать, что сообщения vis позволят с успехом предотвратить многие нежелательныепередачи, и в таком случае по каждому каналу может передаваться только дваили три сообщения.Сидон отмечает, что, хотя в алгоритме маркер может передаваться тем вершинам, в которых он уже побывал, сам алгоритм имеет лучшую сложность повремени (равно как и по числу обменов сообщениями), нежели алгоритм 6.14,и это приводит к предотвращению таких нежелательных передач.
Это наводит намысль о том, что для исправления ненужных действий требуется меньше времении сообщений, нежели для предотвращения этих действий. Сидон оставил открытым вопрос о том, существует ли алгоритм поиска в глубину, который достигаеттой же сложности по числу обменов сообщениями, что и классический алгоритм,т. е. 2|E|, и при этом укладывается в O(N) единиц времени.6.4.3.
Поиск в глубину с учетом сведений о соседяхЕсли процессы осведомлены об отличительных признаках своих соседей, топередачу маркера по стягивающим ребрам можно предотвратить, включив список пройденных вершин в состав маркера. Процесс p, получив маркер, в который вложен список L, не будет передавать маркер процессам из L. Переменнуюusedp [q] можно изъять, потому что если процесс p ранее уже передавал маркерпроцессу q, то q ∈ L (см. алгоритм 6.17).var fatherp: процесс229initudef ;Только для инициатора, выполнить один раз:begin fatherp := p ; choose q ∈ Neighp ;send htlist, {p}i to qendДля каждого процесса после получения htlist, Li от q0 :begin if fatherp = udef then fatherp := q0 ;if ∃q ∈ Neighp \ Lthen begin choose q ∈ Neighp \ L ;send htlist, L ∪ {p}i to qendelse if p is initiatorthen decideelse send htlist, L ∪ {p}i 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 обозначает количество процессов, |E| —количество каналов, а D — диаметр сети (измеряемый по числу переходов).Сложность образования волны в сетях с наиболее распространенной топологией существенно зависит от того, требуется ли, чтобы алгоритм был централизованным или децентрализованным.
В таблице 6.19 перечислены оценки сложности по числу сообщений для централизованных и децентрализованных волновыхалгоритмов для колец, произвольных сетей и деревьев. Подобным же образом230Гл. 6.АлгоритмКольцевойДревесныйЭхаОпросаФазовыйФазовыйна кликахФиннаНомерТопология Ц/Д ОСВSection 6.6.2. Общие алгоритмы6.1кольцоЦ даNN6.2деревоД нетNO(D)6.4 произвольная Ц нет 2|E|O(N)6.5кликаЦ нет 2N − 226.6 произвольная Д нет 2D|E|2D6.7кликаД нетN(N − 1) 26.8произвольная Д нет 6 4N|E| O(D)§ 6.6.3.
Алгоритмы обходаПоследовательного6.9кликаЦопросаТора6.10торЦГиперкуба6.11гиперкубЦТарри6.12 произвольная ЦКлассическийАвербахаСидонас учетомсоседей6.5. Прочие вопросыВолновые алгоритмы и алгоритмы обхода§ 6.6.4. Алгоритмы поиска в6.13 произвольная6.14 произвольная6.15/6.16произвольная6.17 произвольнаяда 2N − 2 2N − 2дададаNN2|E|NN2|E|глубинуЦ да 2|E|2|E|Ц нет 4|E| 4N − 2Ц нет 4|E| 2N − 2Ц да 2N − 2 2N − 2Примечание: фазовый алгоритм (6.6) и алгоритм Финна (6.8) пригодны для ориентированных сетей.Таблица 6.18. Волновые алгоритмы, рассмотренные в настоящей главеможно проанализировать зависимость сложности от других параметров, такихкак осведомленность о соседях или восприятие направления (см.
§ Б.4.3).6.5.2. Вычисление суммКак было показано в § 6.1.5, при помощи одиночной волны можно вычислятьточную нижнюю грань по входным данным всех процессов. Вычисление точнойнижней грани можно применять для выполнения коммутативных, ассоциативныхи идемпотентных операций над входными данными, наподобие вычисления минимума, максимума, и т. п.
(см. следствие 6.14). Однако большое число функций,наподобие суммирования, так вычислять нельзя, потому что они не идемпотентны.Суммирование можно применять для подсчета количества процессов, обладающих определенными свойствами (полагая, что на вход подается 1, если процессобладает нужным свойством, и 0 в противном случае), но результаты этого параграфа можно также применять и для других операций, являющихся коммутативными и ассоциативными, таких как произведение целых чисел или объединениемультимножеств.ТопологияЦ /ДСложность231СсылкаКольцоЦNалгоритм 6.1ДO(N log N) алгоритм 7.7Произвольная Ц2|E|алгоритм 6.4Д O(N log N + |E|) раздел 7.5.3ДеревоЦ2(N − 1)алгоритм 6.4ДO(N)алгоритм 6.2Таблица 6.19.
Влияние централизации на сложность по числу сообщенийОказывается, общего метода для вычисления сумм при помощи волновогоалгоритма не существует, но в отдельных случаях вычисление суммы возможно. Это те случаи, когда алгоритм является алгоритмом обхода, когда процессынаделены отличительными признаками, или когда алгоритм порождает остовноедерево, которое может быть использовано.Невозможность общего построения.
Нельзя предложить общую конструкцию для вычисления сумм на основе произвольного волнового алгоритма, подобную той, которая была использована в теореме 6.12 для вычисления точныхнижних граней. И вот почему. Есть волновой алгоритм, а именно фазовый алгоритм (с параметром D = 2), для определенного класса сетей, включающего всенеориентированные безымянные сети диаметра два. Но нет алгоритма, способного вычислять сумму всех входных данных, который делал бы это корретно на всехнеориентированных безымянных сетях диаметра два. К этому классу сетей относятся две сети, изображенные на рис.
6.20. Предположим, что на вход каждогопроцесса поступила 1. Тогда искомый результат равен 6 для левой сети и 8 дляправой сети. Применяя метод, предложенный в гл. 9, можно показать, что всякийалгоритм будет выдавать одинаковый результат на каждой из этих двух сетей, и,значит, он не является одновременно корректным для обеих сетей. Детальнуюразработку этой аргументации оставляем читателю в качестве упражнения 9.7.Вычисление суммы с помощью алгоритмов обхода.
Если A является алгоритмом обхода, то сумму всех входных данных можно вычислить так. Пустьпроцесс p обладает переменной jp , первоначальное значение которой — это входные данные процесса p. Наделим маркер дополнительным полем s. Всякий раз,когда процесс p передает маркер, он выполняет операторs := s + jp ; jp := 0.И тогда можно показать, что каждый раз, когда маркер покидает процесс p, будетвыполняться соотношение jp = 0, а s будет иметь значение, равное сумме входныхданных для всех ранее пройденных процессов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
