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

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

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

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

Такаяединица времени будет задаваться аксиомой, гласящей, что задержка переда­чи всякого сообщения ограничена этой единицей времени. Поэтому изложенныйниже тезис Т2 нужно в действительности рассматривать не как допущение о вы­числении, а как утверждение об этой единице времени.Определение 6.31. Сложностью по времени для распределенного алго­ритма называется наибольшее время, которое требуется для выполнения произ­вольного вычисления этого алгоритма с учетом следующих допущений.Т1. Во всяком процессе любое конечное число событий может осуществитьсямгновенно (за время 0 ).Т2. Период времени между отправлением и получением одного и того же со­общения не превышает одной единицы времени.Сложность по времени для всех волновых алгоритмов, описанных в этой гла­ве, приведена в таблице 6.18.

Мы не приводим обоснования тех значений, кото­рые указаны в таблице; читателю предлагается в качестве упражнения проверитьэти значения самостоятельно. Альтернативные определения сложности по вре­мени будут обсуждаются в §6.5.3.Лемма 6.32. Для алгоритмов обхода сложность по времени равна слож­ности по числу сообщений.Гл. 6.222Волновые алгоритмы и алгоритмы обходаД о к а з а т е л ь с т в о .

Обмен сообщениями осуществляется последователь­но, и для каждого обмена может потребоваться одна единица времени.□6.4.1. Распределенный поиск в глубинуКлассический алгоритм поиска в глубину получается из алгоритма Тарри,в котором свобода выбора очередного соседа для передачи ему маркера огра­ничена третьим правилом следующего вида (см. алгоритм 6.13).R3. Всякий раз, когда процесс получает маркер, он возвращает его назад потому же каналу, если это не противоречит правилам R1 и R2.var usedp[q]fatherрfalse for each q € Neighp ;(* Указывает, отправлял ли p маркер процессу: process init u d e f ;: boolinitТолько для инициатора, выполнить один раз:begin fatherр := р ; choose q 6 Neighpusedp[q] := true ; send toktoq *);qendtok от q$\begin if fatherp = udef then father,, := qo ;if V<7 6 Neighp : usedp[q] then decideelse if 3<7 € Neighp : (q Ф fatherp A ~^usedp[q])then begin if fatherp ф qo A ~^usedp[qo\ then q := qaelse choose q € Neighp \ {fatherp}with -iusedp[q]) ;usedp[q] := true ; send tok to qendelse begin usedp[fatherp] := true ;send tok to fatherpendendДля каждого процесса, при полученииАлгоритм 6.13.

Классический алгоритм поиска в глубинуТеорема 6.33. Классический алгоритм поиска в глубину (алгоритм 6.13)строит остовное дерево поиска в глубину за 2 |£| единиц времени, исполь­зуя при этом 2\Е\ обменов сообщениями.Д о к а з а т е л ь с т в о .

Поскольку в основу нашего алгоритма положен ал­горитм Тарри, мы имеем дело с алгоритмом обхода, который вычисляет остовноедерево Т. Как было уже установлено, по каждому каналу передаются два сооб­щения (по одному в каждом направлении), и это служит обоснованием сложностипо числу сообщений. А сложность по времени равна 2|£|, поскольку обмен со­общениями проводится поочередно и каждый обмен требует не более одной еди­6.4. Сложность по времени-, поиск в глубину223ницы времени. Остается убедиться в том, что дерево, построенное в результатеприменения правила R3, будет деревом поиска в глубину.Во-первых, согласно правилу R3 вслед за первым прохождением по стяги­вающему ребру немедленно следует повторное прохождение в обратном направ­лении. Предположим, что pq — это стягивающее ребро и р является первымпроцессом, воспользовавшимся этим стягивающим ребром.

