Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 99

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 99)

Восприятие направления усиливаетмодель и дает процессам возможность более эффективно обмениваться инфор­мацией друг с другом, а также использовать в своих алгоритмах топологическиеособенности сетей связи.Как было установлено, восприятие направления позволяет понизить слож­ность некоторых задач, однако тот класс задач, для решения которых применимаэта возможность, оказывается необычайно мал. На самом деле, есть много за­дач для которых известны эффективные или простые алгоритмы, использующиеразметку дуг. Тем не менее, во многих нетривиальных случаях хорошие нижниеоценки, которые известны для неразмеченных вариантов задачи, оказываютсянедостижимыми, и, более того, для неразмеченных графов удалось построитьнесколько невероятно эффективных алгоритмов.В этой главе предпринята попытка проследить усилия, инициированные Сан­торо в работе [168], с целью выявления тех вариантов задачи о выборах и за­дачи широковещательного распространения сообщений, в которых восприятиенаправления приносит выгоду.Мы определим восприятие направления для некоторых специальных классовсетей и покажем, что задача о выборах на кольцах может быть решена болееэффективно при наличии восприятия направления, если в нашем распоряжениибудут хорды.

Мы покажем, что, располагая восприятием направления, избра­ние лидера на гиперкубах и кликах можно осуществить с линейной сложностью,но при этом такой же сложности можно достичь при помощи рандомизованныхалгоритмов, в которых не используется SoD. Мы обсудим также алгоритмы фор­мирования SoD в сетях, где его первоначально не было.Обзор главы. В §11.6.1 вводятся некоторые общие понятия и ставятся зада­чи, которые будут обсуждаться в последующих параграфах. В §11.1.1 даютсястрогие определения восприятия направления, а в § 1 1 . 1 .2 приводятся примеры,иллюстрирующие его применение.

В §11.1.3 описано, как эффективно прове­сти широковещательное отправление сообщения, используя униформное вос­приятие направления. В § 11.6.2 приведены некоторые результаты, касающиеся') От англ. Sense of Direction. — Прим, перев.11.1. Введение и определения375выборов на простых кольцах и кольцах с хордами с учетом восприятия направле­ния; при этом будет показано, что восприятие направления позволяет уменьшитьсложность избрания лидера на кликах.В §11.6.3 изучаются преимущества, которые дает восприятие направленияна гиперкубах. Несколько лет назад стали известны очень эффективные алго­ритмы для размеченных гиперкубов; алгоритмы для неразмеченных гиперкубовбыли менее эффективны, и исследования были сосредоточены на доказательствесоответствующих нижних оценок.

Не так давно, однако, были предложены бо­лее эффективные алгоритмы для неразмеченных гиперкубов, свидетельствующиео том, что повышение эффективности достигается за счет особенностей тополо­гии, а не за счет разметки дуг.В §11.4 обсуждается ряд вопросов, связанных со сложностью алгоритмов,включая алгоритмы формирования восприятия направления в неразмеченных се­тях. В конце главы (§ 11.5) мы проведем обсуждение открытых вопросов.11.1. Введение и определенияКак обычно, мы будем моделировать сеть процессов графом с N вершинамии т дугами. Дуги, примыкающие к каждому процессу, имеют локальные имена,и поэтому процесс может различать, по какой дуге к нему поступила информа­ция, и может выбирать, по какой дуге ему отправлять информацию. Процессорыимеют разные отличительные признаки, но этими признаками являются числа,которые не имеют специального истолкования и не привязаны к топологии сети.Мы будем иметь дело с асинхронными сетями.11.1.1. Определения и характеристические свойствавосприятия направленияХотя восприятию направления было уделено немало внимания в последниегоды, простое определение этого понятия так и не было согласовано.

В работе[190] были определены некоторые частные случаи, а в работе [8 6 ] был выделенряд классов восприятия направления.Определения из теории групп. Мы будем использовать методы теории груп­пы, и поэтому начнем с того, что напомним некоторые понятия из теории групп.Тем читателям, кто незнаком с теорией групп, некоторые из определений могутпоказаться загадочными, но мы, по мере возможности, снабдим наши определе­ния конкретными примерами.Коммутативной, или абелевой, группой называется множество G с выде­ленным нулевым элементом 0 и бинарной операцией +, которые удовлетворяютследующим требованиям.1.

Замкнутость. Для любых элементов х, у &G выполняется соотношение(х + у) € G.2. Тождественность. Для любого элемента х <Е G выполняются равенства0~\~х = х~Т0 = х.376Гл. 11. Восприятие направления и ориентация3. Обратимость. Для любого элемента х € G существует такой элементу е G, что х + у = у + х = 0.4. Ассоциативность. Для любых элементов х, у, z ^ G выполняется равен­ство (х + у) + z = х + (у + z).5. Коммутативность.

