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

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

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

Для каждого ребра pq выражениеfpq будет обозначать г-е событие отправления процессом р сообщения процессуq, а выражение gpq будет обозначать г-е событие приема процессом q сообще­ния от процесса р. Если канал связи между процессами р и q имеет тип оче­реди (first in —first out), эти события соответствуют друг другу, и соотношениеfpq ^ gpq, очевидно, выполняется. Причинно-следственные отношения между fpqи gpq соблюдаются и в тех случаях, когда канал не является очередью, о чемсвидетельствует следующая лемма.Лемма 6.19.

Соотношение ffq Д g fq соблюдается и тогда, когда каналне является очередью.Гл. 6.210con s Dvar R ecp [q\S en tpВолновые алгоритмы и алгоритмы обхода: in teg er= диаметр сети ;: 0 ..Dinit 0 для каждого q 6 I n p ;(* Число сообщений, полученных от q *): 0 ..Dinit 0 ;(* Число сообщений, отправленных каждому соседу на выходе *)b egin if р is initiator thenb egin forall r e O u t p do send (tok) to r ;S e n t p := S e n tp +1end;w h ile min? R ecp [q\ < D dobegin receive (tok) (from neighbor q o) ;R ecp [q0\ := R ecp [q0\ + 1 ;if min? R ecp [q] Д S e n t p and S e n t p < D th enb egin forall r 6 O u t p do send (tok) to r ;S e n tp:= S e n tp + 1endend;decid eendАлгоритм 6.6.Фазовый алгоритмД о к а з а т е л ь с т в о .

Допустим, что число т/г таково, что— это со­бытие отправления сообщения, которое соответствует g fq, т. е. при выполненииh-то события приема процесс q получает тр-е сообщение от р. По определениюпричинно-следственнои зависимости мы имеем< gpq.Поскольку каждое сообщение на протяжении вычисления С принимается од­нократно, все m/г различны, откуда следует, что хотя бы одно из чисел т \ , . .

. , от­будет не меньше чем г. Выберем такое j ^ /, что rrij > /. Тогда выполняются со­отношения ffq Д (р1^ < g fq Д g%.□Теорема 6.20. Фазовый алгоритм (алгоритм 6 .6 ) — это волновой алго­ритм.Д о к а з а т е л ь с т в о . Поскольку каждый процесс отправляет не более Dсообщений по каждому каналу, алгоритм завершает работу после конечного чис­ла шагов. Обозначим символом у заключительную конфигурацию вычисления Снашего алгоритма и будем предполагать, что в С есть хотя бы один инициатор(их может оказаться и несколько).Чтобы убедиться в том, что в у каждый процесс принял решение, мы сначалапокажем, что каждый процесс хотя бы один раз отправлял сообщения. Ввидутого что в конфигурации у в каналах нет сообщений, для каждого канала qpсправедливо равенство Recp[q] = Sentq.

Кроме того, поскольку каждый процессотправляет сообщения самое позднее после того, как некоторое сообщение было6.2. Семейство волновых алгоритмов211им получено, имеем Recp[q] > 0 ==>• Sentp > 0. Тогда исходя из предположе­ния о существовании хотя бы одного инициатора ро, для которого SentPo > 0,приходим к выводу о том, что Sentp > 0 для каждого р.Далее будет показано, что каждый процесс принял решение.

Рассмотрим про­цесс р, у которого в конфигурации у переменная Sent имеет наименьшее зна­чение, т. е. в у для всех q выполняется неравенство Sentq > Sentp. В частно­сти, это неравенство справедливо для процесса q, являющегося соседом про­цесса р на входе, и тогда из равенства Recp[q] = Sentq вытекает неравенствоminqRecp[q] > Sentp. Но это означает, что Sentp = D\ в противном случаепроцесс р пришлось бы отправлять дополнительное сообщение, как только онв последний раз получил некоторое сообщение.

Значит, Sentp = D для всех р, и,следовательно, для всех каналов qp имеет место равенство Recp[q] = D. Отсюдазаключаем, что каждый процесс принял решение.Остается показать, что всякому решению предшествует хотя бы одно событиев каждом из процессов. Рассмотрим путь в сети Р = ро, р\, . . . , pi, где / ^ D.Тогда по лемме 6.19 соотношениеfO'+P -< ff0'+i)- S Pipi+l1Р>Р>+1справедливо для любого /,соотношение0^ / < /, и в соответствии с описанием алгоритма0-(i+l) -м (U+2)& PiPi+l — ' Pi+ 1Pi+2имеет место для любого г, 0 ^ г < I — 1. Следовательно, fPqPl ■< gpl_lPl. Таккак диаметр сети равен D, для каждой пары процессов q и р существует путьq = Ро, Р\, ■■■, Pi = Р, длина которого не превосходит D.

Таким образом, длякаждого q найдется такое I ^ D и такой сосед г на входе процесса р, что имеетместо соотношение /^ , ■< gf^. А в силу устройства нашего алгоритма событиеgrp предшествует dp.□В алгоритме по каждому каналу передается D сообщений, и поэтому егосложность по числу обменов сообщениями равна \E\D.

Нужно иметь в виду, од­нако, что здесь |£| обозначает количество односторонних каналов. Если нашалгоритм используется для неориентированной сети, то каждый ее канал следу­ет рассматривать как два односторонних канала, и поэтому сложность по числусообщений будет равна 2\E\D.Фазовый алгоритм для клик. Если сеть является кликой, то ее диаметр ра­вен 1. В таком случае от каждого соседа должно быть получено в точности односообщение и каждому процессу достаточно подсчитать общее число полученныхсообщений, вместо того чтобы подсчитывать по отдельности сообщения, полу­ченные от каждого соседа на выходе (см. алгоритм 6.7).

При этом сложность почислу сообщений будет равна N(N — 1) и алгоритму будет хватать всего лишьO(logiV) битов внутренней памяти.212Гл. 6.var RecpВолновые алгоритмы и алгоритмы обхода: 0.. jV - 1 init 0 ;(* Число полученных сообщений *)Sentp : 0..1init 0 ;(* Число сообщений, отправленных каждому соседу *)b egin if р is initiator thenb egin forall r 6 Neighp do send (tok) to r ;Sentp := Sentp + 1end;w h ile Recp < #Neighp dobegin receive (tok)Recp := Recp + 1 ;if Sentp = 0 th enb egin forall r 6 Neighp do send (tok) to r ;Sentp := Sentp + 1endend;decideendАлгоритм 6.7.Фазовый алгоритм для клик6.2.6. Алгоритм ФиннаАлгоритм Финна (см.

[79]) — это еще один волновой алгоритм, который мож­но использовать для произвольных ориентированных сетей. Здесь не требуется,чтобы диаметр сети был известен заранее, но зато этот алгоритм опирается наоднозначную идентифицируемость процессов. В сообщениях процессы обменива­ются отличительными признаками, и это приводит к тому, что битовая сложностьалгоритма становится достаточно большой.В процессе р формируются два множества отличительных признаков 1 п с р иNInCp. Если говорить неформально, то 1 п с р обозначает множество таких процес­сов q, что некоторое событие в q предшествует самому последнему событию, слу­чившемуся в р , a N I n C p обозначает множество таких процессов q, что у каждогососеда г процесса q какое-нибудь событие в г предшествует самому последнемусобытию, случившемуся в р .

Формирование этих множеств осуществляется так.Вначале 1 п с р = { р } и N I n c p = 0 . Процесс р отправляет сообщения, в которыхсодержатся 1 п с р и N I n c p , всякий раз, когда одно из этих множеств расширяется.Когда р получает сообщение, содержащее множество I n c и множество Nine, по­лученные отличительные признаки добавляются к соответствующим множествам,которые формирует процесс р. Если процесс р получил сообщения от всех своихсоседей на входе, то отличительный признак р вставляется в N I n c p .

Когда эти двамножества станут одинаковыми, р принимает решение (см. алгоритм 6 .8 ). Исхо­дя из содержательного смысла, который приписан этим множествам, это будетозначать, что, каков бы ни был процесс q, если некоторое событие в q пред­шествует dp, то у всякого соседа г процесса q также произошло какое-нибудь6.2. Семейство волновых алгоритмов213событие, предшествующее dp. Отсюда следует, что для нашего алгоритма требо­вание зависимости соблюдено.По ходу доказательства корректности алгоритма будет показано, что все этосвойственно каждому процессу р, и равенство двух указанных множеств означает,что решению предшествует какое-нибудь событие в каждом процессе.var Incp: set of processesNIncp : set of processesrecp[q\ : bool for q e Inpinit {p} ;init 0 ;init false ;(* индикаторы получения процессом p сообщения от q *)b egin if p is initiator thenforall r e Outp do send (se ts, Incp, NIncp) to r ;w h ile IriCp ф NIncp dob egin receive (se ts, Inc, Nine) from qо ;Incp := Incp u Inc ; NIncp := NIncp U Nine ;recp [<70] := true ;if V<7 € Inp : recp[q] th en NIncp := NIncp U {p} ;if Incp or NIncp has changed th enforall r 6 Outp do send (se ts, Incp, NIncp) to rend;decideendАлгоритм 6.8.

Алгоритм ФиннаТеорема 6.21. Алгоритм Финна (алгоритм 6 .8 ) является волновым ал­горитмом.Д о к а з а т е л ь с т в о . Заметим, что два множества, формируемые каждымпроцессом, могут только увеличиваться. Поскольку суммарный размер этих двухмножеств варьируется от 1 в первом сообщении, передаваемом по каждому ка­налу, до не более чем 2 N в последнем сообщении, общее количество сообщенийограничено величиной 2Af|£|. Рассмотрим вычисление С, в котором есть хотя быодин инициатор, и его последнюю конфигурацию у, которая является заключи­тельной.

Так же как и в доказательстве теоремы 6.20, можно показать, что еслипроцесс р сумел отправить хотя бы одно сообщение (каждому соседу) и q — со­сед процесса р на выходе, то q также сумел отправить по меньшей мере односообщение. Отсюда следует, что каждый процесс сумел отправить хотя бы односообщение (по каждому каналу).Теперь будет показано, что в у каждый процесс принял решение. Во-первых,для каждого ребра pq в конфигурации у выполняется включение lncp С Incq.И в самом деле, совершив последнее изменение множества 1пср, процесс р от­правил сообщение (sets, Incp, NIncp). Как только оно было получено, процесс qвыполнил оператор Iticq := Incq U 1пср.

Сильная связность сети приводит к тому,что 1пср = Incq для всех р и q. Коль скоро р е 1пср и каждое множество Inc214Гл. 6.Волновые алгоритмы и алгоритмы обходасодержит только отличительные признаки процессов, для каждого процесса рв конфигурации у выполняется равенство Incp = Р.Во-вторых, аналогичным образом можно показать, что для каждой пары про­цессов р и q выполняется равенство NIticp = NIncq.

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

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