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

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

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

Двуместная операция П является коммутативной (а П b = b П а)и ассоциативной (а П (Ь П с) = ( а П Ь) П с), и поэтому ее можно распространитьна конечные множества:in f{ / 1,j k } = /1 п ••• п д .Проблема вычисления точной нижней грани (Infimum Computation, INF) та­кова. Все процессы q наделены входными данными j q, которые являются элемен­тами частично упорядоченного множества X. Требуется, чтобы некоторые выде­ленные процессы вычислили значение inf{/p : q <ЕР} и чтобы эти процессы были6.1. Определение и применение волновых алгоритмов201осведомлены о завершении вычисления.

Они записывают результат вычисленияв переменной out, и им не разрешается впоследствии изменять значение этойпеременной.Запись значения в переменную out, рассматривается как событие decideв INF-алгоритме.Теорема 6.11. Каждый INF-алгоритм является волновым алгоритмом.Д о к а з а т е л ь с т в о . Пусть / — это некоторый INF-алгоритм. Предпо­ложим, что существует вычисление С алгоритма / с начальной конфигурацией у,в котором процесс р записывает значение I в переменной outp, и этому собы­тию записи не предшествует никакое событие в процессе q. Тогда рассмотримначальную конфигурацию у7, отличающуюся от у только тем, что q имеет дру­гие входные данные j'q, которые выбраны так, чтобы выполнялось соотношение1 j'q.

Поскольку никакое использование входных данных процесса q в вычис­лении С не является причинно-следственным предшественником события записив р, все события С, предшествующие этому событию записи, происходят в томже самом порядке и для вычисления, начинающегося с у'. В образовавшемсявычислении р записывает такой же результат J, как и в вычислении С, но теперьэтот результат ошибочный.□Теорема 6.12. Каждый волновой алгоритм можно использовать длявычисления точной нижней грани.Д о к а з а т е л ь с т в о .

Пусть задан алгоритм А. Придадим каждому про­цессу q дополнительную переменную vq, которая инициализирована элементом j q.По ходу волны значения этой переменной претерпевают следующие изменения.Всякий раз, когда процесс q отправляет сообщение, предусмотренное алгорит­мом А, текущее значение vq включается в сообщение.

Всякий раз, когда процессq получает сообщение, предусмотренное алгоритмом А и содержащее значение и,переменная vq полагается равной vq П v. Когда в процессе р происходит событиеdecide, текущее значение vp записывается в outp.Покажем, что алгоритм выдает правильное значение. Правильным называетсятакой ответ /, что J = inf{jq : geP }.

Для всякого события а в процессе q обозна­чим символом г/Р значение vq сразу после осуществления события а. Посколькувначале значение vq было равно jq и по ходу волны могло только уменьшиться,^'соотношение v ^ ^ jq соблюдается для каждого события а в q. Присваиванияпеременной v устроены так, что для любых событий а и b имеет место соотно­шение а ■< b =>^ v® . Кроме того, поскольку v вычисляется как точнаянижняя грань уже существующих значений, соотношение / ^ v соблюдается длявсех значений по ходу волны. Таким образом, если d — это событие decide в р,то значение v^ удовлетворяет соотношению J ^ v^d\ а поскольку событию dпредшествует хотя бы одно событие в каждом процессе q, мы имеем^ jq длявсех q. Отсюда следует, что J = v<d).□Построенный INF-алгоритм обладает всеми теми же свойствами, что и Л, заисключением битовой сложности, поскольку к каждому сообщению А присоеди­нялся элемент из X.

Понятие функции точной нижней грани может показаться202Гл. 6.Волновые алгоритмы и алгоритмы обходадовольно-таки абстрактным, но на самом деле многие функции могут быть пред­ставлены как точные нижние грани, о чем свидетельствует работа [187, теоре­ма 4.1.1.2].Теорема 6.13 (о точной нижней грани).

Пусть * — это такая двух­местная операция на множестве X, которая обладает следующими свой­ствами:1) операция * коммутативна, т.е. a x b = Ьх а,2 ) операция х ассоциативна, т.е. (ах Ь)х с = а х (Ь х с),3) операция х идемпотентна, т.е. а х а = а.Тогда существует частичный порядок ^ на X, для которого х являетсяфункцией точной нижней грани.К числу операций, удовлетворяющих трем перечисленным выше требованиям,относятся логические конъюнкция и дизъюнкция, функции минимума и максиму­ма на множестве целых чисел, наибольший общий делитель и наименьшее общеекратное на множестве целых чисел, а также операции пересечения и объединениямножеств.Следствие 6.14.

Функции A, V, min, max, НОК, НОД, П, и U, зависящиеот значений, локализованных во всех процессах, можно вычислить по ходуодной единственной волны.Вычисление операций, которые являются коммутативными, ассоциативными,но не идемпотентными, рассматривается в § 6.5.2.6.2. Семейство волновых алгоритмовВ следующих трех параграфах представлено семейство волновых алгорит­мов и алгоритмов обхода. Во всех случаях описание алгоритма приводится длявыделенного процесса р.6.2.1. Кольцевой алгоритмВ этом параграфе будет представлен волновой алгоритм для кольцевой сети.Этот же самый алгоритм можно использовать и для гамильтоновой сети, в ко­торой информация о некотором фиксированном гамильтоновом цикле заложенаво всех процессах. Предполагается, что каждому процессу р предписан соседNextp так, чтобы каналы связи между выделенными таким образом соседямиобразовывали гамильтонов цикл.Алгоритм является централизованным: инициатор отправляет сообщение tok(оно называется маркером) по циклу, каждый процесс передает его далее, и,когда оно возвращается инициатору, тот принимает решение (см.

алгоритм 6 . 1 ).Теорема 6.15. Кольцевой алгоритм (алгоритм 6.1) является волновымалгоритмом.6.2. Семейство волновых алгоритмов203Д о к а з а т е л ь с т в о . Пусть инициатором является процесс р о. Посколь­ку каждый процесс отправляет не более одного сообщения, всего в алгоритмепроисходит обмен не более N сообщениями.Для инициатора:b e g i n send t o k to Nextp ; receive t o k ; decide e n dДля неинициатора:b e g i n receive t o k ; send t o k to Nextp e n dА л г о р и т м 6 .1 . Кольцевой алгоритмЧерез конечное число шагов алгоритм достигает заключительной конфигу­рации.

