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

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

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

Тогда множество {к \ a g k < Ь\содержит / чисел, делящихся на я. Отсюда следует, что я|/, и поэтому п2\(Ь - а),что является противоречием. Так как все процессы, начиная с ро и оканчиваяyV_i, попарно различны, маркеру после х переходов удается посетить х + 1процессов.□6.3.3. Обход гиперкубовГраф G = ( V, Е), в которомV = {(b0,=1}иЕ = {(&о, • • •, ^я- i), (со, . . . , сп-\): наборы б и с отличаются в одном бите}называется я-мерным гиперкубом (см.

§ Б.2.5). Предполагается, что в гиперку­бе имеется восприятие направления (см. §Б.4.3), т. е. канал между вершинамиГл. 6.218Волновые алгоритмы и алгоритмы обходаЬ и с, отличающимися в г-м бите, помечен «г» в обеих вершинах. Предпола­гается также, что процессы не располагают сведениями о пометках вершин; ихпредставление о топологии ограничено знанием меток каналов.Как и в случае тора, гиперкуб является гамильтоновым графом, и гамиль­тонов цикл можно обойти, воспользовавшись алгоритмом 6.11. Доказательствокорректности этого алгоритма почти такое же, как для алгоритма 6 . 1 0 .Для инициатора выполнить один раз:send (num, 1 ) по каналу я — 1 .Для каждого процесса после приема маркера (num, k)\begin if k = 2" then d e c i d eelse begin let / — наибольшее такое число, что 2l\k ;send (num, k + 1 ) по каналу lendendАлгоритм 6.11.

Алгоритм обхода для гиперкубаТеорема 6.28. Алгоритм гиперкуба (алгоритм 6.11) является алгорит­мом х-обхода для гиперкуба.Д о к а з а т е л ь с т в о . Как видно из описания алгоритма, решение прини­мается после 2я переходов маркера. Обозначим символом ро инициатор, и пустьPk будет обозначать процесс, к которому поступил маркер (num, k).

Для всяко­го k < 2 я наборы, обозначающие вершины pk и pk+i, отличаются в одном бите,индекс которого обозначим l(k). Этот индекс удовлетворяет соотношениюl(k)J п ~ 1>если ^ = о,I наибольшее такое /, что 2l\k, если k > 0 .Так как для каждого i < п существует четное число таких индексов &е{0, . . . , 2я},что l(k ) = /, мы заключаем, что ро = р 2 » и решение принимается инициатором.Проводя рассуждения, сходные с теми, которые применялись для доказательстватеоремы 6.27, приходим к выводу о том, что равенство ра = рь влечет условие2Я|(Ь —а).

Отсюда следует, что все процессы ро, . . . , p 2 »-i попарно различны.Таким образом, к моменту завершения вычисления маркеру удалось посетитьвсе процессы. При этом, совершив х переходов, маркеру удается посетить х + 1процессов.□6.3.4. Обход связных сетейАлгоритм обхода произвольных связных сетей был предложен Тарри в 1895;см. [183].

Этот алгоритм определяется двумя следующими правилами (см. алго­ритм 6 . 1 2 ).R1. Процесс не передает маркер по одному и тому же каналу дважды.6.3. Алгоритмы обхода219R2. Неинициатор передает маркер своей родительской вершине (соседу, откоторого он впервые получил маркер) только в том случае, когда его невозможнопередать по другим каналам согласно правилу R 1 .varusedplq] : boolfalse for each q e Neighp ;(* Показывает, отправлял ли p сообщение процессу q *)fatherp : process in it udef ;initТолько для инициатора, выполнить один раз:begin fatherp := р ; choose q е Neighp ;usedp [q] := true ; send tok to qendtok от qо:begin if fatherp = udef th en fatherp := qо ;if Vq 6 Neighp : usedp[q] th en decideelse if З17 6 Neighp : (q Д fatherp A ->usedP[q])th en b egin choose q € Neighp \ {fatherp}Для каждого процесса после приемаwith -iusedp[q] '<usedp[q] '■=true ; sendendelse b eg intokto qusedp[fatherp] := true ;tok to fatherpsenden dendАлгоритм 6.12.Алгоритм обхода ТарриТеорема 6.29.

Алгоритм Тарри (алгоритм 6.12) является алгоритмомобхода.Д о к а з а т е л ь с т в о . Так как маркер передается не более чем по одномуразу в каждом из двух направлений по любому каналу, он совершает не более 2 |£|переходов, пока алгоритм не завершится. Поскольку каждый процесс отправляетмаркер по каждому каналу не более одного раза, он его и получает по каждомуканалу не более одного раза. Всякий раз, когда маркером владеет неинициатор р ,это означает, что процессу р пришлось получать маркер на один раз больше, чемотправлять его. Отсюда следует, что число каналов, инцидентных р, превосходитчисло каналов, использованных этим процессом, по крайней мере на 1 , и поэтомур не принимает решения, а передает маркер.

Значит, решение может принятьтолько инициатор.Далее мы обоснуем три тезиса, из которых следует, что всякий раз, когдаалгоритм завершает работу, каждому процессу пришлось участвовать в передачемаркера.1.Все каналы , инцидентные инициатору, были использованы по одно­му разу в каждом направлении. Каждый канал был использован инициатором220Гл. 6.Волновые алгоритмы и алгоритмы обходадля передачи маркера, ибо в противном случае алгоритм не завершается. Ини­циатору пришлось получать маркер столько же раз, сколько и отправлять его.А поскольку получать его приходилось по разным каналам, маркер был полученпо одному разу с использованием каждого канала.2.

Для каждого посещенного маркером процесса р все каналы , инци­дентные р, были использованы для передачи маркера в каждом направле­нии по одному разу. Предположим, что это не так. Пусть р — самый первый изпосещенных маркером процессов, для которого не выполняется это предположе­ние. Заметим, что согласно тезису 1).

