Предыдущая страница реферата | 23  24  25  26  27  28  29  30  31  32  33 | Следующая страница реферата



[pic]
Рис.6.1 Включение процесса в неиспользуемый канал.

Нижние границы сложности волн. Из леммы 6.4 непосредственно следует, что нижняя граница количества сообщений, которые передаются в волне, равна N-1.
Если событие decide происходит в единственном инициаторе волны (что выполняется всегда в случае алгоритмов обхода), граница равна N сообщениям, а волновые алгоритмы для сетей произвольной топологии используют не менее
|E| сообщений.
Теорема 6.5 Пусть C - волна с одним инициатором p, причем событие decide dp происходит в p. Тогда в C передается не менее N сообщений.
Доказательство. По лемме 6.2 каждому событию в C предшествует событие в p, и, используя каузальную последовательность, как в доказательстве леммы 6.4, нетрудно показать, что в p происходит хотя бы одно событие send. По лемме
6.4 событие send также происходит во всех других процессах, откуда количество посылаемых сообщений составляет не меньше N.
Теорема 6.6 Пусть A - волновой алгоритм для сетей произвольной топологии без начального знания об идентификации соседей. Тогда A передает не менее
|E| сообщений в каждом вычислении.
Доказательство. Допустим, A содержит вычисление C, в котором передается менее |E| сообщений; тогда существует канал xy, по которому в C не передаются сообщения; см. Рис.6.1. Рассмотрим сеть G', полученную путем включения одного узла z в канал между x и y. Т.к. узлы не имеют знания о соседях, начальное состояние x и y в G' совпадает с их начальным состоянием в G. Это верно и для всех остальных узлов G. Следовательно, все события C могут быть применены в том же порядке, начиная с исходной конфигурации G', но теперь событию decide не предшествует событие в z.
В Главе 7 будет доказана улучшенная нижняя граница количества сообщений децентрализованных волновых алгоритмов для колец и сетей произвольной топологии без знания о соседях; см. Заключение 7.14 и 7.16.

6.1.3 Распространение информации с обратной связью
В этом подразделе будет продемонстрировано применение волновых алгоритмов для случая, когда некоторая информация должна быть передана всем процессам и определенные процессы должны быть оповещены о завершении передачи. Эта задача распространения информации с обратной связью (PIF - propagation of information with feedback) формулируется следующим образом [Seg83].
Формируется подмножество процессов из тех, кому известно сообщение M (одно и то же для всех процессов), которое должно быть распространено, т.е. все процессы должны принять M. Определенные процессы должны быть оповещены о завершении передачи; т.е. должно быть выполнено специальное событие notify, причем оно может быть выполнено только когда все процессы уже получили сообщение M. Алгоритм должен использовать конечное количество сообщений.
Оповещение в PIF-алгоритме можно рассматривать как событие decide.
Теорема 6.7 Каждый PIF-алгоритм является волновым алгоритмом.
Доказательство. Пусть P - PIF-алгоритм. Из формулировки задачи каждое вычисление P должно быть конечным и в каждом вычислении должно происходить событие оповещения (decide). Если в некотором вычислении P происходит оповещение dp, которому не предшествует никакое событие в процессе q, тогда из Теоремы 2.21 и Аксиомы 2.23 следует, что существует выполнение P, в котором оповещение происходит до того, как q принимает какое-либо сообщение, что противоречит требованиям.
Мы должны иметь в виду, что теорема 2.21 выполняется только для систем с асинхронной передачей сообщений; см. Упражнение 6.1.
Теорема 6.8 Любой волновой алгоритм может использоваться как PIF-алгоритм.
Доказательство. Пусть A - волновой алгоритм. Чтобы использовать A как PIF- алгоритм, возьмем в качестве процессов, изначально знающих M, стартеры
(инициаторы) A. Информация M добавляется к каждому сообщению A. Это возможно, поскольку по построению стартеры A знают M изначально, а последователи не посылают сообщений, пока не получат хотя бы одно сообщение, т.е. пока не получат M. Событию decide в волне предшествуют события в каждом процессе; следовательно, когда оно происходит, каждый процесс знает M, и событие decide можно считать требуемым событием notify в
PIF-алгоритме.
Построенный PIF-алгоритм имеет такую же сложность сообщений, как и алгоритм
A и обладает всеми другими качествами A, описанными в Подразделе 6.1.1, кроме битовой сложности. Битовая сложность может быть уменьшена путем добавления M только к первому сообщению, пересылаемому через каждый канал.
Если w - количество бит в M, битовая сложность полученного алгоритма превышает битовую сложность A на w*|E|.

