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

В построенноммоментальном состоянии системы все процессы являются пассивными , так какмаркер обрабатывается только пассивными процессами . Поэтому для вычисления значения Pholds требуется всего лишь проверить , пусты ли все каналы . Для10.5. Упражнения к главе 10373этого в маркере указывается суммарное значение счетчиков сообщений . Однакомне неясна та роль , которую играют окраски white и black, а также как удаетсяобеспечить значимость моментальных состояний системы .»Не могли бы Вы помочь профессору?11.1.

Введение и определенияГ Л А В А 11ВОСПРИЯТИЕ НАПРАВЛЕНИЯ И ОРИЕНТАЦИЯВ сетях, имеющих регулярную структуру, наподобие торов или гиперкубов,в соединительных линиях обычно указывается их направление. Мы обсудим здесьрезультаты сравнительно недавних исследований, оценивающих ту пользу, которую приносит подобная разметка; эту разметку мы будем называть восприятием направления или сокращенно SoD 1) . Восприятие направления усиливаетмодель и дает процессам возможность более эффективно обмениваться информацией друг с другом, а также использовать в своих алгоритмах топологическиеособенности сетей связи.Как было установлено, восприятие направления позволяет понизить сложность некоторых задач, однако тот класс задач, для решения которых применимаэта возможность, оказывается необычайно мал.

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

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

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

Несколько лет назад стали известны очень эффективные алгоритмы для размеченных гиперкубов; алгоритмы для неразмеченных гиперкубовбыли менее эффективны, и исследования были сосредоточены на доказательствесоответствующих нижних оценок. Не так давно, однако, были предложены более эффективные алгоритмы для неразмеченных гиперкубов, свидетельствующиео том, что повышение эффективности достигается за счет особенностей топологии, а не за счет разметки дуг.В § 11.4 обсуждается ряд вопросов, связанных со сложностью алгоритмов,включая алгоритмы формирования восприятия направления в неразмеченных сетях.

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

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

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

Мы будем использовать запись −x для элемента, обратногоэлементу x. Если s ∈ Z, то запись s · x будет обозначать сумму, состоящую из sэлементов x.Количество элементов в множестве G называется порядком; при изучениивосприятия направления порядок ord(G) будет полагаться конечным. В конечныхгруппах для каждого элемента x существует такое положительное число k, чтоk · x = 0; наименьшее из подобных положительных чисел называется порядкомэлемента x, и оно всегда является делителем порядка группы.Для произвольного набора элементов g1 , .

. . , gk рассмотрим множество всехтех элементов группы, которые представимы в виде суммы этих элементов g i :)(kXS = x : ∃s 1 , . . . , s k : x =s i · gi .i=1Это множество само является группой; оно называется подгруппой, порожденной элементами g1 , . . . , gk , и обозначается записью hg1 , .

. . , gk i. Для элементаy ∈ G множество T = S + y = {y + x : x ∈ S} называется орбитой подгруппы S.Все орбиты подгруппы S имеют одинаковый размер, причем две орбиты S + y 1и S + y2 либо совпадают, либо не пересекаются. Таким образом, орбиты подгруппы S разбивают группу G на непересекающиеся множества.Группа называется циклической, если она порождается единственным элементом, т. е. существует такой элемент g, что G = hgi. Порождающий элемент неединствен (исключение составляет группа порядка 2), но мы обычно выбираемнекоторый фиксированный порождающий элемент и обозначаем его 1; запись iпри этом будет обозначать элемент i · 1. Циклическую группу порядка k будемобозначать Zk .Таким образом, Zk — группа сложения натуральных чисел по модулю k: ееэлементами являются числа, начиная с 0 и оканчивая k − 1. Другая группа, заслуживающая особого внимания, — это группа (Zk) d , элементами которой являютсявекторы длины d, а в качестве групповой операции выступает покомпонентноесложение по модулю k.Сети и разметки.

В дальнейшем мы будем полагать, что G — это коммутативная группа и для соседних процессов p и q запись L p (q) обозначает имя,которое используется в процессе p для обозначения связи pq. В основе идеи использования теоретико-группового восприятия направления лежит соответствиемежду топологией сети и структурой группы.11.1. Введение и определения377Определение 11.1. Разметка дуг L считается восприятием направления(на основе G), если все дуги помечены элементами группы G и существует такоеинъективное отображение N множества вершин сети в множество G, что длялюбой пары соседних процессов p и q выполняется равенство N q = Np + Lp (q).Если задано восприятие направления L, то та разметка вершин сети, котораяупомянута в приведенном определении, называется свидетельствующей разметкой или просто свидетельством для L.

Процессоры осведомлены о разметке связей L, но при этом не предполагается и не требуется, чтобы свидетельствующая разметка вершин была известна процессам; эта разметка не является составной частью восприятия направления. Нетрудно показать (см. [192]),что свидетельствующая разметка вершин не единственна; всякую заданную свидетельствующую разметку можно модифицировать, добавив к пометке каждойвершины один и тот же элемент группы в качестве слагаемого. Поэтому количество свидетельствующих разметок для восприятия направления в точности равнопорядку группы ord(G).Восприятие направления можно охарактеризовать и без упоминания разметкивершин, а именно при помощи свойств замкнутых путей (см.

упражнение 11.1).Обратим внимание на то, что SoD не использует элемент 0 для разметки дуг(ввиду того, что соседние вершины помечены по-разному) и что SoD удовлетворяет свойству антисимметричности Lp (q) + Lq (p) = 0, или, что то же самое,Lp (q) = −Lq (p). Обычно получается так, что порядок группы равен числу вершин сети, и, следовательно, свидетельствующая разметка является биекцией. Этосвойство никак не учитывается в большинстве алгоритмов, которые мы опишемздесь, но часто оно неявно подразумевается.Для заданной сети, состоящей из N процессов, и группы G порядка N нетрудно построить восприятие направления.

Вначале припишем всем вершинам различные элементы группы G, а затем возьмем в качестве разметки каждой дугиLp (q) элемент Nq − Np . В результате получим восприятие направления.Как мы увидим в дальнейшем, полученная таким образом разметка позволяет значительно уменьшить сложность отдельных задач, однако большинстворазметок, которые оказались особенно эффективными, обладают еще одним дополнительным качеством — униформностью.Униформность. Процессоры в параллельных компьютерах часто соединенытак, что образуется заранее известная симметрическая структура (т. е. граф выглядит одинаково «с точки зрения» любого процесса); как раз симметрия и осведомленность о топологии подразумеваются в униформном восприятии направления.Определение 11.2.