Распределенные алгоритмы (стр. 44 из 85)

Теперь нужно показать, что в результат заносится правильное значение. Обозначим правильный ответ через J, т.е. J = inf { j_q: q Î P}. Для события a в процессе q обозначим через v^(a) значение v_q сразу после выполнения a. Т.к. начальное значение v_q равно j_q, и в течение волны оно только уменьшается, неравенство v^(a) £ j_q сохраняется для каждого события a в q. Из присваивания v следует, что для событий a и b, a p b Þ v^(a) ³ v^(b). Кроме того, т.к. v всегда вычисляется как инфимум двух уже существующих величин, неравенство J £ v выполняется для всех величин в течение волны. Таким образом, если d - событие decide в p, значение v^(d) удовлетворяет неравенству J £ v^(d) и, т.к. событию d предшествует хотя бы одно событие в каждом процессе q, v^(d) £ j_q для всех q. Отсюда следует, что J = v^(d).

Построенный INF-алгоритм обладает всеми свойствами A, кроме битовой сложности, поскольку к каждому сообщению A добавляется элемент X. Понятие функции инфимума может показаться довольно абстрактным, но фактически многие функции могут быть выражены через функцию инфимума, как показано в [Tel91b, Теорема 4.1.1.2].

Аксиома 6.13 (Теорема об инфимуме) Если * - бинарный оператор на множестве X, причем он:

(1) коммутативен, т.е. a * b = b * a,

(2) ассоциативен, т.е. (a * b) * c = a * (b * c), и

(3) идемпотентен, т.е. a * a = a

то существует отношение частичного порядка £ на X такое, что * - функция инфимума.

Среди операторов, удовлетворяющих этим трем критериям - логическая конъюнкция и дизъюнкция, минимум и максимум целых чисел, наибольший общий делитель и наименьшее общее кратное целых чисел, пересечение и объединение множеств.

Заключение 6.14 &, Ú, min, max, НОД, НОК, Ç и È величин, локальных по отношению к процессам, могут быть вычислены за одну волну.

Вычисление операторов, которые являются коммутативными и ассоциативными, но не идемпотентны, рассматривается в Подразделе 6.5.2.

6.2 Волновые алгоритмы

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

6.2.1 Кольцевой алгоритм

В этом разделе будет приведен алгоритм для кольцевой сети. Этот же алгоритм может быть применен для Гамильтоновых сетей, где один фиксированный Гамильтонов цикл проходит через все процессы. Предположим, что для каждого процесса p задан сосед Next_p такой, что все каналы, выбранные таким образом, составляют Гамильтонов цикл.

Алгоритм является централизованным; инициатор посылает сообщение <tok> (называемое маркером) вдоль цикла, каждый процесс передает его дальше и когда оно возвращается к инициатору, инициатор принимает решение; см. Алгоритм 6.2.

Для инициатора:

begin send <tok> to Next_p; receive <tok>; decide end

Для не-инициатора:

begin receive <tok>; send <tok> to Next_pend

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

Теорема 6.15 Кольцевой алгоритм (Алгоритм 6.2) является волновым алгоритмом.

Доказательство. Обозначим инициатор через p₀. Так как каждый процесс посылает не более одного сообщения, алгоритм передает в целом не больше N сообщений.

За ограниченное количество шагов алгоритм достигает заключительной конфигурации. В этой конфигурации p₀ уже переслал маркер, т.е. выполнил оператор send в своей программе. Кроме того, ни одно сообщение <tok> не передается ни по одному каналу, иначе оно может быть получено и конфигурация не будет заключительной. Также, ни один процесс, кроме p₀, не «задерживает» маркер (т.е. получил, но не передал дальше <tok>), иначе процесс может послать <tok> и конфигурация не будет конечной. Следовательно, (1) p₀ отправил маркер, (2) для любого p, пославшего маркер, Next_p получил маркер, и (3) каждый p ¹ p₀, получивший маркер, отправил маркер. Из этого и свойства Next следует, что каждый процесс отправил и получил маркер. Т.к. p₀ получил маркер и конфигурация конечна, p₀ выполнил оператор decide.

Получение и отправка <tok> каждым процессом p ¹ p₀ предшествует получению маркера процессом p₀, следовательно, условие зависимости выполнено.

6.2.2 Древовидный алгоритм

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

var rec_p[q] for each q Î Neigh_p : boolean init false ;

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

begin while # {q : rec_p[q] is false} > 1 do

begin receive <tok> from q ; rec_p[q] := true end ;

(* Теперь остался один q₀, для которого rec_p[q₀] = false *)

send <tok> to q₀ with rec_p[q₀] is false ;

x : receive <tok> from q₀ ; rec_p[q₀] := true ;

decide

(* Сообщить другим процессам о решении:

forall q Î Neigh_p, q ¹ q₀do send <tok> to q *)

end

Алгоритм 6.3 Древовидный алгоритм.

Чтобы показать, что этот алгоритм является волновым, введем некоторые обозначения. Пусть f_pq - событие, где p посылает сообщение q, а g_pq - событие, где q получает сообщение от p. Через T_pq обозначим подмножество процессов, которые достижимы из p без прохождения по дуге pq (процессы на стороне p дуги pq); см. Рис.6.4.

Из связности сети следует, что (см. Рис.6.4)

T_pq = и P =

Рис. 6.4 Поддеревья T_pq.

Оператор 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.

Наконец, нужно показать, что решению предшествует событие в каждом процессе. Пусть f_pq - событие, где p посылает сообщение q, а g_pq - событие, где q получает сообщение от p. Применяя индукцию по событиям получения сообщений, можно доказать, что " s Î T_pq $ e Î C_s: e p g_pq.

Предположим, что это выполняется для всех событий получения сообщений, предшествующих g_pq. Из того, что событию g_pq предшествует f_pq (в процессе p), и из алгоритма p следует, что для всех r Î Neigh_p при r ¹ q, g_rp предшествует f_pq. Из гипотезы индукции следует, что для всех таких r и для всех s Î T_rp существует событие e Î C_s, где e p g_rp, следовательно, e p g_pq.

Решению d_p в p предшествуют g_rp для всех r Î Neigh_p, откуда следует, что " s Î P $ e Î C_s : e p d_p.

Читатель может смоделировать вычисление алгоритма на небольшом дереве (например, см. дерево на Рис.6.4) и самостоятельно убедиться в справедливости следующих замечаний. В Алгоритме 6.3 существует два процесса, которые получают сообщения через все свои каналы и принимают решение; все остальные тем временем ожидают сообщения с счетчиком команд, установленным на x, в заключительной конфигурации. Если к программе добавить оператор forall (в скобках комментария в Алгоритме 6.3), то все процессы принимают решение и в конечной конфигурации каждый процесс находится в конечном состоянии. Модифицированная программа использует 2N-2 сообщений.

6.2.3 Эхо-алгоритм

Эхо-алгоритм - это централизованный волновой алгоритм для сетей произвольной топологии. Впервые он был представлен Чангом [Chang; Cha82] и поэтому иногда называется эхо-алгоритмом Чанга. Более эффективная версия, которая и представлена здесь, была предложена Сегаллом [Segall; Seg83].

Алгоритм распространяет сообщения <tok> по всем процессам, таким образом определяя остовное дерево, как определено в Лемме 6.3. Маркеры «отражаются» обратно через ребра этого дерева аналогично потоку сообщений в древовидном алгоритме. Алгоритм обозначен как Алгоритм 6.5.