таким процессом не может быть инициатор.Согласно выбору р все каналы, инцидентные fatherp, были использованы по од­ному разу в каждом направлении. Отсюда следует, что р уже отправил маркерв родительскую вершину. Но это означает, что р использовал все инцидентныеканалы для отправления маркера.

А поскольку маркер вернулся к инициато­ру, процессу р пришлось получать его столь же часто, сколь и отправлять. Нов таком случае по каждому инцидентному каналу процесс р получал маркер поодному разу. А это противоречит сделанному предположению.3. Маркер посетил все процессы и передавался по каждому каналув обоих направлениях. Если бы нашлись процессы, которые маркеру не удалосьпосетить, то это означало бы, что для некоторой пары соседних процессов р и qмаркеру удалось побывать в р, но не удалось посетить q.

Но это противоречиттому, что процессу р пришлось использовать каждый канал в обоих направлени­ях. Значит, маркер побывал во всех процессах, и все каналы были задействованыпо одному разу в каждом направлении согласно тезису 2 ).□Каждое вычисление алгоритма Тарри задает в сети остовное дерево, о чемсвидетельствует лемма 6.3. Корнем дерева служит инициатор, и каждый нениициатор р к моменту завершения вычисления уже заносит в переменную fatherрссылку на родительскую вершину в этом дереве.

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

Стягивающее ребро — это ребро, не принадлежащее остовному дереву.Для заданного остовного дерева Т сети G и для каждой его вершины р мы бу­дем использовать запись Т[р] для обозначения множества процессов поддерева,растущего из р, а запись А[р ] — для обозначения множества предшественни­ков р, т.

е. вершин, лежащих в дереве Т на пути из корня в р. Заметим, чтоqeT[p] •*=*> peA[q],6.4. Сложность по времени-, поиск в глубину221Определение 6.30. Корневое остовное дерево Т сети G называется дере­вом поиска в глубину, если для каждого стягивающего ребра pq выполняетсясоотношение q € Т[р] V q е А[р].Деревья поиска в глубину применяются во многих графовых алгоритмах, напо­добие проверки планарности, проверки двусвязности, построения интервальныхсхем разметки (см. § 4.4.2). В § 6.4.1 будет показано, что незначительная модифи­кация алгоритма Тарри (связанная с ограничением свободы выбора процессов)позволяет применять его для построения деревьев поиска в глубину. Полученныйтаким образом алгоритм мы назовем классическим алгоритмом поиска в глу­бину.

В §6.4.2 будут рассмотрены два алгоритма, позволяющие строить деревьяпоиска в глубину за меньшее время по сравнению с классическим алгоритмом.Для распределенных алгоритмов понятие сложности по времени будет опреде­лено ниже. В § 6.4.3 будет предложен алгоритм поиска в глубину для сетей приналичии предварительных сведений об отличительных признаках соседей. В этомслучае теорема 6 . 6 уже будет не применима, и по сути дела можно построитьалгоритм, использующий всего лишь 2 N —2 сообщений.Сложность по времени для распределенных алгоритмов.

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

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