Для любых элементов х, у выполняется равенствох + у = у + х.Вследствие закона ассоциативности скобки при проведении суммирования мо­гут быть опущены. Мы будем использовать запись —х для элемента, обратногоэлементу х. Если s € Z, то запись s ■х будет обозначать сумму, состоящую из sэлементов х.Количество элементов в множестве G называется порядком ; при изучениивосприятия направления порядок ord(G) будет полагаться конечным. В конечныхгруппах для каждого элемента х существует такое положительное число k, чтоk ■х = 0 ; наименьшее из подобных положительных чисел называется порядкомэлемента х, и оно всегда является делителем порядка группы.Для произвольного набора элементов g i, ■■■, gk рассмотрим множество всехтех элементов группы, которые представимы в виде суммы этих элементов gpЭто множество само является группой; оно называется подгруппой, порожден­элементами g \ , ■■■, g k , и обозначается записью (gi, .

. . , g k ) . Для элементау е G множество T = S + y = {y + x : x e S } называется орбитой подгруппы S.Все орбиты подгруппы 5 имеют одинаковый размер, причем две орбиты S + у\и 5 + 1/2 либо совпадают, либо не пересекаются. Таким образом, орбиты подгруп­пы 5 разбивают группу G на непересекающиеся множества.Группа называется циклической, если она порождается единственным эле­ментом, т. е. существует такой элемент g, что G = (g). Порождающий элемент неединствен (исключение составляет группа порядка 2 ), но мы обычно выбираемнекоторый фиксированный порождающий элемент и обозначаем его 1 ; запись iпри этом будет обозначать элемент i ■1.

Циклическую группу порядка k будемобозначать Z*.Таким образом, Z* — группа сложения натуральных чисел по модулю k: ееэлементами являются числа, начиная с 0 и оканчивая k —\. Другая группа, заслу­живающая особого внимания, — это группа (Z/,)d, элементами которой являютсявекторы длины d, а в качестве групповой операции выступает покомпонентноесложение по модулю k.нойСети и разметки. В дальнейшем мы будем полагать, что G — это комму­тативная группа и для соседних процессов р и q запись Cp(q) обозначает имя,которое используется в процессе р для обозначения связи pq.

В основе идеи ис­пользования теоретико-группового восприятия направления лежит соответствиемежду топологией сети и структурой группы.11.1. Введение и определения377Определение 11.1. Разметка дуг С считается восприятием направления(на основе G), если все дуги помечены элементами группы G и существует такоеинъективное отображение N множества вершин сети в множество G, что длялюбой пары соседних процессов р и q выполняется равенство Mq = Afp + £ P(q)Если задано восприятие направления £, то та разметка вершин сети, котораяупомянута в приведенном определении, называется свидетельствующей раз­меткой или просто свидетельством для £. Процессоры осведомлены о раз­метке связей £, но при этом не предполагается и не требуется, чтобы свидетель­ствующая разметка вершин была известна процессам; эта разметка не являет­ся составной частью восприятия направления.

Нетрудно показать (см. [192]),что свидетельствующая разметка вершин не единственна; всякую заданную сви­детельствующую разметку можно модифицировать, добавив к пометке каждойвершины один и тот же элемент группы в качестве слагаемого. Поэтому количе­ство свидетельствующих разметок для восприятия направления в точности равнопорядку группы ord(G).Восприятие направления можно охарактеризовать и без упоминания разметкивершин, а именно при помощи свойств замкнутых путей (см. упражнение 1 1 . 1 ).Обратим внимание на то, что SoD не использует элемент 0 для разметки дуг(ввиду того, что соседние вершины помечены по-разному) и что SoD удовлетво­ряет свойству антисимметричности Cp(q) + Cq(p) = 0 , или, что то же самое,£ p(q) = —Cq(p). Обычно получается так, что порядок группы равен числу вер­шин сети, и, следовательно, свидетельствующая разметка является биекцией.

Этосвойство никак не учитывается в большинстве алгоритмов, которые мы опишемздесь, но часто оно неявно подразумевается.Для заданной сети, состоящей из N процессов, и группы G порядка N нетруд­но построить восприятие направления. Вначале припишем всем вершинам раз­личные элементы группы G, а затем возьмем в качестве разметки каждой дугиCp(q) элемент J\fq —ЛГР. В результате получим восприятие направления.Как мы увидим в дальнейшем, полученная таким образом разметка позво­ляет значительно уменьшить сложность отдельных задач, однако большинстворазметок, которые оказались особенно эффективными, обладают еще одним до­полнительным качеством — униформностью.Униформность.

Характеристики

Список файлов книги