Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 60
Текст из файла (страница 60)
Рассмотрим путь, по которому следовалмаркер, до тех пор пока он не был отправлен по ребру pq. Коль скоро pq —стягивающее ребро, маркер уже побывал в вершине q до того момента, когда ондостиг q по указанному ребру:. . . , q, . . . , p, q.Образуем из рассматриваемого пути как можно более короткий путь, заменяя всефрагменты вида r1 , r2 , r1 , где r1 r2 — стягивающее ребро, фрагментом r1 .
Согласноприведенным выше соображениям все стягивающие ребра будут таким образомудалены. Отсюда следует, что полученный в результате путь будет путем в T,состоящим только из ребер, использованных прежде первого обращения к pq.Если q не относится к числу предшественников процесса p, то это означает,что ребро из q в fatherq было задействовано ранее, нежели было использованоребро qp, вопреки правилу R2 нашего алгоритма.Сложность по числу сообщений классического распределенного поиска в глубину равна 2|E|, и, как следует из теоремы 6.6, эта оценка является оптимальной(с точностью до постоянного множителя 2), если только отличительные признакисоседей заранее неизвестны.
Сложность по времени также равна 2|E|, и это наилучшее из того, что могут в этом случае дать алгоритмы обхода (см. лемму 6.32).Распределенный вариант поиска в глубину был впервые предложен Чуном [51] .В § 6.4.2 будут рассмотрены два алгоритма, позволяющие строить в сети дерево поиска в глубину без предварительных сведений об отличительных признакахсоседей за O(N) единиц времени.
Ясно, что эти алгоритмы не являются алгоритмами обхода. В § 6.4.3 мы покажем, как можно воспользоваться сведениями оботличительных признаках соседей, чтобы построить алгоритм, у которого сложность по числу обменов сообщениями и по времени равна O(N).6.4.2.
Алгоритмы поиска в глубину, требующие линейноговремениКлассический алгоритм поиска в глубину имеет большую сложность по времени, потому что все ребра сети, как стягивающие ребра, так и ребра, входя-224Гл. 6.6.4. Сложность по времени: поиск в глубинуВолновые алгоритмы и алгоритмы обходащие в дерево, обходятся последовательно. Как показано в доказательстве теоремы 6.33, маркер-сообщение tok обходит все стягивающие ребра и немедленновозвращается. Всякое решение, приводящее к более низкой сложности по времени, основывается на том соображении, что маркер-сообщение проходит толькопо ребрам, входящим в дерево. Ясно, что для этого потребуется линейное время,ибо в дереве имеется всего N − 1 ребер.Решение Авербаха.
В наш алгоритм теперь будет включен механизм, предотвращающий передачу маркера по стягивающим ребрам. В алгоритме Авербаха[13] это обеспечивается тем, что каждый процесс в тот момент, когда он долженпередать маркер, обладает сведениями о том, у какого из его соседей уже побывал маркер. Тогда процесс либо выбирает какого-нибудь соседа, не получавшегодо сих пор маркер, либо возвращает маркер в родительскую вершину, если такогососеда нет.Когда маркер впервые достается процессу p (для инициатора это происходитв момент запуска алгоритма), p оповещает об этом событии каждого своего соседа r, за исключением родительской вершины, отправляя ему сообщение hvisi.Передача маркера приостанавливается, до тех пор пока p не получит сообщение hacki от всех своих соседей.
Это служит гарантией того, что каждый сосед rпроцесса p осведомлен к моменту отправления маркера процессом p о том, чтоэтот маркер уже побывал у p. Когда позднее маркер достигнет r, процесс r ужене будет отправлять маркер процессу p, если только p не является родительскойвершиной для r (см. алгоритм 6.14).var usedp [q]fatherp225: boolinit false for each q ∈ Neighp ;(*Указывает, отправлял ли p маркер процессу q*): process init udef ;Только для инициатора, выполнить один раз:begin fatherp := p ; choose q ∈ Neighp ;forall r ∈ Neighp do send hvisi to r ;forall r ∈ Neighp do receive hacki from r ;usedp [q] := true ; send htoki to qendДля каждого процесса после получения htoki от q0 :begin if fatherp = udef thenbegin fatherp := q0 ;forall r ∈ Neighp \ {fatherp } do send hvisi to r ;forall r ∈ Neighp \ {fatherp } do receive hacki from rend;if p is the initiator and ∀q ∈ Neighp : usedp [q]then decideelse if ∃q ∈ Neighp : (q 6= fatherp ∧ ¬usedp [q])then begin if fatherp 6= q0 ∧ ¬usedp [q0 ]then q := q0else choose q ∈ Neighp \ {fatherp } with ¬usedp [q] ;usedp [q] := true ; send htoki to qendelse begin usedp [fatherp ] := true ; send htoki to fatherp endendДля каждого процесса после получения hvisi от q0 :begin usedp [q0 ] := true ; send hacki to q0 endАлгоритм 6.14.
Алгоритм Авербаха поиска в глубинуОбмен сообщениями часто приводит к тому, что элементу массива used p [fatherp ]присваивается значение true, даже когда процесс p еще не отправлял маркерв свою родительскую вершину. Поэтому в алгоритме должно быть явно указано, что решение может принимать только инициатор; неинициатор p, у которогоusedp [q] имеет значение true для всех соседей q, отправляет маркер в свою родительскую вершину.Теорема 6.34.
Алгоритм Авербаха (алгоритм 6.14) строит дерево поиска в глубину за 4N − 2 единиц времени, проводя при этом 4|E| обменовсообщениями.Д о к а з а т е л ь с т в о. Маркер пересылается в точности по тем же каналам, что и в алгоритме 6.13, за исключением стягивающих ребер — по ним передачи маркера не происходит. Поскольку передачи по стягивающим ребрам невлияют на окончательное значение fatherp для каждого процесса p, полученное226Гл. 6.Волновые алгоритмы и алгоритмы обходав результате дерево всегда будет совпадать с одним из возможных результатовалгоритма 6.13.
Маркер проходит последовательно в обе стороны по N − 1 ребрам дерева, и для этого требуется 2N − 2 единиц времени. В каждой вершинедвижение маркера приостанавливается не более одного раза для обмена сообщениями vis/ack и это приводит к задержке в каждой вершине на две единицывремени.По каждому стягивающему ребру проходят два сообщения vis и два сообщения ack.
По каждому ребру дерева передаются два сообщения tok, одно сообщение vis (от родительской вершины к ее преемнику) и одно сообщение ack (кродительской вершине от ее преемника). Следовательно, происходит обмен 4|E|сообщениями.Отправление сообщения vis тем соседям, которым процесс собирается передать маркер, может быть опущено. Это улучшение (оно не приведено в алгоритме 6.14) позволяет сэкономить по два сообщения на каждом ребре дерева и,следовательно, сокращает сложность по числу обменов сообщениями на 2N − 2сообщения.var usedp [q]fatherpmrsp: boolinit false for each q ∈ Neighp ;(* Указывает, отправлял ли p маркер процессу q *): process init udef ;: process init udef ;Только для инициатора, выполнить один раз:begin fatherp := p ; choose q ∈ Neighp ;forall r ∈ Neighp do send vis to r ;usedp [q] := true ; mrsp := q ; send tok to qendДля каждого процесса после получения vis от q0 :begin usedp [q0 ] := true ;if q0 = mrsp then (* Истолковывать как сообщение tok *)forward tok message as upon receipt of tok messageendАлгоритм 6.15.
Алгоритм Сидон поиска в глубину (Часть 1)Решение Сидона. В алгоритме Сидона [53] , в отличие от алгоритма Авербаха, не отправляются сообщения ack, и за счет этого улучшается сложность повремени. В модифицированном алгоритме Сидона маркер отправляется немедленно, т. е. без той задержки на две единицы времени, которая введена в алгоритме Авербаха для ожидания подтверждений. Тот же самый алгоритм былпредложен Лакшмананом и др. [123] . В алгоритме Сидона возможно возникновение следующей ситуации.
В процессе p уже побывал маркер, и этот процессуже отправил сообщение vis своему соседу r. Позднее маркер достается процессу r, но в тот момент, когда r получает маркер, сообщение vis от p еще не6.4. Сложность по времени: поиск в глубину227Для каждого процесса после получения tok от q0 :begin if mrsp 6= udef and mrsp 6= q0(* Это стягивающее ребро, истолковывать как сообщение vis *)then usedp [q0 ] := trueelse(* Поступать, как в предыдущем алгоритме *)begin if fatherp = udef thenbegin fatherp := q0 ;forall r ∈ Neighp \ {fatherp } dosend vis to rend ;if p — инициатор and ∀q ∈ Neighp : usedp [q]then decideelse if ∃q ∈ Neighp : (q 6= fatherp ∧ ¬usedp [q])then begin if fatherp 6= q0 ∧ ¬usedp [q0 ]then q := q0else choose q ∈ Neighp \ {fatherp }with ¬usedp [q] ;usedp [q] := true ; mrsp := q ;send tok to qendelse begin usedp [fatherp ] := true ;send tok to fatherpendendendАлгоритм 6.16.
Алгоритм Сидона поиск в глубину (Часть 2)достигло r. В таком случае r может передать маркер процессу p, отправляя его,таким образом, по стягивающему ребру. (Обратите внимание на то, как сообщения ack в алгоритме Авербаха предотвращают подобный сценарий развитиясобытий.)Чтобы справиться с такой ситуацией, процесс p записывает (в переменнуюmrsp) тех соседей, которым он в последнюю очередь отправлял маркер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
