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

" q ¹ p: $ f Î C_q: ( f p d_p & f - событие send)

Доказательство. Т.к. C - это волна, существует событие f ÎC_q, которое каузально предшествует d_p; выберем в качестве f последнее событие C_q, которое предшествует d_p. Чтобы показать, что f - событие send, отметим, что из определения каузальности (Определение 2.20) следует, что существует последовательность (каузальная цепочка)

f = e₀, e₁, ..., e_k = d_p,

такая, что для любого i < k, e_i и e_i+1 - либо последовательные события в одном процессе, либо пара соответствующих событий send-receive. Т.к. f - последнее событие в q, которое предшествует d_p, e₁ происходит в процессе, отличном от q, следовательно f - событие send.

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

Нижние границы сложности волн. Из леммы 6.4 непосредственно следует, что нижняя граница количества сообщений, которые передаются в волне, равна N-1. Если событие decide происходит в единственном инициаторе волны (что выполняется всегда в случае алгоритмов обхода), граница равна N сообщениям, а волновые алгоритмы для сетей произвольной топологии используют не менее |E| сообщений.

Теорема 6.5 Пусть C - волна с одним инициатором p, причем событие decide d_pпроисходит в 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 происходит оповещение d_p, которому не предшествует никакое событие в процессе 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 должно быть выполнено событие a_q, и в некоторых процессах должны быть выполнены события b_p, причем все события a_q должны быть выполнены по времени раньше, чем будет выполнено какое-либо событие b_p. Алгоритм должен использовать конечное количество сообщений.

В SYN-алгоритмах события b_p будут рассматриваться как события decide.

Теорема 6.9 Каждый SYN-алгоритм является волновым алгоритмом.

Доказательство. Пусть S - SYN-алгоритм. Из формулировки задачи каждое вычисление S должно быть конечным и в каждом вычислении должно происходить событие b_p (decide). Если в некотором вычислении S происходит событие b_p, которому каузально не предшествует a_q, тогда (по Теореме 2.21 и Аксиоме 2.23) существует выполнение S, в котором b_p происходит ранее a_q.

Теорема 6.10 Любой волновой алгоритм может использоваться как SYN-алгоритм.

Доказательство. Пусть A - волновой алгоритм. Чтобы преобразовать A в SYN-алгоритм, потребуем, чтобы каждый процесс q выполнял a_q до того, как q пошлет сообщение в A или примет решение в A. Событие b_p происходит после события decide в p. Из леммы 6.4, каждому событию decide каузально предшествует a_q для любого 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 { j₁, ..., j _k} = j₁ Ù ... Ù j _k .

Задача вычисления инфимума формулируется следующим образом. Каждый процесс q содержит вход j_q, являющийся элементом частично упорядоченного множества X. Потребуем, чтобы определенные процессы вычисляли значение inf {j_q : q Î P} и чтобы эти процессы знали, когда вычисление завершается. Они записывают результат вычисления в переменную out и после этого не могут изменять ее значение.

Событие write, которое заносит значение в out, рассматривается в INF-алгоритме как событие decide.

Теорема 6.11 Каждый INF-алгоритм является волновым алгоритмом.

Доказательство. Пусть I - INF-алгоритм. Предположим, что существует вычисление C алгоритма I с начальной конфигурацией ¡, в котором p записывает значение J в out_p и этому событию write не предшествует никакое событие в q. Рассмотрим начальную конфигурацию ¡¢, которая аналогична ¡ за исключением того, что q имеет другой вход j_q¢, выбранный так, что j_q¢ < J. Так как никакое применение входа q не предшествует каузально событию write процесса p в C, все события C, предшествующие событию write, применимы в том же порядке, начиная с ¡¢. В полученном вычислении p записывает ошибочный результат J, так же как в C.

Теорема 6.12 Любой волновой алгоритм может быть использован для вычисления инфимума.

Доказательство. Допустим, что дан волновой алгоритм A. Назначим каждому процессу q дополнительную переменную v_q, которой придадим начальное значение j_q. Во время волны эти переменные переприсваиваются следующим образом. Всякий раз, когда процесс q посылает сообщение, текущее значение v_q включается в сообщение. Всякий раз, когда процесс q получает сообщение со значением v, v_q присваивается значение v_q Ù v. Когда в процессе p происходит событие decide, текущее значение v_p заносится в out_p.