К тому моменту, ко­гда процесс q получает маркер от р, этот маркер уже побывал в q (в противномслучае процесс q занес бы в переменную fatherq ссылку па р и наше ребро немогло бы считаться стягивающим) и usedq[p] имеет значение false (посколькупо предположению процесс р был первым из этих двух процессов, воспользо­вавшимся указанным ребром). Следовательно, согласно правилу R3, процесс qнемедленно возвращает маркер процессу р.Теперь можно показать, что если ребро pq является стягивающим и его впер­вые использовал процесс р, то q &А[р\.

Рассмотрим путь, по которому следовалмаркер, до тех пор пока он не был отправлен по ребру pq. Коль скоро pq —стягивающее ребро, маркер уже побывал в вершине q до того момента, когда ондостиг q по указанному ребру:q,р, q.Образуем из рассматриваемого пути как можно более короткий путь, заменяя всефрагменты вида г\, г2, г \ , где г\ г2 — стягивающее ребро, фрагментом г\. Согласноприведенным выше соображениям все стягивающие ребра будут таким образомудалены. Отсюда следует, что полученный в результате путь будет путем в Т,состоящим только из ребер, использованных прежде первого обращения к pq.Если q не относится к числу предшественников процесса р, то это означает,что ребро из q в fatherq было задействовано ранее, нежели было использованоребро qp, вопреки правилу R2 нашего алгоритма.□Сложность по числу сообщений классического распределенного поиска в глу­бину равна 2 |£|, и, как следует из теоремы 6 .6 , эта оценка является оптимальной(с точностью до постоянного множителя 2 ), если только отличительные признакисоседей заранее неизвестны.

Сложность по времени также равна 2|£|, и это наи­лучшее из того, что могут в этом случае дать алгоритмы обхода (см. лемму 6.32).Распределенный вариант поиска в глубину был впервые предложен Чуном [51].В § 6.4.2 будут рассмотрены два алгоритма, позволяющие строить в сети дере­во поиска в глубину без предварительных сведений об отличительных признакахсоседей за 0(N) единиц времени.

Ясно, что эти алгоритмы не являются алгорит­мами обхода. В §6.4.3 мы покажем, как можно воспользоваться сведениями оботличительных признаках соседей, чтобы построить алгоритм, у которого слож­ность по числу обменов сообщениями и по времени равна 0(N).6.4.2. Алгоритмы поиска в глубину, требующие линейноговремениКлассический алгоритм поиска в глубину имеет большую сложность по вре­мени, потому что все ребра сети, как стягивающие ребра, так и ребра, входя­224Гл. 6.Волновые алгоритмы и алгоритмы обходащие в дерево, обходятся последовательно. Как показано в доказательстве тео­ремы 6.33, маркер-сообщение tok обходит все стягивающие ребра и немедленновозвращается.

Всякое решение, приводящее к более низкой сложности по време­ни, основывается на том соображении, что маркер-сообщение проходит толькопо ребрам, входящим в дерево. Ясно, что для этого потребуется линейное время,ибо в дереве имеется всего N — 1 ребер.Решение Авербаха. В наш алгоритм теперь будет включен механизм, предот­вращающий передачу маркера по стягивающим ребрам. В алгоритме Авербаха[13] это обеспечивается тем, что каждый процесс в тот момент, когда он долженпередать маркер, обладает сведениями о том, у какого из его соседей уже побы­вал маркер. Тогда процесс либо выбирает какого-нибудь соседа, не получавшегодо сих пор маркер, либо возвращает маркер в родительскую вершину, если такогососеда нет.Когда маркер впервые достается процессу р (для инициатора это происходитв момент запуска алгоритма), р оповещает об этом событии каждого своего со­седа г, за исключением родительской вершины, отправляя ему сообщение (vis).Передача маркера приостанавливается, до тех пор пока р не получит сообще­ние (аск) от всех своих соседей.

Это служит гарантией того, что каждый сосед гпроцесса р осведомлен к моменту отправления маркера процессом р о том, чтоэтот маркер уже побывал у р. Когда позднее маркер достигнет г, процесс г ужене будет отправлять маркер процессу р, если только р не является родительскойвершиной для г (см. алгоритм 6.14).2256.4.

Сложность по времени: поиск в глубинуvar usedP[q]fatherpfor each q € Neighp ;(“'Указывает, отправлял ли p маркер процессу: process init u d e f;'■boolinit falseq*)Только для инициатора, выполнить один раз:begin fatherp := р ; choose q е Neighp ;forall r e Neighp do send (vis) to r ;forall r e Neighp do receive (ack) from r ;usedp[q] := true ; send (tok) to qend(tok) от qo'.begin if fatherp = udef thenbegin fatherp := qo ;forall r e Neighp \ {fatherp} do send (vis) to r ;forall r e Neighp \ {fatherp} do receive (ack) from rend;if p is the initiator and Vq € Neighp : usedp[q]then decideelse if 3q € Neighp : (q ф fatherp A -iusedp[q\)then begin if fatherp Ф q0 A ^usedp[qo]then q := qoelse choose q € Neighp \ {fatherp} with ^usedp[q\Для каждого процесса после полученияusedp[q] := true; send (tok) toendelse begin usedp[fatherp] := true;q; send (tok) tofatherp endendДля каждого процесса после получения (vis) от q0:begin usedp[qo] := true ; send (ack) to q0 endАлгоритм 6.14.

Алгоритм Авербаха поиска в глубинуОбмен сообщениями часто приводит к тому, что элементу массива usedp[fatherp]присваивается значение true, даже когда процесс р еще не отправлял маркерв свою родительскую вершину. Поэтому в алгоритме должно быть явно указа­но, что решение может принимать только инициатор; неинициатор р, у которогоusedp[q] имеет значение true для всех соседей q, отправляет маркер в свою ро­дительскую вершину.Теорема 6.34.

Алгоритм Авербаха (алгоритм 6.14) строит дерево по­иска в глубину за AN — 2 единиц времени, проводя при этом 4|£| обменовсообщениями.Д о к а з а т е л ь с т в о . Маркер пересылается в точности по тем же кана­лам, что и в алгоритме 6.13, за исключением стягивающих ребер — по ним пе­редачи маркера не происходит. Поскольку передачи по стягивающим ребрам невлияют на окончательное значение fatherр для каждого процесса р, полученноеГл.

6.226Волновые алгоритмы и алгоритмы обходав результате дерево всегда будет совпадать с одним из возможных результатовалгоритма 6.13. Маркер проходит последовательно в обе стороны по N —1 реб­рам дерева, и для этого требуется 2N —2 единиц времени. В каждой вершинедвижение маркера приостанавливается не более одного раза для обмена сооб­щениями vis/ack и это приводит к задержке в каждой вершине на две единицывремени.По каждому стягивающему ребру проходят два сообщения vis и два сообще­ния аск.

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

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