Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 56
Текст из файла (страница 56)
Если к нашей программе добавить оператор forall (тот самый, который «закомментирован» в алгоритме 6.2), то решениебудут принимать все процессы, и в заключительной конфигурации каждый процесс будет пребывать в заключительном состоянии. Всего в модифицированнойпрограмме используется 2N − 2 сообщений.206Гл. 6.Волновые алгоритмы и алгоритмы обхода6.2.3. Алгоритм эхаАлгоритм эха — это централизованный волновой алгоритм для сетей с произвольной топологией. Впервые как отдельный алгоритм он был представлен Ченемв работе [41] и поэтому иногда называется алгоритмом Ченя.
Несколько болееэффективная версия была предложена Сигаллом [174] , и мы рассмотрим здесьименно ее.Алгоритм наводняет сообщениями tok все процессы, выделяя таким образомостовное дерево, как это было определено в лемме 6.3. Маркеры возвращаются«эхом» обратно по ребрам этого дерева, напоминая поток сообщений в древесном алгоритме (см. алгоритм 6.4). Инициатор отправляет сообщение всем своимсоседям. После получения первого сообщения всякий неинициатор переправляетсообщения всем своим соседям, за исключением того, от которого было полученоэто сообщение. Как только неинициатор получит сообщения от всех своих соседей, он отправляет эхо родительскому процессу.
Как только инициатор получитсообщения от всех своих соседей, он принимает решение.var recp: integer init 0 ; (* Подсчет числа полученных сообщений *)fatherp : Pinit undef ;Для инициатора:begin forall q ∈ Neighp do send htoki to q ;while recp < #Neighp dobegin receive htoki ; recp := recp + 1 end;decideendДля неинициатора:begin receive htoki from neighbor q ; fatherp := q ; recp := recp + 1 ;forall q ∈ Neighp , q 6= fatherp do send htoki to q ;while recp < #Neighp dobegin receive htoki ; recp := recp + 1 end;send htoki to fatherpendАлгоритм 6.4. Алгоритм эхаТеорема 6.17. Алгоритм эха (алгоритм 6.4) является волновым алгоритмом.Д о к а з а т е л ь с т в о. Поскольку каждый процесс отправляет не болееодного сообщения по инцидентному каналу, число сообщений, которыми обмениваются процессы на протяжении одного вычисления, конечно.
Пусть — заключительная конфигурация, которая достигается при вычислении C с инициатором p0 .6.2. Семейство волновых алгоритмов207Для этой конфигурации определим (так же, как в лемме 6.3) граф T = (P, E T),полагая pq ∈ ET ⇐⇒ fatherp = q. Чтобы показать, что этот граф являетсядеревом, необходимо установить, что число ребер меньше числа вершин на единицу (лемма 6.3 утверждает, что T — дерево, но исходя из предположения о том,что используемый алгоритм — волновой, а это как раз то, что нам здесь нужнодоказать). Заметим, что каждый процесс, участвующий в C, отправляет сообщения всем своим соседям, за исключением (если только этот процесс не являетсяинициатором) того соседа, от которого было получено первое сообщение.
Значит,каждый его сосед получит хотя бы одно сообщение в C и также примет участиев C. Отсюда следует, что fatherp 6= udef для всех p 6= p0 . То, что T не содержитциклов, было показано в доказательстве леммы 6.3.Корнем дерева служит вершина p0 . Обозначим символом Tp множество вершин поддерева, растущего из вершины p. Ребра сети, не принадлежащие T, назовем стягивающими. В конфигурации каждый процесс p обязательно долженотправить сообщения всем своим соседям, за исключением родительской вершины fatherp , и, следовательно, в ходе вычисления C по каждому стягивающемуребру должно передаваться сообщение в обе стороны. Обозначим символом f pсобытие отправления процессом p сообщения родительской вершине (если таковое случается в C), а символом gp — событие получения процессом fatherpсообщения от p (если это происходит).
Индукцией по числу вершин дерева можно показать, что1) C содержит событие fp для каждого p 6= p0 ;2) для всех s ∈ Tp есть такое e ∈ Cs , что e gp .Мы рассмотрим следующие два случая.Процесс p — это листовая вершина. Процесс p в вычислении C уже получил сообщение от своей родительской вершины и от всех своих соседей (поскольку все прочие каналы являются стягивающими ребрами).
Значит, он могсовершить отправление сообщения tok процессу father p . Коль скоро является заключительной конфигурацией, это сообщение было отправлено. Дерево T pсодержит одну лишь вершину p, и, очевидно, f p gp .Процесс p не является листовой вершиной. Процесс p в C уже получилсообщение от родительской вершины, а также по всем стягивающим ребрам.
Поиндуктивной гипотезе в вычислении C для каждой сыновней вершины p 0 процессаp представлено событие fp0 . Коль скоро — это заключительная конфигурация,вычисление C содержит также и событие gp0 . Следовательно, событие отправления сообщения tok процессу fatherp имеет все предпосылки, для того чтобыосуществиться. И поскольку конфигурация является заключительной, это сообщение было отправлено.
Дерево Tp содержит объединение деревьев Tp0 по всемсыновним вершинам процесса p и саму вершину p. Применив индуктивную гипотезу, можно показать, что в каждом процессе из этого множества есть событие,предшествующее gp .Отсюда также следует, что процесс p0 уже получил сообщение от каждогосвоего соседа и что p0 осуществил событие decide, которому предшествует хотябы одно событие в каждом из процессов.208Гл. 6.Волновые алгоритмы и алгоритмы обходаОстовное дерево, построенное в ходе вычисления алгоритма 6.4, иногда используется последующими алгоритмами. Например, алгоритм Мерлина —Сигалла для вычисления таблицы маршрутизации по кратчайшим путям исходит изпредположения о том, что остовное дерево с корнем в v 0 уже задано; см. § 4.2.3.Это исходное остовное дерево может быть вычислено при помощи алгоритма эха.В последней конфигурации алгоритма каждый процесс (отличный от p 0) запоминает, кто из соседей является его родительской вершиной, но своих сыновнихвершин среди соседей он в этом дереве не различает.
В нашем алгоритме однои то же сообщение поступает от родительской вершины по стягивающим ребрам,а также от сыновних вершин. Если требуются сведения о сыновних вершинахв построенном дереве, алгоритм нужно чуть-чуть видоизменить так, чтобы сообщение, отправляемое родительской вершине (последняя операция отправлениясообщения для неинициаторов), было особым. Сыновними вершинами процессабудут признаны те соседи, от которых поступило особое сообщение.6.2.4. Алгоритм опросаВ сети, образующей клику, каждая пара процессов соединена каналом.
Всякий процесс может судить о том, получил ли он сообщение от каждого своегососеда. В алгоритме опроса (см. 6.5) инициатор обращается к каждому соседус просьбой отправить ему сообщение и принимает решение после получения всехсообщений.var recp: integerinit 0 ;(* только для инициатора *)Для инициатора:begin forall q ∈ Neighp do send htoki to qf ;while recp < #Neighp dobegin receive htoki ; recp := recp + 1 end;decideendДля неинициатора:begin receive htoki from q ; send tok to q endАлгоритм 6.5. Алгоритм опросаТеорема 6.18. Алгоритм опроса (алгоритм 6.5) является волновым алгоритмом.Д о к а з а т е л ь с т в о.
В этом алгоритме по каждому каналу, инцидентному инициатору, отправляются два сообщения. Каждый сосед инициатора отвечаетодин раз на полученный запрос, и, следовательно, инициатор получает N − 1 откликов. Это как раз то число, которое необходимо для принятия решения, и от-6.2. Семейство волновых алгоритмов209сюда следует, что инициатор примет решение, и этому решению предшествуетнекоторое событие в каждом из процессов.Опрос можно проводить также и в звездных сетях, если инициатор будетрасполагаться в центре.6.2.5.
Фазовый алгоритмВ этом параграфе будет представлен фазовый алгоритм, который является децентрализованным алгоритмом, пригодным для сетей с произвольной топологией.Этот алгоритм был предложен в работе [187, § 4.2.3] . Его можно использоватьв качестве волнового алгоритма для ориентированных сетей.В этом алгоритме требуется, чтобы все процессы располагали сведениямио диаметре сети, который обозначен константой D в тексте описания алгоритма. Алгоритм будет оставаться корректным (хотя и менее эффективным), есливсе процессы будут использовать вместо D константу D 0 , превышающую диаметр сети.
Таким образом, для применения фазового алгоритма не нужно знатьточного значения диаметра; достаточно, если будет известна верхняя оценка (например, N − 1) диаметра сети. Во всех процессах должна использоваться однаи та же константа D0 . Пелег в работе [158] расширил этот алгоритм так, чтобыдиаметр вычислялся по ходу выполнения алгоритма, но в этом случае требуетсяоднозначная идентифицируемость процессов.Общий случай. Алгоритм можно применять для всякой ориентированнойсети, по каналам которой осуществляется односторонняя передача сообщений. Вэтом случае соседями вершины p будут соседи на входе (т.
е. процессы, которыемогут отправлять сообщения процессу p) и соседи на выходе (т. е. процессы,которым p может отправлять сообщения). Соседи процесса p на входе образуютмножество Inp , а соседи на выходе — множество Outp .В фазовом алгоритме всякий процесс отправляет в точности D сообщенийкаждому соседу на выходе. При этом (i + 1)-е сообщение отправляется каждомусоседу на выходе только после того, как были получены i сообщений от каждогососеда на входе (см.
алгоритм 6.6).И в самом деле, из описания алгоритма сразу видно, что по каждому каналу передается не более D сообщений (то, что по каждому каналу передаетсяне менее D сообщений, мы покажем ниже). Для каждого ребра pq выражение(i)fpq будет обозначать i-е событие отправления процессом p сообщения процессу(i)q, а выражение gpq будет обозначать i-е событие приема процессом q сообщения от процесса p. Если канал связи между процессами p и q имеет тип очереди (first in – first out), эти события соответствуют друг другу, и соотношение(i)(i)(i)fpq gpq , очевидно, выполняется. Причинно-следственные отношения между fpq(i)и gpq соблюдаются и в тех случаях, когда канал не является очередью, о чемсвидетельствует следующая лемма.(i)(i) gpqсоблюдается и тогда, когда каналЛемма 6.19.
Соотношение fpqне является очередью.210Гл. 6.cons Dvar Recp [q]Sentp6.2. Семейство волновых алгоритмовВолновые алгоритмы и алгоритмы обхода: integer= диаметр сети ;: 0..Dinit 0 для каждого q ∈ Inp ;(* Число сообщений, полученных от q *): 0..Dinit 0 ;(* Число сообщений, отправленных каждому соседу на выходе *)begin if p is initiator thenbegin forall r ∈ Outp do send htoki to r ;Sentp := Sentp + 1end;while minq Recp [q] < D dobegin receive htoki (from neighbor q0) ;Recp [q0 ] := Recp [q0 ] + 1 ;if minq Recp [q] > Sentp and Sentp < D thenbegin forall r ∈ Outp do send htoki to r ;Sentp := Sentp + 1endend;decideend211им получено, имеем Recp [q] > 0 =⇒ Sentp > 0. Тогда исходя из предположения о существовании хотя бы одного инициатора p 0 , для которого Sentp0 > 0,приходим к выводу о том, что Sentp > 0 для каждого p.Далее будет показано, что каждый процесс принял решение.
Рассмотрим процесс p, у которого в конфигурации переменная Sent имеет наименьшее значение, т. е. в для всех q выполняется неравенство Sent q > Sentp . В частности, это неравенство справедливо для процесса q, являющегося соседом процесса p на входе, и тогда из равенства Recp [q] = Sentq вытекает неравенствоminq Recp [q] > Sentp . Но это означает, что Sentp = D; в противном случаепроцесс p пришлось бы отправлять дополнительное сообщение, как только онв последний раз получил некоторое сообщение. Значит, Sent p = D для всех p, и,следовательно, для всех каналов qp имеет место равенство Rec p [q] = D. Отсюдазаключаем, что каждый процесс принял решение.Остается показать, что всякому решению предшествует хотя бы одно событиев каждом из процессов. Рассмотрим путь в сети P = p 0 , p1 , . .
. , pl , где l 6 D.Тогда по лемме 6.19 соотношениеfp(ii+pi1)+1 gp(ii+pi1)+1справедливо для любого i, 0 6 i < l, и в соответствии с описанием алгоритмасоотношениеАлгоритм 6.6. Фазовый алгоритм2)gp(ii+pi1)+1 fp(ii++1 pi+2(m )Д о к а з а т е л ь с т в о. Допустим, что число mh таково, что fpq h — это со(h)бытие отправления сообщения, которое соответствует g pq , т. е. при выполненииh-го события приема процесс q получает mh -е сообщение от p. По определению(mh)(h)причинно-следственной зависимости мы имеем fpq gpq.Поскольку каждое сообщение на протяжении вычисления C принимается однократно, все mh различны, откуда следует, что хотя бы одно из чисел m 1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