6.1.4 Синхронизация
В этом разделе будет рассмотрено применение волновых алгоритмов для случаев, когда должна быть достигнута глобальная синхронизация процессов.
Задача синхронизации (SYN) формулируется следующим образом [Fin79]. В каждом процессе q должно быть выполнено событие aq, и в некоторых процессах должны быть выполнены события bp, причем все события aq должны быть выполнены по времени раньше, чем будет выполнено какое-либо событие bp.
Алгоритм должен использовать конечное количество сообщений.
В SYN-алгоритмах события bp будут рассматриваться как события decide.
Теорема 6.9 Каждый SYN-алгоритм является волновым алгоритмом.
Доказательство. Пусть S - SYN-алгоритм. Из формулировки задачи каждое вычисление S должно быть конечным и в каждом вычислении должно происходить событие bp (decide). Если в некотором вычислении S происходит событие bp, которому каузально не предшествует aq, тогда (по Теореме 2.21 и Аксиоме
2.23) существует выполнение S, в котором bp происходит ранее aq.
Теорема 6.10 Любой волновой алгоритм может использоваться как SYN-алгоритм.
Доказательство. Пусть A - волновой алгоритм. Чтобы преобразовать A в SYN- алгоритм, потребуем, чтобы каждый процесс q выполнял aq до того, как q пошлет сообщение в A или примет решение в A. Событие bp происходит после события decide в p. Из леммы 6.4, каждому событию decide каузально предшествует aq для любого q.
Построенный SYN-алгоритм имеет такую же сложность сообщений, как и A, и обладает всеми другими свойствами A, описанными в Подразделе 6.1.1.

