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

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

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

6.3. Поддеревья Tpqства (2 N - 2) - К Д 2 ( N - К ) + К следует, что - 2 > 0. Полученное противоречиеозначает, что хотя бы одно решение в у уже принято; см. также упражнение 6.5.Наконец, необходимо показать, что решение предшествует какому-либо со­бытию в каждом из процессов. Напомним, что f p q обозначает событие отправ­ления процессом р сообщения процессу q, a g pq — событие приема процессом qсообщения от процесса р. Воспользуемся индукцией по числу событий приема,чтобы показать, чтоV s € Tpq Эе еCs: е Д g pq.Допустим, это верно для всех событий приема, предшествующих событию g pq.Тогда событию g pq предшествует событие fpq (в процессе р) и из устройствапрограммы р следует, что для всех r g N e i g h p при г ф q событию fpq предшествуетсобытие g rp.

Из индуктивной гипотезы вытекает, что для всех таких г и для всехs <Е Т гр найдется такое событие е € C s , что е Д g rp. Значит, е Д g pq.Решению dp в р предшествует событие g rp для всех г <Е N e i g h p , И отсюдаследует, что V s е Р Зе е C s : е Д d p .□Читатель может промоделировать вычисление алгоритма на небольшом де­реве (например, на дереве, изображенном на рис. 6.3), и удостовериться в спра­ведливости следующих замечаний. В алгоритме 6.2 есть два процесса, которыеполучают сообщение по каждому из своих каналов и принимают решение; всеостальные процессы еще ожидают сообщения, пребывая в заключительной кон­фигурации в точке х своей программы.

Если к нашей программе добавить опера­тор forall (тот самый, который «закомментирован» в алгоритме 6 .2 ), то решениебудут принимать все процессы, и в заключительной конфигурации каждый про­цесс будет пребывать в заключительном состоянии. Всего в модифицированнойпрограмме используется 2 N —2 сообщений.Гл. 6.206Волновые алгоритмы и алгоритмы обхода6.2.3. Алгоритм эхаАлгоритм эха — это централизованный волновой алгоритм для сетей с произ­вольной топологией. Впервые как отдельный алгоритм он был представлен Ченемв работе [41] и поэтому иногда называется алгоритмом Ченя.

Несколько болееэффективная версия была предложена Сигаллом [174], и мы рассмотрим здесьименно ее.Алгоритм наводняет сообщениями t o k все процессы, выделяя таким образомостовное дерево, как это было определено в лемме 6.3. Маркеры возвращаются«эхом» обратно по ребрам этого дерева, напоминая поток сообщений в древес­ном алгоритме (см. алгоритм 6.4). Инициатор отправляет сообщение всем своимсоседям. После получения первого сообщения всякий неинициатор переправляетсообщения всем своим соседям, за исключением того, от которого было полученоэто сообщение.

Как только неинициатор получит сообщения от всех своих сосе­дей, он отправляет эхо родительскому процессу. Как только инициатор получитсообщения от всех своих соседей, он принимает решение.varreCp: integer in it 0 ; (* Подсчет числа полученных сообщений *)fatherp : Рin it undef ;Для инициатора:b egin forall q € Neighp do send (tok) tow h ile reCp < UNeighp dob egin receive (tok) ; recp :=q;recp +1 end;decideen dДля неинициатора:b egin receive (tok) from neighbor q ; fatherp := q ; recp := recp +forall q € Neighp, q / father,, do send (tok) to q ;recp < if Neighp dobegin receive (tok) ; recp := recp +send (tok) to fatherp1;w h ile1end;endАлгоритм 6.4.Алгоритм эхаТеорема 6.17.

Алгоритм эха (алгоритм 6.4) является волновым алго­ритмом.Д о к а з а т е л ь с т в о . Поскольку каждый процесс отправляет не болееодного сообщения по инцидентному каналу, число сообщений, которыми обме­ниваются процессы на протяжении одного вычисления, конечно. Пусть у — за­ключительная конфигурация, которая достигается при вычислении С с инициа­тором ро-6.2.

Семейство волновых алгоритмов207Для этой конфигурации определим (так же, как в лемме 6.3) граф Т = (Р, Ер),полагая pq е Ер -^=>- fatherp = q. Чтобы показать, что этот граф являетсядеревом, необходимо установить, что число ребер меньше числа вершин на еди­ницу (лемма 6.3 утверждает, что Т — дерево, но исходя из предположения о том,что используемый алгоритм — волновой, а это как раз то, что нам здесь нужнодоказать). Заметим, что каждый процесс, участвующий в С, отправляет сообще­ния всем своим соседям, за исключением (если только этот процесс не являетсяинициатором) того соседа, от которого было получено первое сообщение.

Значит,каждый его сосед получит хотя бы одно сообщение в С и также примет участиев С. Отсюда следует, что fatherр ф udef для всех р Ф ро. То, что Т не содержитциклов, было показано в доказательстве леммы 6.3.Корнем дерева служит вершина ро. Обозначим символом Тр множество вер­шин поддерева, растущего из вершины р. Ребра сети, не принадлежащие Т, на­зовем стягивающими. В конфигурации у каждый процесс р обязательно долженотправить сообщения всем своим соседям, за исключением родительской верши­ны fatherp , и, следовательно, в ходе вычисления С по каждому стягивающемуребру должно передаваться сообщение в обе стороны.

Обозначим символом fpсобытие отправления процессом р сообщения родительской вершине (если та­ковое случается в С), а символом gp — событие получения процессом fatherрсообщения от р (если это происходит). Индукцией по числу вершин дерева мож­но показать, что1) С содержит событие fp для каждого р Ф ро,2) для всех s е Т р есть такое е е Cs, что е ф gp.Мы рассмотрим следующие два случая.Процесс р — это листовая вершина. Процесс р в вычислении С уже по­лучил сообщение от своей родительской вершины и от всех своих соседей (по­скольку все прочие каналы являются стягивающими ребрами).

