Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 57
Текст из файла (страница 57)
. , miбудет не меньше чем i. Выберем такое j 6 i, что mj > i. Тогда выполняются со(m )(i)(j)(i)отношения fpq fpq j gpq gpq .Теорема 6.20. Фазовый алгоритм (алгоритм 6.6) — это волновой алгоритм.Д о к а з а т е л ь с т в о. Поскольку каждый процесс отправляет не более Dсообщений по каждому каналу, алгоритм завершает работу после конечного числа шагов. Обозначим символом заключительную конфигурацию вычисления Cнашего алгоритма и будем предполагать, что в C есть хотя бы один инициатор(их может оказаться и несколько).Чтобы убедиться в том, что в каждый процесс принял решение, мы сначалапокажем, что каждый процесс хотя бы один раз отправлял сообщения. Ввидутого что в конфигурации в каналах нет сообщений, для каждого канала qpсправедливо равенство Recp [q] = Sentq .
Кроме того, поскольку каждый процессотправляет сообщения самое позднее после того, как некоторое сообщение было(1)(l)имеет место для любого i, 0 6 i < l − 1. Следовательно, f p0 p1 gpl−1 pl . Таккак диаметр сети равен D, для каждой пары процессов q и p существует путьq = p0 , p1 , . . . , pl = p, длина которого не превосходит D. Таким образом, длякаждого q найдeтся такое l 6 D и такой сосед r на входе процесса p, что имеет(1)(l)место соотношение fqq0 grp . А в силу устройства нашего алгоритма событие(l)grp предшествует dp .В алгоритме по каждому каналу передается D сообщений, и поэтому егосложность по числу обменов сообщениями равна |E|D.
Нужно иметь в виду, однако, что здесь |E| обозначает количество односторонних каналов. Если нашалгоритм используется для неориентированной сети, то каждый ее канал следует рассматривать как два односторонних канала, и поэтому сложность по числусообщений будет равна 2|E|D.Фазовый алгоритм для клик. Если сеть является кликой, то ее диаметр равен 1. В таком случае от каждого соседа должно быть получено в точности односообщение и каждому процессу достаточно подсчитать общее число полученныхсообщений, вместо того чтобы подсчитывать по отдельности сообщения, полученные от каждого соседа на выходе (см.
алгоритм 6.7). При этом сложность почислу сообщений будет равна N(N − 1) и алгоритму будет хватать всего лишьO(log N) битов внутренней памяти.212Гл. 6.var RecpSentpВолновые алгоритмы и алгоритмы обхода: 0..N − 1 init 0 ;(* Число полученных сообщений *): 0..1init 0 ;(* Число сообщений, отправленных каждому соседу *)begin if p is initiator thenbegin forall r ∈ Neighp do send htoki to r ;Sentp := Sentp + 1end;while Recp < #Neighp dobegin receive htokiRecp := Recp + 1 ;if Sentp = 0 thenbegin forall r ∈ Neighp do send htoki to r ;Sentp := Sentp + 1endend;decideendАлгоритм 6.7.
Фазовый алгоритм для клик6.2.6. Алгоритм ФиннаАлгоритм Финна (см. [79]) — это еще один волновой алгоритм, который можно использовать для произвольных ориентированных сетей. Здесь не требуется,чтобы диаметр сети был известен заранее, но зато этот алгоритм опирается наоднозначную идентифицируемость процессов. В сообщениях процессы обмениваются отличительными признаками, и это приводит к тому, что битовая сложностьалгоритма становится достаточно большой.В процессе p формируются два множества отличительных признаков Inc p иNIncp . Если говорить неформально, то Incp обозначает множество таких процессов q, что некоторое событие в q предшествует самому последнему событию, случившемуся в p, а NIncp обозначает множество таких процессов q, что у каждогососеда r процесса q какое-нибудь событие в r предшествует самому последнемусобытию, случившемуся в p. Формирование этих множеств осуществляется так.Вначале Incp = {p} и NIncp = ∅.
Процесс p отправляет сообщения, в которыхсодержатся Incp и NIncp , всякий раз, когда одно из этих множеств расширяется.Когда p получает сообщение, содержащее множество Inc и множество NInc, полученные отличительные признаки добавляются к соответствующим множествам,которые формирует процесс p. Если процесс p получил сообщения от всех своихсоседей на входе, то отличительный признак p вставляется в NInc p . Когда эти двамножества станут одинаковыми, p принимает решение (см.
алгоритм 6.8). Исходя из содержательного смысла, который приписан этим множествам, это будетозначать, что, каков бы ни был процесс q, если некоторое событие в q предшествует dp , то у всякого соседа r процесса q также произошло какое-нибудь6.2. Семейство волновых алгоритмов213событие, предшествующее dp . Отсюда следует, что для нашего алгоритма требование зависимости соблюдено.По ходу доказательства корректности алгоритма будет показано, что все этосвойственно каждому процессу p, и равенство двух указанных множеств означает,что решению предшествует какое-нибудь событие в каждом процессе.varIncp: set of processesinit {p} ;NIncp : set of processesinit ∅ ;recp [q] : bool for q ∈ Inpinit false ;(* индикаторы получения процессом p сообщения от q *)begin if p is initiator thenforall r ∈ Outp do send hsets, Incp , NIncp i to r ;while Incp 6= NIncp dobegin receive hsets, Inc, NInci from q0 ;Incp := Incp ∪ Inc ; NIncp := NIncp ∪ NInc ;recp [q0 ] := true ;if ∀q ∈ Inp : recp [q] then NIncp := NIncp ∪ {p} ;if Incp or NIncp has changed thenforall r ∈ Outp do send hsets, Incp , NIncp i to rend;decideendАлгоритм 6.8.
Алгоритм ФиннаТеорема 6.21. Алгоритм Финна (алгоритм 6.8) является волновым алгоритмом.Д о к а з а т е л ь с т в о. Заметим, что два множества, формируемые каждымпроцессом, могут только увеличиваться. Поскольку суммарный размер этих двухмножеств варьируется от 1 в первом сообщении, передаваемом по каждому каналу, до не более чем 2N в последнем сообщении, общее количество сообщенийограничено величиной 2N|E|. Рассмотрим вычисление C, в котором есть хотя быодин инициатор, и его последнюю конфигурацию , которая является заключительной. Так же как и в доказательстве теоремы 6.20, можно показать, что еслипроцесс p сумел отправить хотя бы одно сообщение (каждому соседу) и q — сосед процесса p на выходе, то q также сумел отправить по меньшей мере односообщение.
Отсюда следует, что каждый процесс сумел отправить хотя бы односообщение (по каждому каналу).Теперь будет показано, что в каждый процесс принял решение. Во-первых,для каждого ребра pq в конфигурации выполняется включение Inc p ⊆ Incq .И в самом деле, совершив последнее изменение множества Inc p , процесс p отправил сообщение hsets, Incp , NIncp i. Как только оно было получено, процесс qвыполнил оператор Incq := Incq ∪ Incp . Сильная связность сети приводит к тому,что Incp = Incq для всех p и q.
Коль скоро p ∈ Incp и каждое множество Inc214Гл. 6.6.3. Алгоритмы обходаВолновые алгоритмы и алгоритмы обходасодержит только отличительные признаки процессов, для каждого процесса pв конфигурации выполняется равенство Incp = P.Во-вторых, аналогичным образом можно показать, что для каждой пары процессов p и q выполняется равенство NIncp = NIncq . Поскольку каждый процессуспел отправить хотя бы одно сообщение по каждому каналу, для любого процесса p выполняется требование ∀q ∈ Inp : recp [q] . Следовательно, для каждогоp верно включение p ∈ NIncp .
А так как множества NInc содержат только отличительные признаки процессов, отсюда следует, что NInc p = P для каждогопроцесса p. Из равенств Incp = P и NIncp = P вытекает, что Incp = NIncp , и этоозначает, что в конфигурации каждый процесс p принял решение.Теперь нужно показать, что решению dp в процессе p предшествует какоенибудь событие в каждом из процессов. Для всякого события e в процессе pобозначим Inc (e) (соответственно NInc (e) значение Incp (соответственно NIncp)сразу после осуществления e (см.
доказательство теоремы 6.12). Следующие дваутверждения формально обосновывают тот содержательный смысл, который былпридан этим множествам в начале этого параграфа.Утверждение 6.22. Если существует событие e ∈ Cq : e f, то q ∈ Inc (f) .Д о к а з а т е л ь с т в о. Как и в доказательстве теоремы 6.12, можно показать, что соотношение e f влечет Inc (e) ⊆ Inc (f) . Учитывая соотношение e ∈∈ Cq =⇒ q ∈ Inc (e) , отсюда получаем наше утверждение.Утверждение 6.23. Если q ∈ NInc (f) , то для всех r ∈ Inq существует такоесобытиеe ∈ Cr , что e f.Д о к а з а т е л ь с т в о.
Пусть aq обозначает внутреннее событие в процессе q, связанное с первым выполнением оператора NIncq := NIncq ∪{q} процессомq. Событие aq — это единственное событие, для которого выполняется включение q ∈ NInc (aq) и которому не предшествует другое событие a0 , удовлетворяющее0условию q ∈ NInc (a ) . Значит, q ∈ NInc (f) =⇒ aq f. Из описания алгоритмавидно, что для каждого r ∈ Inq найдется событие e ∈ Cr , предшествующее aq .Отсюда следует доказываемое утверждение.Процесс p принимает решение только тогда, когда Inc p = NIncp ; в нашихобозначениях Inc (dp) = NInc (dp) . Теперь мы видим, что1) p ∈ Inc (dp) ;2) из q ∈ Inc (dp) следует, что q ∈ NInc (dp) , и отсюда получаем Inq ⊆ Inc (dp) .Поскольку сеть сильно связная, мы получаем искомое равенство Inc (dp) = P.6.3.
Алгоритмы обходаВ этом параграфе мы обсудим особый класс волновых алгоритмов, в которых все события по ходу волны линейно упорядочены по отношению причинноследственной зависимости, и при этом последнее событие происходит в том жесамом процессе, что и первое.215Определение 6.24. Алгоритмом обхода называется алгоритм, обладающий следующими тремя свойствами.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