6.1.5 Вычисление функций инфимума
В этой главе будет продемонстрировано применение волновых алгоритмов для вычисления функций, значения которых зависят от входов каждого процесса. В качестве представителей таких функций будут рассмотрены алгоритмы, вычисляющие инфимум по всем входам, которые должны быть извлечены из частично упорядоченного множества.
Если (X, ?) - частичный порядок, то c называют инфимумом a и b, если c ? a, c ? b, и ? d : ( d ? a & d ? b ? d ? c). Допустим, что X таково, что инфимум всегда существует; в этом случае инфимум является единственным и обозначается как a ? b. Т.к. ? - бинарный оператор, коммутативный (a ? b = b ? a) и ассоциативный (т.е. a ? (b ? c) = (a ? b) ? c), операция может быть обобщена на конечные множества: inf { j1, ..., j k} = j1 ? ... ? j k .
Задача вычисления инфимума формулируется следующим образом. Каждый процесс q содержит вход jq, являющийся элементом частично упорядоченного множества
X. Потребуем, чтобы определенные процессы вычисляли значение inf {jq : q ?
P} и чтобы эти процессы знали, когда вычисление завершается. Они записывают результат вычисления в переменную out и после этого не могут изменять ее значение.
Событие write, которое заносит значение в out, рассматривается в INF- алгоритме как событие decide.
Теорема 6.11 Каждый INF-алгоритм является волновым алгоритмом.
Доказательство. Пусть I - INF-алгоритм. Предположим, что существует вычисление C алгоритма I с начальной конфигурацией ?, в котором p записывает значение J в outp и этому событию write не предшествует никакое событие в q. Рассмотрим начальную конфигурацию ?', которая аналогична ? за исключением того, что q имеет другой вход jq', выбранный так, что jq'?< J.
Так как никакое применение входа q не предшествует каузально событию write процесса p в C, все события C, предшествующие событию write, применимы в том же порядке, начиная с ?'. В полученном вычислении p записывает ошибочный результат J, так же как в C.
Теорема 6.12 Любой волновой алгоритм может быть использован для вычисления инфимума.
Доказательство. Допустим, что дан волновой алгоритм A. Назначим каждому процессу q дополнительную переменную vq, которой придадим начальное значение jq. Во время волны эти переменные переприсваиваются следующим образом. Всякий раз, когда процесс q посылает сообщение, текущее значение vq включается в сообщение. Всякий раз, когда процесс q получает сообщение со значением v, vq присваивается значение vq ? v. Когда в процессе p происходит событие decide, текущее значение vp заносится в outp.
Теперь нужно показать, что в результат заносится правильное значение.
Обозначим правильный ответ через J, т.е. J = inf { jq: q ? P}. Для события a в процессе q обозначим через v(a) значение vq сразу после выполнения a.
Т.к. начальное значение vq равно jq, и в течение волны оно только уменьшается, неравенство v(a) ? jq сохраняется для каждого события a в q.
Из присваивания v следует, что для событий a и b, a ? b ? v(a) ? v(b).
Кроме того, т.к. v всегда вычисляется как инфимум двух уже существующих величин, неравенство J ? v выполняется для всех величин в течение волны.
Таким образом, если d - событие decide в p, значение v(d) удовлетворяет неравенству J ? v(d) и, т.к. событию d предшествует хотя бы одно событие в каждом процессе q, v(d) ? jq для всех q. Отсюда следует, что J = v(d).
Построенный INF-алгоритм обладает всеми свойствами A, кроме битовой сложности, поскольку к каждому сообщению A добавляется элемент X. Понятие функции инфимума может показаться довольно абстрактным, но фактически многие функции могут быть выражены через функцию инфимума, как показано в
[Tel91b, Теорема 4.1.1.2].
Аксиома 6.13 (Теорема об инфимуме) Если * - бинарный оператор на множестве
X, причем он: коммутативен, т.е. a * b = b * a, ассоциативен, т.е. (a * b) * c = a * (b * c), и идемпотентен, т.е. a * a = a то существует отношение частичного порядка ? на X такое, что * - функция инфимума.
Среди операторов, удовлетворяющих этим трем критериям - логическая конъюнкция и дизъюнкция, минимум и максимум целых чисел, наибольший общий делитель и наименьшее общее кратное целых чисел, пересечение и объединение множеств.
Заключение 6.14 &, ?, min, max, НОД, НОК, ? и ? величин, локальных по отношению к процессам, могут быть вычислены за одну волну.
Вычисление операторов, которые являются коммутативными и ассоциативными, но не идемпотентны, рассматривается в Подразделе 6.5.2.

6.2 Волновые алгоритмы
В следующих трех разделах будет представлено несколько волновых алгоритмов и алгоритмов обхода. Все тексты алгоритмов даны для процесса p.

6.2.1 Кольцевой алгоритм
В этом разделе будет приведен алгоритм для кольцевой сети. Этот же алгоритм может быть применен для Гамильтоновых сетей, где один фиксированный
Гамильтонов цикл проходит через все процессы. Предположим, что для каждого процесса p задан сосед Nextp такой, что все каналы, выбранные таким образом, составляют Гамильтонов цикл.
Алгоритм является централизованным; инициатор посылает сообщение
(называемое маркером) вдоль цикла, каждый процесс передает его дальше и когда оно возвращается к инициатору, инициатор принимает решение; см.
Алгоритм 6.2.

Для инициатора: begin send to Nextp; receive ; decide end
Для не-инициатора: begin receive ; send to Nextp end

Алгоритм 6.2 Кольцевой алгоритм.