Значит, он могсовершить отправление сообщения tok процессу fatherр. Коль скоро у являет­ся заключительной конфигурацией, это сообщение было отправлено. Дерево Трсодержит одну лишь вершину р, и, очевидно, fp ■<gp.Процесс р не является листовой вершиной. Процесс р в С уже получилсообщение от родительской вершины, а также по всем стягивающим ребрам.

Поиндуктивной гипотезе в вычислении С для каждой сыновней вершины р' процессар представлено событие fp>. Коль скоро у — это заключительная конфигурация,вычисление С содержит также и событие gp>. Следовательно, событие отправ­ления сообщения tok процессу fatherр имеет все предпосылки, для того чтобыосуществиться. И поскольку конфигурация у является заключительной, это со­общение было отправлено. Дерево Тр содержит объединение деревьев Тр>по всемсыновним вершинам процесса р и саму вершину р. Применив индуктивную гипо­тезу, можно показать, что в каждом процессе из этого множества есть событие,предшествующее gp.Отсюда также следует, что процесс ро уже получил сообщение от каждогосвоего соседа и что ро осуществил событие decide, которому предшествует хотябы одно событие в каждом из процессов.□208Гл.

6.Волновые алгоритмы и алгоритмы обходаОстовное дерево, построенное в ходе вычисления алгоритма 6.4, иногда ис­пользуется последующими алгоритмами. Например, алгоритм Мерлина—Сигалла для вычисления таблицы маршрутизации по кратчайшим путям исходит изпредположения о том, что остовное дерево с корнем в vo уже задано; см. § 4.2.3.Это исходное остовное дерево может быть вычислено при помощи алгоритма эха.В последней конфигурации алгоритма каждый процесс (отличный от ро) запоми­нает, кто из соседей является его родительской вершиной, но своих сыновнихвершин среди соседей он в этом дереве не различает.

В нашем алгоритме однои то же сообщение поступает от родительской вершины по стягивающим ребрам,а также от сыновних вершин. Если требуются сведения о сыновних вершинахв построенном дереве, алгоритм нужно чуть-чуть видоизменить так, чтобы сооб­щение, отправляемое родительской вершине (последняя операция отправлениясообщения для неинициаторов), было особым.

Сыновними вершинами процессабудут признаны те соседи, от которых поступило особое сообщение.6.2.4. Алгоритм опросаВ сети, образующей клику, каждая пара процессов соединена каналом. Вся­кий процесс может судить о том, получил ли он сообщение от каждого своегососеда. В алгоритме опроса (см. 6.5) инициатор обращается к каждому соседус просьбой отправить ему сообщение и принимает решение после получения всехсообщений.var recp: in teg erinit 0 ;(* только для инициатора *)Для инициатора:b eginto rail q € Neighp do send (tok) to q f ;w h ile recp < #Neighp dob egin receive (tok) ; recp := recp + 1 end;decideendДля неинициатора:b eginreceive(tok)from q ; send to k to qen dАлгоритм 6.5.

Алгоритм опросаТеорема 6.18. Алгоритм опроса (алгоритм 6.5) является волновым ал­горитмом.Д о к а з а т е л ь с т в о . В этом алгоритме по каждому каналу, инцидентно­му инициатору, отправляются два сообщения. Каждый сосед инициатора отвечаетодин раз на полученный запрос, и, следовательно, инициатор получает N —1 от­кликов.

Это как раз то число, которое необходимо для принятия решения, и от-6.2. Семейство волновых алгоритмов209сюда следует, что инициатор примет решение, и этому решению предшествуетнекоторое событие в каждом из процессов.□Опрос можно проводить также и в звездных сетях, если инициатор будетрасполагаться в центре.6.2.5. Фазовый алгоритмВ этом параграфе будет представлен фазовый алгоритм, который является де­централизованным алгоритмом, пригодным для сетей с произвольной топологией.Этот алгоритм был предложен в работе [187, §4.2.3]. Его можно использоватьв качестве волнового алгоритма для ориентированных сетей.В этом алгоритме требуется, чтобы все процессы располагали сведениямио диаметре сети, который обозначен константой D в тексте описания алгорит­ма. Алгоритм будет оставаться корректным (хотя и менее эффективным), есливсе процессы будут использовать вместо D константу D ', превышающую диа­метр сети.

Таким образом, для применения фазового алгоритма не нужно знатьточного значения диаметра; достаточно, если будет известна верхняя оценка (на пример, N — 1) диаметра сети. Во всех процессах должна использоваться однаи та же константа D'. Пелег в работе [158] расширил этот алгоритм так, чтобыдиаметр вычислялся по ходу выполнения алгоритма, но в этом случае требуетсяоднозначная идентифицируемость процессов.Общий случай.

Алгоритм можно применять для всякой ориентированнойсети, по каналам которой осуществляется односторонняя передача сообщений. Вэтом случае соседями вершины р будут соседи на входе (т. е. процессы, которыемогут отправлять сообщения процессу р) и соседи на выходе (т. е. процессы,которым р может отправлять сообщения). Соседи процесса р на входе образуютмножество 1пр, а соседи на выходе — множество Outp.В фазовом алгоритме всякий процесс отправляет в точности D сообщенийкаждому соседу на выходе. При этом (г + 1)-е сообщение отправляется каждомусоседу на выходе только после того, как были получены i сообщений от каждогососеда на входе (см. алгоритм 6 .6 ).И в самом деле, из описания алгоритма сразу видно, что по каждому ка­налу передается не более D сообщений (то, что по каждому каналу передаетсяне менее D сообщений, мы покажем ниже).

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

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