Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 59
Текст из файла (страница 59)
. . , 2 n },что l(k) = i, мы заключаем, что p0 = p2n и решение принимается инициатором.Проводя рассуждения, сходные с теми, которые применялись для доказательстватеоремы 6.27, приходим к выводу о том, что равенство p a = pb влечет условие2n | (b − a). Отсюда следует, что все процессы p0 , . . . , p2n −1 попарно различны.Таким образом, к моменту завершения вычисления маркеру удалось посетитьвсе процессы. При этом, совершив x переходов, маркеру удается посетить x + 1процессов.6.3.4. Обход связных сетейАлгоритм обхода произвольных связных сетей был предложен Тарри в 1895;см. [183] . Этот алгоритм определяется двумя следующими правилами (см.
алгоритм 6.12).R1. Процесс не передает маркер по одному и тому же каналу дважды.219init false for each q ∈ Neighp ;(* Показывает, отправлял ли p сообщение процессу q *): process init udef ;Только для инициатора, выполнить один раз:begin fatherp := p ; choose q ∈ Neighp ;usedp [q] := true ; send tok to qendДля каждого процесса после приема tok от q0 :begin if fatherp = udef then fatherp := q0 ;if ∀q ∈ Neighp : usedp [q] then decideelse if ∃q ∈ Neighp : (q 6= fatherp ∧ ¬usedp [q])then begin choose q ∈ Neighp \ {fatherp }with ¬usedp [q] ;usedp [q] := true ; send tok to qendelse begin usedp [fatherp ] := true ;send tok to fatherpendendАлгоритм 6.12.
Алгоритм обхода ТарриТеорема 6.29. Алгоритм Тарри (алгоритм 6.12) является алгоритмомобхода.Д о к а з а т е л ь с т в о. Так как маркер передается не более чем по одномуразу в каждом из двух направлений по любому каналу, он совершает не более 2|E|переходов, пока алгоритм не завершится. Поскольку каждый процесс отправляетмаркер по каждому каналу не более одного раза, он его и получает по каждомуканалу не более одного раза.
Всякий раз, когда маркером владеет неинициатор p,это означает, что процессу p пришлось получать маркер на один раз больше, чемотправлять его. Отсюда следует, что число каналов, инцидентных p, превосходитчисло каналов, использованных этим процессом, по крайней мере на 1, и поэтомуp не принимает решения, а передает маркер. Значит, решение может принятьтолько инициатор.Далее мы обоснуем три тезиса, из которых следует, что всякий раз, когдаалгоритм завершает работу, каждому процессу пришлось участвовать в передачемаркера.1. Все каналы, инцидентные инициатору, были использованы по одному разу в каждом направлении.
Каждый канал был использован инициатором220Гл. 6.Волновые алгоритмы и алгоритмы обходадля передачи маркера, ибо в противном случае алгоритм не завершается. Инициатору пришлось получать маркер столько же раз, сколько и отправлять его.А поскольку получать его приходилось по разным каналам, маркер был полученпо одному разу с использованием каждого канала.2. Для каждого посещенного маркером процесса p все каналы, инцидентные p, были использованы для передачи маркера в каждом направлении по одному разу.
Предположим, что это не так. Пусть p — самый первый изпосещенных маркером процессов, для которого не выполняется это предположение. Заметим, что согласно тезису 1). таким процессом не может быть инициатор.Согласно выбору p все каналы, инцидентные father p , были использованы по одному разу в каждом направлении. Отсюда следует, что p уже отправил маркерв родительскую вершину. Но это означает, что p использовал все инцидентныеканалы для отправления маркера.
А поскольку маркер вернулся к инициатору, процессу p пришлось получать его столь же часто, сколь и отправлять. Нов таком случае по каждому инцидентному каналу процесс p получал маркер поодному разу. А это противоречит сделанному предположению.3. Маркер посетил все процессы и передавался по каждому каналув обоих направлениях. Если бы нашлись процессы, которые маркеру не удалосьпосетить, то это означало бы, что для некоторой пары соседних процессов p и qмаркеру удалось побывать в p, но не удалось посетить q. Но это противоречиттому, что процессу p пришлось использовать каждый канал в обоих направлениях. Значит, маркер побывал во всех процессах, и все каналы были задействованыпо одному разу в каждом направлении согласно тезису 2).Каждое вычисление алгоритма Тарри задает в сети остовное дерево, о чемсвидетельствует лемма 6.3.
Корнем дерева служит инициатор, и каждый неинициатор p к моменту завершения вычисления уже заносит в переменную father pссылку на родительскую вершину в этом дереве. Если требуется, чтобы каждыйпроцесс обладал (к моменту завершения вычисления) сведениями о том, какиеиз его соседей являются сыновними вершинами в этом дереве, то этого можнодостичь, отправляя специальное сообщение процессу father p .6.4. Сложность по времени: поиск в глубинуПроцессам в алгоритме Тарри предоставлена достаточная свобода выборасоседей, которым нужно передать маркер, и в результате может образоватьсябольшой класс остовных деревьев.
В этом параграфе мы рассмотрим алгоритмы построения таких остовных деревьев, что в них каждое стягивающее ребро соединяет две вершины, одна из которых выступает в роли предшественникадругой. Стягивающее ребро — это ребро, не принадлежащее остовному дереву.Для заданного остовного дерева T сети G и для каждой его вершины p мы будем использовать запись T [p] для обозначения множества процессов поддерева,растущего из p, а запись A [p] — для обозначения множества предшественников p, т.
е. вершин, лежащих в дереве T на пути из корня в p. Заметим, чтоq ∈ T [p] ⇐⇒ p ∈ A [q] .6.4. Сложность по времени: поиск в глубину221Определение 6.30. Корневое остовное дерево T сети G называется деревом поиска в глубину, если для каждого стягивающего ребра pq выполняетсясоотношение q ∈ T [p] ∨ q ∈ A [p] .Деревья поиска в глубину применяются во многих графовых алгоритмах, наподобие проверки планарности, проверки двусвязности, построения интервальныхсхем разметки (см. § 4.4.2). В § 6.4.1 будет показано, что незначительная модификация алгоритма Тарри (связанная с ограничением свободы выбора процессов)позволяет применять его для построения деревьев поиска в глубину.
Полученныйтаким образом алгоритм мы назовем классическим алгоритмом поиска в глубину. В § 6.4.2 будут рассмотрены два алгоритма, позволяющие строить деревьяпоиска в глубину за меньшее время по сравнению с классическим алгоритмом.Для распределенных алгоритмов понятие сложности по времени будет определено ниже.
В § 6.4.3 будет предложен алгоритм поиска в глубину для сетей приналичии предварительных сведений об отличительных признаках соседей. В этомслучае теорема 6.6 уже будет не применима, и по сути дела можно построитьалгоритм, использующий всего лишь 2N − 2 сообщений.Сложность по времени для распределенных алгоритмов. Время, котороетребуется для передачи сообщения в асинхронных сетях, заранее не известно,и нам не хотелось бы ставить наши методы анализа в зависимость от параметров отдельных систем.
Нужно вспомнить, что в последовательных вычисленияхсложность по времени не измеряется в единицах физического времени, а определяется числом выполненных команд. Здесь мы проделаем то же самое. В качестве единицы измерения продолжительности распределенного вычисления возьмем самую большую задержку передачи сообщения в ходе вычисления. Такаяединица времени будет задаваться аксиомой, гласящей, что задержка передачи всякого сообщения ограничена этой единицей времени.
Поэтому изложенныйниже тезис T2 нужно в действительности рассматривать не как допущение о вычислении, а как утверждение об этой единице времени.Определение 6.31. Сложностью по времени для распределенного алгоритма называется наибольшее время, которое требуется для выполнения произвольного вычисления этого алгоритма с учетом следующих допущений.T1. Во всяком процессе любое конечное число событий может осуществитьсямгновенно (за время 0).T2.
Период времени между отправлением и получением одного и того же сообщения не превышает одной единицы времени.Сложность по времени для всех волновых алгоритмов, описанных в этой главе, приведена в таблице 6.18. Мы не приводим обоснования тех значений, которые указаны в таблице; читателю предлагается в качестве упражнения проверитьэти значения самостоятельно. Альтернативные определения сложности по времени будут обсуждаются в § 6.5.3.Лемма 6.32.
Для алгоритмов обхода сложность по времени равна сложности по числу сообщений.222Гл. 6.Волновые алгоритмы и алгоритмы обходаД о к а з а т е л ь с т в о. Обмен сообщениями осуществляется последовательно, и для каждого обмена может потребоваться одна единица времени.6.4.1. Распределенный поиск в глубинуКлассический алгоритм поиска в глубину получается из алгоритма Тарри,в котором свобода выбора очередного соседа для передачи ему маркера ограничена третьим правилом следующего вида (см. алгоритм 6.13).R3. Всякий раз, когда процесс получает маркер, он возвращает его назад потому же каналу, если это не противоречит правилам R1 и R2.var usedp [q]fatherp: boolinit false for each q ∈ Neighp ;(* Указывает, отправлял ли p маркер процессу q *): process init udef ;Только для инициатора, выполнить один раз:begin fatherp := p ; choose q ∈ Neighp ;usedp [q] := true ; send tok to qendДля каждого процесса, при получении tok от q0 :begin if fatherp = udef then fatherp := q0 ;if ∀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 tok to qendelse begin usedp [fatherp ] := true ;send tok to fatherpendendАлгоритм 6.13.
Классический алгоритм поиска в глубинуТеорема 6.33. Классический алгоритм поиска в глубину (алгоритм 6.13)строит остовное дерево поиска в глубину за 2|E| единиц времени, используя при этом 2|E| обменов сообщениями.Д о к а з а т е л ь с т в о. Поскольку в основу нашего алгоритма положен алгоритм Тарри, мы имеем дело с алгоритмом обхода, который вычисляет остовноедерево T.
Как было уже установлено, по каждому каналу передаются два сообщения (по одному в каждом направлении), и это служит обоснованием сложностипо числу сообщений. А сложность по времени равна 2|E|, поскольку обмен сообщениями проводится поочередно и каждый обмен требует не более одной еди-6.4. Сложность по времени: поиск в глубину223ницы времени. Остается убедиться в том, что дерево, построенное в результатеприменения правила R3, будет деревом поиска в глубину.Во-первых, согласно правилу R3 вслед за первым прохождением по стягивающему ребру немедленно следует повторное прохождение в обратном направлении.
Предположим, что pq — это стягивающее ребро и p является первымпроцессом, воспользовавшимся этим стягивающим ребром. К тому моменту, когда процесс q получает маркер от p, этот маркер уже побывал в q (в противномслучае процесс q занес бы в переменную fatherq ссылку на p и наше ребро немогло бы считаться стягивающим) и usedq [p] имеет значение false (посколькупо предположению процесс p был первым из этих двух процессов, воспользовавшимся указанным ребром). Следовательно, согласно правилу R3, процесс qнемедленно возвращает маркер процессу p.Теперь можно показать, что если ребро pq является стягивающим и его впервые использовал процесс p, то q ∈ A [p] .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
