Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 100
Текст из файла (страница 100)
Восприятие направления называется униформным, есликаждый процесс обладает одним и тем же набором локальных пометок.Обозначим символом L общее множество пометок на дугах. Тогда некоторыесвойства униформного восприятия направления следуют немедленно из определения.378Гл. 11. Восприятие направления и ориентация1. Если g ∈ L, то −g ∈ L: связующая дуга, помеченная элементом g на одномконце, помечена элементом −g на другом конце.2.
Множество L порождает G, поскольку для каждого g ∈ G существует такойпуть P, что SUML (P) = g.3. Для всякого элемента g ∈ G кратчайший путь P, для которого выполняетсяравенство SUML (P) = g, может быть вычислен локально на основе обобщенного варианта задачи о размене монеты. Достаточно вычислить минимальнуюпоследовательность пометок из L, дающих в сумме g, и, поскольку у каждогопроцесса есть такие пометки, эта последовательность задает путь в сети.Мы будем описывать сеть с униформным восприятием направления, простоуказывая множество пометок, используемых в каждом процессе, и опуская приэтом обратные элементы.Примеры.
В научных публикациях упоминаются несколько примеров восприятия направления, и большинство из них подпадают под наше определение. Вработе Флокчини и др. [86] определено хордовое восприятие направления: этовсякое восприятие направления над группой Z N . Особого внимания заслуживаетуниформное хордовое SoD, в котором 1 (или всякий иной порождающий элемент)содержится среди пометок. Хордовое кольцо размера N похоже на обыкновенноекольцо, но только из каждой вершины исходят «срезающие пути», соединяющиеее с вершинами, отстоящими на несколько шагов далее по кольцу.Определение 11.3. Хордовым кольцом CN (c1 , . .
. , ck) называется сеть, в которой существует униформное хордовое восприятие направления, и при этомL = {−ck , . . . , −c1 , −1, 1, c1 , . . . , ck },где k называется числом хорд.Требование, чтобы порождающий элемент группы использовался в качествепометки, очень существенно. Так, например, k × l-тор с циклическим возвратоми взаимно простыми k и l имеет униформное восприятие направления, но неявляется при этом хордовым кольцом. Мы дадим альтернативные определенияв терминах теории групп ряду уже известных топологий.Определение 11.4.
Тором размераn × n называется сеть, для которой существует униформное SoD над группой (Zn) 2 и при этом L = { (0, 1), (0, −1), (1, 0), (−1, 0) }.(Для удобства эти пометки обозначаются N, S, E, W.)Определение 11.5. Гиперкубом размерности n называется сеть, для которой существует униформное восприятие направления над группой (Z 2) n с nпометками, обозначаемыми i = (0, . .
. , 1, . . . , 0), где i = 0, . . . , n − 1.Определение 11.6. Кликой называется сеть, для которой существует униформное SoD над группой ZN и при этом L = ZN \ {0}.11.1. Введение и определения37911.1.2. Применение восприятия направленияМы приведем описание нескольких наиболее важных методов, в основу которых положено применение восприятия направления. Далее в этой главе дляиллюстрации и пояснения этих методов будет представлено полное описание алгоритмов.Сравнение путей. Если заданы два пути 1 и 2 , исходящие из одной и тойже вершины, то пометки, приписанные дугам этих путей, позволяют узнать, оканчиваются ли эти пути в одной и той же вершине или нет.
Действительно, все, чтонам нужно, — это просуммировать пометки на каждом пути; вершины, в которыеведут эти пути, будут совпадать в том и только том случае, когда вычисленныесуммы будут равны.Восприятие направления, таким образом, равносильно осведомленности о соседях, и благодаря этому становится возможен обход сети в глубину с использованием O(N) обменов сообщениями, как это было установлено в § 6.4.3.
Длятого чтобы это можно было проделать, восприятие направления не обязательнодолжно быть униформным.Возможность сравнивать пути настолько присуща восприятию направления,что Флокчини и др. в статье [86] предложили считать это свойство определениемвосприятия направления. В предложенном ими подходе разметка непосредственно сопровождается построением явной транслирующей функции, позволяющейвычислять относительное местоположение конечной точки пути. С одной стороны, это определение является более общим, так как оно описывает более обширный класс разметок.
Однако преимущества такого подхода ограничены: этотобширный класс включает в себя осведомленность о соседях (согласно нашемуопределению это качество не является примером восприятия направления) и ктому же некоторые разметки чрезвычайно редко применяются при проектировании распределенных алгоритмов. С другой стороны, теоретико-групповой подходдает возможность получить компактное представление транслирующей функции(как сложение элементов групп), позволяя тем самым сосредоточить вниманиена более углубленных методах применения восприятия направления.Сжатие путей. Если восприятие направления является униформным, то онодает нам полные сведения о топологии сети.
Действительно, в таком случае восприятие направления невозможно рассматривать в отрыве от полной осведомленности о топологии. Униформное восприятие направления позволяет провестиэффективную маршрутизацию в любую вершину, относительное местоположениекоторой известно, при помощи обобщенного варианта задачи о размене монеты,упомянутой нами ранее.Структура сети. Униформное восприятие направления позволяет управлятьобщим ходом алгоритма, руководствуясь теоретико-групповым представлениемструктуры сети. В качестве примеров будут рассмотрены алгоритм широковещательного распространения сообщений (алгоритм 11.2) и один из вариантовалгоритма избрания лидера на гиперкубе (§ 11.3.2).380Гл. 11.
Восприятие направления и ориентация11.1.3. Широковещательная рассылка сообщений приналичии восприятия направленияВвиду того, что лейтмотивом этой главы является сопоставление сложностишироковещательного распространения сообщений при наличии и при отсутствиивосприятия направления, мы покажем здесь, что восприятие направления позволяет проводить широковещательную связь с использованием O(N) обменовсообщениями.
Если же информация о топологии недоступна, то для широковещательной рассылки сообщений требуется совершить хотя бы по одному обменусообщениями по каждому каналу связи (теорема 6.6), и, следовательно, сложность по числу обменов сообщениями составляет величину Ω (|E|).Применение восприятия направления для поиска в глубину. Как былоотмечено Менсом и Санторо, алгоритм поиска в глубину с использованием осведомленности о соседях (§ 6.4.3) можно легко обобщить на случай сетей с восприятием направления. Напомним, что алгоритм 6.17 проводит перемещение маркера, в котором содержится список имен ранее посещенных процессов. Отправление маркера по листовидным дугам удается полностью устранить, так как процесс, передающий маркер, будет проверять, содержится ли имя соседа в указанном списке.varfatherp: processinit udef ;Только для инициатора, выполнить один раз:begin fatherp := p ; choose q ∈ Neighp ;send htlist, {0}i to qendДля каждого процесса после получения сообщения htlist, Li по каналу :begin forall x ∈ L do x := x + ;if fatherp = udef then fatherp := ;if ∃q ∈ Neighp \ Lthen begin choose q ∈ Neighp \ L ;send htlist, L ∪ {0}i to qendelse if p is initiatorthen decideelse send htlist, L ∪ {0}i to fatherpendАлгоритм 11.1.
Алгоритм поиска в глубину с SoDВ алгоритме 11.1 показано, как использовать восприятие направления вместоосведомленности о соседях. Список, передаваемый вместе с маркером, содержитне имя процесса (мы не пользуемся предположением о том, что оно известно), а указание местоположения процесса относительно той вершины, в которой11.1.
Введение и определения381пребывает маркер. В алгоритме применяется способность проводить «сравнениепутей»: процесс q заносит себя в список, поместив туда элемент 0. После тогокак этот список пройдет путь , сумма пометок на котором составляет элемент ,и достанется, например, процессу p, элемент 0 превратится в − . Заметим здесь,что Lq (p) = и Lp (q) = − , и поэтому в этом списке можно обнаружить пометкудуги pq.Единственное дополнительное действие, которое нужно внести в алгоритм 6.17,состоит в том, что по получении указанного списка все относительные позициив нем уточняются за счет прибавления к каждой из них пометки того канала, покоторому этот список был доставлен.Этот алгоритм можно использовать не только для широковещательной рассылки сообщений, но также и для проведении выборов лидера по алгоритму Каттена и др.
(§ 7.5.4), и в таком случае мы получим алгоритм, требующий O(N log N)обменов сообщениями. Тем самым, достигнут первый успех на пути применениявосприятия направления, поскольку для задач широковещательной рассылки сообщений и избрания лидера без SoD у нас есть точные нижние оценки (теоремы 6.6 и 7.15). Мы подчеркиваем, что восприятие направления не обязано бытьуниформным, и поэтому возможности сравнивать пути вполне достаточно дляполучения этого результата.Следствие 11.7. В тех сетях, в которых отсутствует осведомленность о топологии, наличие восприятия направления уменьшает сложность широковещательной рассылки сообщений с величины Θ (m) до величины Θ (N), а сложность проведения выборов лидера с величины Θ (N log N+m)до величины Θ (N log N).Структурный алгоритм для униформного SoD.
Униформное восприятиенаправления позволяет процессам извлекать из сети остовное дерево «на лету»и вести по этому дереву широковещательную рассылку сообщений, используяв точности N − 1 обменов сообщениями. Эта величина оптимальна, так как каждый из N − 1 процессов, помимо инициатора рассылки, должен быть ознакомленс рассылаемой информацией за счет получения сообщения.Вначале мы приведем простой пример этого алгоритма: предположим, что сетьпредставляет собой n × n-тор, дуги которого помечены «Север», «Восток», и т. п.Широковещательная связь проводится так. Инициатор отправляет сообщениена Восток, и сообщение совершает n − 1 переходов в восточном направлении.Инициатор, а также каждая вершина, в которую поступает сообщение с Запада,отправляет сообщение на Север, и сообщение совершит в точности n − 1 шаговв этом направлении.Легко видеть, что такая стратегия срабатывает и при этом происходит в точности N − 1 обменов сообщениями; если добавить к ним N − 1 подтверждающихсообщений, то алгоритм будет проводить широковещательную рассылку сообщений с обратной связью (PIF).
Если бы мы отправили сообщение на один шагдальше на Восток, то его следующим адресатом стал бы сам инициатор, что излишне. Если бы мы отправили сообщение на один шаг дальше на Север, его382Гл. 11. Восприятие направления и ориентацияполучил бы процесс, который сам же и отправил его на Север, а это тоже излишне.Этот пример показывает, каким образом униформное восприятие направлениядает информацию о структуре всей сети в целом и как эта информация используется в алгоритме.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
