Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 57
Текст из файла (страница 57)
Поскольку каждый процессуспел отправить хотя бы одно сообщение по каждому каналу, для любого процесса р выполняется требование Ус/ € lnp : recp[q]. Следовательно, для каждогор верно включение р € NIncp. А так как множества Nine содержат только отличительные признаки процессов, отсюда следует, что NIncp = Р для каждогопроцесса р. Из равенств Incp = Р и NIncp = Р вытекает, что Incp = NIncp, и этоозначает, что в конфигурации у каждый процесс р принял решение.Теперь нужно показать, что решению dp в процессе р предшествует какоенибудь событие в каждом из процессов.
Для всякого события е в процессе робозначим 1пс^ (соответственно Nine ^ значение 1пср (соответственно NIncp)сразу после осуществления е (см. доказательство теоремы 6.12). Следующие дваутверждения формально обосновывают тот содержательный смысл, который былпридан этим множествам в начале этого параграфа.Утверждение 6.22. Если существует событие e e C q : е N /, то q e ln c (^.Д о к а з а т е л ь с т в о .
Как и в доказательстве теоремы 6.12, можно показать, что соотношение е ■< / влечет Inc^ С Inc®. Учитывая соотношение е €€ Cq =*- q € Inc(e), отсюда получаем наше утверждение.□Утверждение 6.23. Если qeNInc®, то для всех r€lnq существует такоесобытиее е Сг, что е N /•Д о к а з а т е л ь с т в о . Пусть a q обозначает внутреннее событие в процессе q, связанное с первым выполнением оператора NIncq := NIncqli{q} процессомq. Событие a q — это единственное событие, для которого выполняется включение q е Nlnc{aq) и которому не предшествует другое событие а', удовлетворяющееусловию q € NInc(a Значит, q е Nine® =>• a q N /.
Из описания алгоритмавидно, что для каждого г <Е Inq найдется событие е е Сг, предшествующее aq.Отсюда следует доказываемое утверждение.□Процесс р принимает решение только тогда, когда Incp = NIncp\ в нашихобозначениях Inc<dp^ = Nine<'dp\ Теперь мы видим, что1 ) p e ! n c {dp);2) из q € Inc^ следует, что q е Nine{-dp\ и отсюда получаем Inq С Inc^dp).Поскольку сеть сильно связная, мы получаем искомое равенство Inc^dp) = Р. □6.3. Алгоритмы обходаВ этом параграфе мы обсудим особый класс волновых алгоритмов, в которых все события по ходу волны линейно упорядочены по отношению причинноследственной зависимости, и при этом последнее событие происходит в том жесамом процессе, что и первое.6.3. Алгоритмы обхода215Определение 6.24.
Алгоритмом обхода называется алгоритм, обладающий следующими тремя свойствами.1. В каждом вычислении есть единственный инициатор, который запускаеталгоритм, отправляя одно-единственное сообщение.2. Всякий процесс после получения сообщения либо отправляет ровно односообщение, либо принимает решение.Как следует из первых двух свойств, в каждом конечном вычислении в точности один процесс принимает решение. Говорят, что алгоритм завершает работув том единственном процессе, который принимает решение.3. Алгоритм завершает работу в инициаторе, и к тому моменту, когда этопроисходит, каждому процессу хотя бы один раз удалось отправить сообщение.В каждой достижимой конфигурации алгоритма обхода есть либо в точности одно сообщение, находящееся на этапе пересылки, либо в точности одинпроцесс, который только что принял сообщение и еще не успел отправить ответное сообщение.
С более абстрактной точки зрения все вместе взятые сообщенияв вычислении можно рассматривать как единственный объект (маркер), который переходит от одного процесса к другому и «посещает», таким образом, всепроцессы. В параграфе 7.5.4 алгоритмы обхода применяются для построения алгоритмов голосования, а для такого построения важно знать не только общеечисло переходов маркера по ходу одной волны, но и сколько переходов необходимо сделать маркеру, чтобы посетить первые х процессов.Определение 6.25.
Алгоритм называется алгоритмом /-обхода (для некоторого класса сетей), если выполнены следующие условия:1 ) он является алгоритмом обхода (для указанного класса);2 ) в каждом вычислении после совершения f(x) переходов маркер побывалне менее чем у min (А, х + 1 ) процессов.var re c p: in teg er init 0;Для инициатора:(* ЗаписатьN eig h p(* только для инициатора*)= {q\,q2, ■■■, qN-1} *)begin w h ile r e c p < # N e i g h p dob egin send tok to qrecp+ i ;receive tok; r e c p := r e c p + 1end;d ecid eendДля неинициатора:b egin receive tok from q ; send tok to q en dАлгоритм 6.9.Алгоритм последовательного опроса216Гл.
6.Волновые алгоритмы и алгоритмы обходаКольцевой алгоритм (алгоритм 6.1) является алгоритмом обхода, и, посколькупосле х переходов маркер побывал у х + 1 процессов и посетил все процессы поокончании jV-ro перехода, этот алгоритм является также алгоритмом х-обходадля кольцевых сетей.6.3.1. Обход кликВсякую клику можно обойти, воспользовавшись последовательным опросом; этот алгоритм очень похож на алгоритм 6.5, однако соседи инициатора опрашиваются здесь поочередно, и как только поступает отклик от одного соседа,проводится опрос следующего (см.
алгоритм 6.9).Теорема 6.26. Алгоритм последовательного опроса (алгоритм 6.9) —это алгоритм 2 х-обхода для клик.Д о к а з а т е л ь с т в о . Легко видеть, что если алгоритм завершается в инициаторе, то каждому процессу удалось прислать отклик. Запросом к процессу qxслужит (2х—1)-е сообщение, а откликом на него является 2х-е сообщение. Следовательно, если произошел обмен 2х сообщениями, то посетить удалось х + 1процессов р, qi, ...
, qx.□6.3.2. Обход торовТорический граф граф размера п х п — это граф G = (V , Е), у которогоV = Ъп х Z„ = {(г, /) : 0 < /, j < п}иЕ = {(г, /)(/', /') : (/ = /'А/= / ± 1) V (/ = /' ± 1 А/ = /')}(см. §Б.2.4). Сложение и вычитание здесь проводится по модулю п. Предполагается, что в торе имеется восприятие направления (см. § Б.4.3), т. е. в вершине(г, /) канал, соединяющий эту вершину с (/, / + 1), помечен Up, канал, ведущийв вершину (г, j — 1), помечен Down, канал, ведущий в вершину (г+ 1, /), помеченRight, а канал, ведущий в вершину (г —1, j), помечен Left.
Пары координат (/, /)служат удобным средством задания топологии сети и ориентации, однако мы будем считать, что процессы не располагают сведениями об этих координатах; ихпредставление о топологии ограничено метками каналов.Тор является гамильтоновым графом, т. е. в торе произвольного размера существует гамильтонов цикл, и маркер перемещается по этому циклу, руководствуясьалгоритмом 6.10. После 6 -го перехода маркер отправляется вверх, если n\k (пявляется делителем 6 ); в противном случае он отправляется направо.Теорема 6.27. Алгоритм тора (алгоритм 6.10) является алгоритмомх-обхода для тора.Д о к а з а т е л ь с т в о .
Как видно из описания алгоритма, решение принимается, как только маркер был передан п2 раз. Если маркер переместился от6.3. Алгоритмы обхода217Для инициатора, выполнить один раз:send (num, 1) to UpДля каждого процесса после приема маркера (num, k):begin if k = n 2 then d e c i d eelse if n \ k then send (num, k + 1) to Upelse send (num, k + 1) to R i g h tendАлгоритм 6.10. Алгоритм обхода для торапроцесса р к процессу q, совершив U переходов Up и R переходов Right, тор = q тогда и только тогда, когда (n\U Л n\R). Обозначим процесс-инициаторсимволом ро, а процесс, получивший маркер (num, k), обозначим символом pk.Из общего числа я 2 перемещений маркера я ходов были сделаны вверх,а остальные п2 —п ходов были сделаны направо.
Поскольку оба числа п и п2 —яделятся на п, получаем, что р п2 = ро, и это означает, что алгоритм завершаетсяв инициаторе.Далее будет показано, что все процессы, начиная от ро и оканчивая рп2 _ ь попарно различны. А так как у нас всего п2 процессов, отсюда следует, что посетитьудалось каждый процесс. Допустим, ра = рь для некоторых а, 6 ,0 < а < b < я 2.На участке от ра до рь маркер совершил некоторое количество переходов Upи некоторое количество переходов Right, и, поскольку ра = рь, оба числа делятся на я. Обратившись к описанию алгоритма, можно заметить, что это влечет засобой два соотношения# {6: а ^ k < b Л n\k} кратно яиФ{к : а < k < b А п J(k} кратно я.Суммарный размер этих множеств равен b — а, откуда следует, что я | ( 6 —а).Представим это отношение в виде (b —а) = In.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