Теорема 6.15 Кольцевой алгоритм (Алгоритм 6.2) является волновым алгоритмом.
Доказательство. Обозначим инициатор через p0. Так как каждый процесс посылает не более одного сообщения, алгоритм передает в целом не больше N сообщений.
За ограниченное количество шагов алгоритм достигает заключительной конфигурации. В этой конфигурации p0 уже переслал маркер, т.е. выполнил оператор send в своей программе. Кроме того, ни одно сообщение не передается ни по одному каналу, иначе оно может быть получено и конфигурация не будет заключительной. Также, ни один процесс, кроме p0, не
«задерживает» маркер (т.е. получил, но не передал дальше ), иначе процесс может послать и конфигурация не будет конечной.
Следовательно, (1) p0 отправил маркер, (2) для любого p, пославшего маркер,
Nextp получил маркер, и (3) каждый p ? p0, получивший маркер, отправил маркер. Из этого и свойства Next следует, что каждый процесс отправил и получил маркер. Т.к. p0 получил маркер и конфигурация конечна, p0 выполнил оператор decide.
Получение и отправка каждым процессом p ? p0 предшествует получению маркера процессом p0, следовательно, условие зависимости выполнено.

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

var recp[q] for each q ? Neighp : boolean init false ;

(* recp[q] = true, если p получил сообщение от q *)

begin while # {q : recp[q] is false} > 1 do begin receive from q ; recp[q] := true end ;

(* Теперь остался один q0, для которого recp[q0] = false *) send to q0 with recp[q0] is false ; x : receive from q0 ; recp[q0] := true ; decide

(* Сообщить другим процессам о решении: forall q ? Neighp, q ? q0 do send to q *) end