В этой конфигурации процесс ро уже отправил маркер, т. е. выполнилоператор send своей программы. При этом никакое сообщение tok не передаетсяни по одному каналу, ибо иначе оно бы могло быть получено и конфигурациюнельзя было бы считать заключительной. Кроме того, ни один процесс, отличныйот ро, не «хранит» маркер (т. е. уже получил, но еще не отправил tok), ибо иначеэтот процесс мог бы отправить tok и конфигурация была бы не заключительной.Приходим к следующему заключению:1 ) процесс ро уже отправил маркер,2) для каждого процесса р, отправившего маркер, процесс Nextp уже полу­чил этот маркер,3) каждый процесс р Ф ро, получивший маркер, уже отправил маркер.Отсюда, а также из свойства Next вытекает, что каждый процесс уже получили уже отправил маркер. Поскольку процесс ро уже получил маркер, и конфигу­рация является заключительной, процесс ро выполнил оператор decide.Получение и отправление сообщения tok каждым процессом р ф ро предше­ствует событию получения маркера процессом ро.

Значит, условие зависимостисоблюдено.□6.2.2. Древесный алгоритмВ этом параграфе будет представлен волновой алгоритм для древесной се­ти. Этот же алгоритм можно использовать и для произвольной сети, если иметьдоступ к остовному дереву этой сети. Предполагается, что все листья сети запус­кают наш алгоритм. Каждый процесс отправляет в точности одно сообщение напротяжении работы алгоритма. Если процесс уже получил сообщение по каждо­му из инцидентных ему каналов, кроме одного (это условие первоначально вернодля листьев), то он отправляет сообщение по оставшемуся каналу. Если процессуже получил сообщение по всем инцидентным ему каналам, то он принимает ре­шение (см. алгоритм 6 .2 ).Для доказательства того, что этот алгоритм является волновым, потребуютсянекоторые обозначения.

Будем использовать запись fpq для обозначения событияотправления сообщения процессом р процессу q, a gpq — для обозначения со­бытия приема процессом q сообщения от процесса р. Обозначим символом TpqГл. 6.204Волновые алгоритмы и алгоритмы обходамножество процессов, которые достижимы из р без прохождения по ребру pq(процессы, лежащие в дереве «по ту же сторону» этого ребра, что и вершина р).Из связности сети следуют соотношения (см. рис. 6.3)Tpq =(JTrp U {р}(Jи Р = {р} иТгр.reNeighpreN eighp \ { q }for each q 6 N e i g h p : boolean i n i t false ;(* recp [q] принимает значение true, если p уже получил сообщение от q *)v a r recp [q\false} > 1 d oreceive ( t o k ) from q ; recp [q] := true e n d ;(* Теперь есть е д и н с т в е н н ы й qo, для которого recp [qo\ имеет значение false *)send ( t o k ) to qo with recp [qo] = false ;x: receive ( t o k ) from qo ; recp [qo] := true ;b e g i n w h i l e # { q : recp [q\ =b eg ind ecide(* Оповестить другие процессы о решении:t o rail q 6 N e ig h p , q qh qo do send ( t o k ) to q *)endА л г о р и т м 6.2.Д р е в е с н ы й алгоритмСмысл «закомментированного» оператора forall в алгоритме 6.2 мы обсудимв конце этого параграфа.

Следующая теорема касается того варианта указанногоалгоритма, в котором не содержится этого оператора.Теорема 6.16. Древесный алгоритм (алгоритм 6.2) является волновымалгоритмом.Д о к а з а т е л ь с т в о . Поскольку каждый процесс отправляет не болееодного сообщения, всего в алгоритме используется не более N сообщений. От­сюда следует, что алгоритм достигает заключительной конфигурации у спустяконечное число шагов. Мы покажем, что в у хотя бы в одном из процессов ужепроизошло событие decide.Пусть F — это число битов гес со значением false в конфигурации у, а К —количество процессов, которые уже отправили сообщения в конфигурации у.

По­скольку в у никаких сообщений не пересылается (иначе конфигурация у не былабы заключительной), F = (2N —2) —К. Общее число битов гес равно 2N —2, и Киз них имеют значение true.Допустим, что ни один из процессов не принял решения в у. Тогда N — Кпроцессов, которые в у еще не отправляли сообщения, имеют в гес по меньшеймере два бита со значением false; в противном случае они могли бы отправитьсообщение, вопреки тому что у —заключительная конфигурация. Кроме того, Кпроцессов, которые в у уже отправили сообщение, имеют в гес хотя бы по одно­му биту со значением false; в противном случае они могли бы принять решениевопреки сделанному предположению о у. Значит, F > 2 (N —K)+K, и из неравен-2056.2. Семейство волновых алгоритмовТпа и Та,о••Ц Wу *VА— •“•тДекомпозиция ТрцА— ••тДекомпозиция ТРис.

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

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