Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 55
Текст из файла (страница 55)
Тогда элемент c называвначале значение vq было равно jq и по ходу волны могло только уменьшиться,ется точной нижней гранью элементов a и b, если c 6 a, c 6 b и ∀d : (d 6 a∧d 6 b =⇒ d 6 c).соотношение v (a) 6 jq соблюдается для каждого события a в q. ПрисваиванияДопустим, что X обладает тем свойством, что точная нижняя грань всегда сущепеременной v устроены так, что для любых событий a и b имеет место соотноствует.
В таком случае эта точная нижняя грань определяется однозначно и обошение a b =⇒ v (a) > v (b) . Кроме того, поскольку v вычисляется как точнаязначается a u b. Двуместная операция u является коммутативной (a u b = b u a)нижняя грань уже существующих значений, соотношение J 6 v соблюдается дляи ассоциативной (a u (b u c) = (a u b) u c), и поэтому ее можно распространитьвсех значений по ходу волны. Таким образом, если d — это событие decide в p,на конечные множества:то значение v (d) удовлетворяет соотношению J 6 v (d) , а поскольку событию dinf{j1 , . . . , jk } = j1 u · · · u jk .предшествует хотя бы одно событие в каждом процессе q, мы имеем v (d) 6 jq длявсех q. Отсюда следует, что J = v (d) .Проблема вычисления точной нижней грани (Infimum Computation, INF) такова. Все процессы q наделены входными данными j q , которые являются элеменПостроенный INF-алгоритм обладает всеми теми же свойствами, что и A, затами частично упорядоченного множества X.
Требуется, чтобы некоторые выдеисключением битовой сложности, поскольку к каждому сообщению A присоедиленные процессы вычислили значение inf{jp : q ∈ P} и чтобы эти процессы былинялся элемент из X. Понятие функции точной нижней грани может показаться202Гл. 6.Волновые алгоритмы и алгоритмы обходадовольно-таки абстрактным, но на самом деле многие функции могут быть представлены как точные нижние грани, о чем свидетельствует работа [187, теорема 4.1.1.2] .Теорема 6.13 (о точной нижней грани). Пусть ? — это такая двухместная операция на множестве X, которая обладает следующими свойствами:1) операция ? коммутативна, т. е.
a ? b = b ? a,2) операция ? ассоциативна, т. е. (a ? b) ? c = a ? (b ? c),3) операция ? идемпотентна, т. е. a ? a = a.Тогда существует частичный порядок 6 на X, для которого ? являетсяфункцией точной нижней грани.К числу операций, удовлетворяющих трем перечисленным выше требованиям,относятся логические конъюнкция и дизъюнкция, функции минимума и максимума на множестве целых чисел, наибольший общий делитель и наименьшее общеекратное на множестве целых чисел, а также операции пересечения и объединениямножеств.Следствие 6.14. Функции ∧, ∨, min, max, НОК, НОД, ∩, и ∪, зависящиеот значений, локализованных во всех процессах, можно вычислить по ходуодной единственной волны.Вычисление операций, которые являются коммутативными, ассоциативными,но не идемпотентными, рассматривается в § 6.5.2.6.2. Семейство волновых алгоритмовВ следующих трех параграфах представлено семейство волновых алгоритмов и алгоритмов обхода.
Во всех случаях описание алгоритма приводится длявыделенного процесса p.6.2.1. Кольцевой алгоритмВ этом параграфе будет представлен волновой алгоритм для кольцевой сети.Этот же самый алгоритм можно использовать и для гамильтоновой сети, в которой информация о некотором фиксированном гамильтоновом цикле заложенаво всех процессах. Предполагается, что каждому процессу p предписан соседNextp так, чтобы каналы связи между выделенными таким образом соседямиобразовывали гамильтонов цикл.Алгоритм является централизованным: инициатор отправляет сообщение tok(оно называется маркером) по циклу, каждый процесс передает его далее, и,когда оно возвращается инициатору, тот принимает решение (см. алгоритм 6.1).Теорема 6.15.
Кольцевой алгоритм (алгоритм 6.1) является волновымалгоритмом.6.2. Семейство волновых алгоритмов203Д о к а з а т е л ь с т в о. Пусть инициатором является процесс p 0 . Поскольку каждый процесс отправляет не более одного сообщения, всего в алгоритмепроисходит обмен не более N сообщениями.Для инициатора:begin send tok to Nextp ; receive tok ; decide endДля неинициатора:begin receive tok ; send tok to Nextp endАлгоритм 6.1.
Кольцевой алгоритмЧерез конечное число шагов алгоритм достигает заключительной конфигурации. В этой конфигурации процесс p0 уже отправил маркер, т. е. выполнилоператор send своей программы. При этом никакое сообщение tok не передаетсяни по одному каналу, ибо иначе оно бы могло быть получено и конфигурациюнельзя было бы считать заключительной. Кроме того, ни один процесс, отличныйот p0 , не «хранит» маркер (т. е. уже получил, но еще не отправил tok), ибо иначеэтот процесс мог бы отправить tok и конфигурация была бы не заключительной.Приходим к следующему заключению:1) процесс p0 уже отправил маркер,2) для каждого процесса p, отправившего маркер, процесс Next p уже получил этот маркер,3) каждый процесс p 6= p0 , получивший маркер, уже отправил маркер.Отсюда, а также из свойства Next вытекает, что каждый процесс уже получили уже отправил маркер.
Поскольку процесс p0 уже получил маркер, и конфигурация является заключительной, процесс p0 выполнил оператор decide.Получение и отправление сообщения tok каждым процессом p 6= p 0 предшествует событию получения маркера процессом p0 . Значит, условие зависимостисоблюдено.6.2.2. Древесный алгоритмВ этом параграфе будет представлен волновой алгоритм для древесной сети.
Этот же алгоритм можно использовать и для произвольной сети, если иметьдоступ к остовному дереву этой сети. Предполагается, что все листья сети запускают наш алгоритм. Каждый процесс отправляет в точности одно сообщение напротяжении работы алгоритма. Если процесс уже получил сообщение по каждому из инцидентных ему каналов, кроме одного (это условие первоначально вернодля листьев), то он отправляет сообщение по оставшемуся каналу. Если процессуже получил сообщение по всем инцидентным ему каналам, то он принимает решение (см. алгоритм 6.2).Для доказательства того, что этот алгоритм является волновым, потребуютсянекоторые обозначения. Будем использовать запись f pq для обозначения событияотправления сообщения процессом p процессу q, а g pq — для обозначения события приема процессом q сообщения от процесса p.
Обозначим символом T pq204Гл. 6.6.2. Семейство волновых алгоритмовВолновые алгоритмы и алгоритмы обходаTpq uмножество процессов, которые достижимы из p без прохождения по ребру pq(процессы, лежащие в дереве «по ту же сторону» этого ребра, что и вершина p).Из связности сети следуют соотношения (см. рис. 6.3)[[Tpq =Trp ∪ {p} и P = {p} ∪Trp .r∈Neighp \{q}@@uuAAAuur∈Neighpvar recp [q] for each q ∈ Neighp : boolean init false ;(* recp [q] принимает значение true, если p уже получил сообщение от q *)begin while #{q : recp [q] = false} > 1 dobegin receive htoki from q ; recp [q] := true end;(* Теперь есть единственный q0 , для которого recp [q0 ] имеет значение false *)send htoki to q0 with recp [q0 ] = false ;x: receive htoki from q0 ; recp [q0 ] := true ;decide(* Оповестить другие процессы о решении:forall q ∈ Neighp , q 6= q0 do send htoki to q *)endАлгоритм 6.2.
Древесный алгоритмСмысл «закомментированного» оператора forall в алгоритме 6.2 мы обсудимв конце этого параграфа. Следующая теорема касается того варианта указанногоалгоритма, в котором не содержится этого оператора.Теорема 6.16. Древесный алгоритм (алгоритм 6.2) является волновымалгоритмом.Д о к а з а т е л ь с т в о. Поскольку каждый процесс отправляет не болееодного сообщения, всего в алгоритме используется не более N сообщений. Отсюда следует, что алгоритм достигает заключительной конфигурации спустяконечное число шагов. Мы покажем, что в хотя бы в одном из процессов ужепроизошло событие decide.Пусть F — это число битов rec со значением false в конфигурации , а K —количество процессов, которые уже отправили сообщения в конфигурации .
Поскольку в никаких сообщений не пересылается (иначе конфигурация не былабы заключительной), F = (2N − 2) − K. Общее число битов rec равно 2N − 2, и Kиз них имеют значение true.Допустим, что ни один из процессов не принял решения в . Тогда N − Kпроцессов, которые в еще не отправляли сообщения, имеют в rec по меньшеймере два бита со значением false; в противном случае они могли бы отправитьсообщение, вопреки тому что – заключительная конфигурация. Кроме того, Kпроцессов, которые в уже отправили сообщение, имеют в rec хотя бы по одному биту со значением false; в противном случае они могли бы принять решениевопреки сделанному предположению о .
Значит, F > 2(N − K) + K, и из неравен-u@@uuAAAuuuuuuuuuqup@@uuuuuqup@u@uДекомпозиция TpquT205TqpuTpq и TqpTu@@uuAAAuuuuuup@@uuuuuTДекомпозиция TРис. 6.3. Поддеревья Tpqства (2N − 2) − K > 2(N − K) + K следует, что −2 > 0. Полученное противоречиеозначает, что хотя бы одно решение в уже принято; см. также упражнение 6.5.Наконец, необходимо показать, что решение предшествует какому-либо событию в каждом из процессов. Напомним, что fpq обозначает событие отправления процессом p сообщения процессу q, а gpq — событие приема процессом qсообщения от процесса p. Воспользуемся индукцией по числу событий приема,чтобы показать, что∀ s ∈ Tpq ∃e ∈ Cs : e gpq .Допустим, это верно для всех событий приема, предшествующих событию g pq .Тогда событию gpq предшествует событие fpq (в процессе p) и из устройствапрограммы p следует, что для всех r ∈ Neighp при r 6= q событию fpq предшествуетсобытие grp .
Из индуктивной гипотезы вытекает, что для всех таких r и для всехs ∈ Trp найдется такое событие e ∈ Cs , что e grp . Значит, e gpq .Решению dp в p предшествует событие grp для всех r ∈ Neighp , И отсюдаследует, что ∀ s ∈ P ∃e ∈ Cs : e dp .Читатель может промоделировать вычисление алгоритма на небольшом дереве (например, на дереве, изображенном на рис. 6.3), и удостовериться в справедливости следующих замечаний. В алгоритме 6.2 есть два процесса, которыеполучают сообщение по каждому из своих каналов и принимают решение; всеостальные процессы еще ожидают сообщения, пребывая в заключительной конфигурации в точке x своей программы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