Алгоритм 6.3 Древовидный алгоритм.
Чтобы показать, что этот алгоритм является волновым, введем некоторые обозначения. Пусть fpq - событие, где p посылает сообщение q, а gpq - событие, где q получает сообщение от p. Через Tpq обозначим подмножество процессов, которые достижимы из p без прохождения по дуге pq (процессы на стороне p дуги pq); см. Рис.6.4.
Из связности сети следует, что (см. Рис.6.4)
Tpq = [pic] и ( = [pic]

[pic]
Рис. 6.4 Поддеревья Tpq.

Оператор forall в комментариях в Алгоритме 6.3 будет обсуждаться в конце этого подраздела; в следующей теореме речь идет об алгоритме без этого оператора.
Теорема 6.16 Древовидный алгоритм (Алгоритм 6.3) является волновым алгоритмом.
Доказательство. Т.к. каждый процесс посылает не более одного сообщения, в целом алгоритм использует не более 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, а из (2N-2) - K ? 2(N-K) + K следует, что -2 ? 0; мы пришли к противоречию, следовательно, хотя бы один процесс в
? принимает решение. См. Упражнение 6.5.
Наконец, нужно показать, что решению предшествует событие в каждом процессе. Пусть fpq - событие, где p посылает сообщение q, а gpq - событие, где q получает сообщение от p. Применяя индукцию по событиям получения сообщений, можно доказать, что ? s ? Tpq ? e ? Cs: e ? gpq.
Предположим, что это выполняется для всех событий получения сообщений, предшествующих gpq. Из того, что событию gpq предшествует fpq (в процессе p), и из алгоритма p следует, что для всех r ? Neighp при r ? q, grp предшествует fpq. Из гипотезы индукции следует, что для всех таких r и для всех s ? Trp существует событие e ? Cs, где e ? grp, следовательно, e ? gpq.
Решению dp в p предшествуют grp для всех r ? Neighp, откуда следует, что
? s ? P ? e ? Cs : e ? dp.
Читатель может смоделировать вычисление алгоритма на небольшом дереве
(например, см. дерево на Рис.6.4) и самостоятельно убедиться в справедливости следующих замечаний. В Алгоритме 6.3 существует два процесса, которые получают сообщения через все свои каналы и принимают решение; все остальные тем временем ожидают сообщения с счетчиком команд, установленным на x, в заключительной конфигурации. Если к программе добавить оператор forall (в скобках комментария в Алгоритме 6.3), то все процессы принимают решение и в конечной конфигурации каждый процесс находится в конечном состоянии. Модифицированная программа использует 2N-2 сообщений.

6.2.3 Эхо-алгоритм
Эхо-алгоритм - это централизованный волновой алгоритм для сетей произвольной топологии. Впервые он был представлен Чангом [Chang; Cha82] и поэтому иногда называется эхо-алгоритмом Чанга. Более эффективная версия, которая и представлена здесь, была предложена Сегаллом [Segall; Seg83].
Алгоритм распространяет сообщения по всем процессам, таким образом определяя остовное дерево, как определено в Лемме 6.3. Маркеры «отражаются» обратно через ребра этого дерева аналогично потоку сообщений в древовидном алгоритме. Алгоритм обозначен как Алгоритм 6.5.
Инициатор посылает сообщения всем своим соседям. После получения первого сообщения не-инициатор пересылает сообщения всем своим соседям, кроме того, от которого было получено сообщение. Когда не-инициатор получает сообщения от всех своих соседей, эхо пересылается родителю (father). Когда инициатор получает сообщения от всех своих соседей, он принимает решение.

var recp : integer init 0 ; (* Счетчик полученных сообщений *) fatherp : P init udef ;

Для инициатора: begin forall q ? Neighp do send to q ; while recp < # Neighp do begin receive ; recp := recp + 1 end ; decide end ;
Для не-инициатора: begin receive from neighbor q ; fatherp := q ; recp := recp
+ 1 ; forall q ? Neighp, q ? fatherp do send to q ; while recp < # Neighp do begin receive ; recp := recp + 1 end ; send to fatherp end

Алгоритм 6.5 Эхо-алгоритм.
Теорема 6.17 Эхо-алгоритм (Алгоритм 6.5) является волновым алгоритмом.
Доказательство. Т.к. каждый процесс посылает не более одного сообщения по каждому инцидентному каналу, количество сообщений, пересылаемых за каждое вычисление, конечно. Пусть ? - конечная конфигурация, достигаемая в вычислении C с инициатором p0.
Для этой конфигурации определим (подобно определению в лемме 6.3) граф T =
(P,ET), где pq ? ET ? fatherp = q. Чтобы показать, что этот граф является деревом, нужно показать, что количество ребер на единицу меньше, чем количество вершин (Лемма 6.3 утверждает, что T - дерево, но предполагается, что алгоритм является волновым, что нам еще нужно доказать). Отметим, что каждый процесс, участвующий в C, посылает сообщения всем своим соседям, кроме соседа, от которого он получил первое сообщение (если процесс - не- инициатор). Отсюда следует, что все его соседи получают хотя бы одно сообщение в C и также участвуют в C. Из этого следует, что fatherp ? udef для всех p ? p0. Что T не содержит циклов, можно показать, как в доказательстве Леммы 6.3.
В корне дерева находится p0; обозначим через Tp множество вершин в поддереве p. Ребра сети, не принадлежащие T, называются листовыми ребрами
(frond edges). В ? каждый процесс p, по крайней мере, послал сообщения всем своим соседям, кроме родителя fatherp, следовательно, каждое листовое ребро передавало в C сообщения в обоих направлениях. Пусть fp - событие, в котором p посылает сообщение своему родителю (если в C это происходит), а gp - событие, в котором родитель p получает сообщение от p (если это происходит). С помощью индукции по вершинам дерева можно показать, что
C содержит событие fp для любого p ? p0; для всех s ? Tp существует событие e ? Cs такое, что e ? gp.
Мы рассмотрим следующие два случая. p - лист. p получил в C сообщение от своего родителя и от всех других соседей (т.к. все остальные каналы - листовые). Таким образом, посылка родителю p была возможна, и, т.к. ? - конечная конфигурация, это произошло. Tp содержит только p, и, очевидно, fp ? gp. p - не лист. p получил в C сообщение от своего родителя и через все листовые ребра. По индукции, C содержит fp' для каждой дочерней вершины p' вершины p, и, т.к. ? - конечная конфигурация, C также содержит gp'.
Следовательно, посылка родителю p была возможна, и, т.к. ? - конечная конфигурация, это произошло. Tp состоит из объединения Tp' по всем дочерним вершинам p и из самого p. С помощью индукции можно показать, что в каждом процессе этого множества существует событие, предшествующее gp.
Отсюда следует, также, что p0 получил сообщение от каждого соседа и выполнил событие decide, которому предшествуют события в каждом процессе.
Остовное дерево, которое строится в вычислении Алгоритма 6.5, иногда используют в последовательно выполняемых алгоритмах. (Например, алгоритм
Мерлина-Сегалла (Merlin-Segall) для вычисления таблиц кратчайших маршрутов предполагает, что изначально дано остовное дерево с корнем в v0; см.
Подраздел 4.2.3. Начальное остовное дерево может быть вычислено с использованием эхо-алгоритма). В последней конфигурации алгоритма каждый процесс (кроме p0) запомнил, какой сосед в дереве является его родителем, но не запомнил дочерних вершин. В алгоритме одинаковые сообщения принимаются от родителя, через листовые ребра, и от дочерних вершин. Если требуется знание дочерних вершин в дереве, алгоритм может быть слегка изменен, так чтобы отправлять родителю сообщения, отличные от остальных (в последней операции отправления сообщения для не-инициаторов). Дочерними вершинами процесса тогда являются те соседи, от которых были получены эти сообщения.

6.2.4 Алгоритм опроса
В сетях с топологией клика между каждой парой процессов существует канал.
Процесс может определить, получил ли он сообщение от каждого соседа. В алгоритме опроса, обозначенном как Алгоритм 6.6, инициатор запрашивает у каждого соседа ответ на сообщение и принимает решение после получения всех ответных сообщений.
Теорема 6.18 Алгоритм опроса (Алгоритм 6.6) является волновым алгоритмом.
Доказательство. Алгоритм пересылает по два сообщения через каждый канал, смежный с инициатором. Каждый сосед инициатора отвечает только один раз на первоначальный опрос, следовательно, инициатор получает N-1 ответ. Этого достаточно, чтобы принять решение, следовательно, инициатор принимает решение и ему предшествует событие в каждом процессе.
Опрос может быть использован и в сети с топологией звезда, в которой инициатор находится в центре.

var recp : integer init 0 ; (* только для инициатора *)

Для инициатора: begin forall q ? Neighp do send to q ; while recp < # Neighp do begin receive ; recp := recp + 1 end ; decide end ;
Для не-инициатора: begin receive from q ; send to q end

Алгоритм 6.6 Алгоритм опроса.

6.2.5 Фазовый алгоритм
В этом разделе будет представлен фазовый алгоритм, который является децентрализованным алгоритмом для сетей с произвольной топологией. Алгоритм дан в [Tel91b, Раздел 4.2.3]. Алгоритм может использоваться как волновой для ориентированных сетей.
Алгоритм требует, чтобы процессам был известен диаметр сети, обозначенный в тексте алгоритма как D. Алгоритм остается корректным (хотя и менее эффективным), если процессы вместо D используют константу D' > D. Таким образом, для применения алгоритма необязательно точно знать диаметр сети; достаточно, если известна верхняя граница диаметра (например, N-1). Все процессы должны использовать одну и ту же константу D'. Пелег [Peleg;
Pel90] дополнил алгоритм таким образом, чтобы диаметр вычислялся во время выполнения, но это расширение требует уникальной идентификации.
Общий случай. Алгоритм может использоваться в ориентированных сетях произвольной топологии, где каналы могут передавать сообщения только в одном направлении. В этом случае, соседи p являются соседями по входу
(процессы, которые могут посылать сообщения p) и соседями по выходу
(процессы, которым p может посылать сообщения). Соседи по входу p содержатся в множестве Inp, а соседи по выходу - в множестве Outp.
В фазовом алгоритме каждый процесс посылает ровно D сообщений каждому соседу по выходу. Только после того, как i сообщений было получено от каждого соседа по входу, (i+1)-ое сообщение посылается каждому соседу по выходу; см. алгоритм 6.7.

cons D : integer = диаметр сети ; var recp[q] : 0..D init 0, для каждого q ? Inp ;

(* Количество сообщений, полученных от q *)

Sentp : 0..D init 0 ;

(* Количество сообщений, посланных каждому соседу по выходу *)

begin if p - инициатор then begin forall r ? Outp do send to r ;

Sentp := Sentp + 1 end ; while minq Recp[q] < D do begin receive (от соседа q0) ;

Recp[q0] := Recp[q0] + 1 ; if minq Recp[q] ? Sentp and Sentp < D then begin forall r ? Outp do send to r ;

Sentp := Sentp + 1 end end ; decide end

Алгоритм 6.7 Фазовый алгоритм.
Действительно, из текста алгоритма очевидно, что через каждый канал проходит не более D сообщений (ниже показано, что через каждый канал проходит не менее D сообщений). Если существует ребро pq, то fpq(i) - i-е событие, в котором p передает сообщение q, а gpq(i) - i-е событие, в котором q получает сообщение от p. Если канал между p и q удовлетворяет дисциплине FIFO, эти события соответствуют друг другу и неравенство fpq(i) ? gpq(i) выполняется. Каузальные отношения между fpq(i) и gpq(i) сохраняются и в случае, если канал не является FIFO, что доказывается в следующей лемме.
Лемма 6.19 Неравенство fpq(i) ? gpq(i) выполняется, даже если канал не является каналом FIFO.
Доказательство. Определим mh следующим образом: fpq(mh) - событие отправления сообщения, соответствующее gpq(h), т.е. в своем h-м событии получения q получает mh-е сообщение p. Из определения каузальности fpq(mh) ? gpq(h).
Т.к. каждое сообщение в C получают только один раз, все mh различны, откуда следует, что хотя бы одно из чисел m1, ..., mi больше или равно i. Выберем j ? i так, чтобы mj ? i. Тогда fpq(i) ? fpq(mj) ? gpq(j) ? gpq(i).
Теорема 6.20 Фазовый алгоритм (Алгоритм 6.7) является волновым алгоритмом.
Доказательство. Т.к. каждый процесс посылает не более D сообщений по каждому каналу, алгоритм завершается за конечное число шагов. Пусть ? - заключительная конфигурация вычисления C алгоритма, и предположим, что в C существует, по крайней мере, один инициатор (их может быть больше).
Чтобы продемонстрировать, что в ? каждый процесс принял решение, покажем сначала, что каждый процесс хотя бы один раз послал сообщения. Т.к. в ? по каналам не передается ни одно сообщение, для каждого канала qp Recp[q] =
Sentpq. Также, т.к. каждый процесс посылает сообщения, как только получит сообщение сам, Recp[q] > 0 ? Sentp > 0. Из предположения, что существует хотя бы один инициатор p0, для которого Sentp0 > 0, следует, что Sentp > 0 для каждого p.
Впоследствии будет показано, что каждый процесс принял решение. Пусть p - процесс с минимальным значением переменной Sent в ?, т.е. для всех q
Sentq ? Sentp в ?. В частности, это выполняется, если q - сосед по входу p, и из Recp[q] = Sentq следует, что minq Recp[q] ? Sentp. Но отсюда следует, что Sentp = D; иначе p послал бы дополнительные сообщения, когда он получил последнее сообщение. Следовательно, Sentp = D для всех p, и Recp[q] = D для всех qp, откуда действительно следует, что каждый процесс принял решение.
Остается показать, что каждому решению предшествует событие в каждом процессе. Если P = p0, p1, ..., pl (l ? D) - маршрут в сети, тогда, по
Лемме 6.19,
[pic]

для 0 ? i < l и, по алгоритму,
[pic] для 0 ? i < l - 1. Следовательно, [pic]. Т.к. диаметр сети равен D, для любых q и p существует маршрут q = p0, p1, ..., pl = p длины не более D.
Таким образом, для любого q существует l ? D и сосед по входу r процесса p, такие, что [pic]; на основании алгоритма, [pic]предшествует dp.
Алгоритм пересылает D сообщений через каждый канал, что приводит в сложности сообщений, равной |E|*D. Однако нужно заметить, что |E| обозначает количество направленных каналов. Если алгоритм используется для неориентированной сети, каждый канал считается за два направленных канала, и сложность сообщений равна 2|E|*D.

var recp : 0..N - 1 init 0 ;

(* Количество полученных сообщений *)

Sentp : 0..1 init 0 ;

(* Количество сообщений, посланных каждому соседу *)

begin if p - инициатор then begin forall r ? Neighp do send to r ;

Sentp := Sentp + 1 end ; while Recp < # Neighp do begin receive ;

Recp := Recp + 1 ; if Sentp = 0 then begin forall r ? Neighp do send to r ;

Sentp := Sentp + 1 end end ; decide end

Алгоритм 6.8 Фазовый алгоритм для клики.

Фазовый алгоритм для клики. Если сеть имеет топологию клика, ее диаметр равен 1; в этом случае от каждого соседа должно быть получено ровно одно сообщение, и для каждого процесса достаточно посчитать общее количество полученных сообщений вместо того, чтобы считать сообщения от каждого соседа по входу отдельно; см. Алгоритм 6.8. Сложность сообщений в этом случае равна N(N-1) и алгоритм использует только O(log N) бит оперативной памяти.

6.2.6 Алгоритм Финна
Алгоритм Финна [Fin79] - еще один волновой алгоритм, который можно использовать в ориентированных сетях произвольной топологии. Он не требует того, чтобы диаметр сети был известен заранее, но подразумевает наличие уникальных идентификаторов процессов. В сообщениях передаются множества идентификаторов процессов, что приводит к довольно высокой битовой сложности алгоритма.
Процесс p содержит два множества идентификаторов процессов, Incp и NIncp.
Неформально говоря, Incp - это множество процессов q таких, что событие в q предшествует последнему произошедшему событию в p, а NIncp - множество процессов q таких, что для всех соседей r процесса q событие в r предшествует последнему произошедшему событию в p. Эта зависимость поддерживается следующим образом. Изначально Incp = {p}, а NIncp = ?.
Каждый раз, когда одно из множеств пополняется, процесс p посылает сообщение, включая в него Incp и NIncp. Когда p получает сообщение, включающее множества Inc и NInc, полученные идентификаторы включаются в версии этих множеств в процессе p. Когда p получит сообщения от всех соседей по входу, p включается в NIncp. Когда два множества становятся равны, p принимает решение; см. Алгоритм 6.9. Из неформального смысла двух множеств следует, что для каждого процесса q такого, что событие в q предшествует dp, выполняется следующее: для каждого соседа r процесса q событие в r также предшествует dp, откуда следует зависимость алгоритма.
В доказательстве корректности демонстрируется, что это выполняется для каждого p, и что из равенства двух множеств следует, что решению предшествует событие в каждом процессе.
Теорема 6.21 Алгоритм Финна (Алгоритм 6.9) является волновым алгоритмом.
Доказательство. Заметим, что два множества, поддерживаемые каждым процессом, могут только расширяться. Т.к. размер двух множеств в сумме составляет не менее 1 в первом сообщении, посылаемом по каждому каналу, и не более 2N в последнем сообщении, то общее количество сообщений ограничено
2N*|E|.
Пусть C - вычисление, в котором существует хотя бы один инициатор, и пусть
? - заключительная конфигурация. Можно показать, как в доказательстве
Теоремы 6.20, что если процесс p отправил сообщения хотя бы один раз
(каждому соседу), а q - сосед p по выходу, то q тоже отправил сообщения хотя бы один раз. Отсюда следует, что каждый процесс переслал хотя бы одно сообщение (через каждый канал).

var Incp : set of processes init {p} ;

Рекомендуем скачать другие рефераты по теме: педагогические рефераты, реферат машини.

Предыдущая страница реферата | 23  24  25  26  27  28  29  30  31  32  33 | Следующая страница реферата