Реферат: Распределенные алгоритмы
Волна с одним инициатором определяет остовное дерево сети, где для каждого не-инициатора выбирается канал, через который будет получено первое сообщение.
Лемма 6.3 Пусть C - волна с одним инициатором p; и пусть для каждого не-инициатора q fatherq - это сосед q, от которого q получает сообщение в своем первом событии. Тогда граф T = (P, ET), где ET = {qr: q ¹ p & r = fatherq } - остовное дерево, направленное к p.
Доказательство. Т.к. количество вершин T превышает количество ребер на 1, достаточно показать, что T не содержит циклов. Это выполняется, т.к. если eq - первое событие в q, из того, что qr Î ET следует, что er p eq, а p - отношение частичного порядка.
В качестве события f в пункте (3) Определения 6.1 может быть выбрано событие посылки сообщения всеми процессами q, кроме того, где происходит событие decide.
Лемма 6.4 Пусть C - волна, а dp Î C - событие decide в процессе p. Тогда
" q ¹ p: $ f Î Cq: ( f p dp & f - событие send)
Доказательство. Т.к. C - это волна, существует событие f ÎCq, которое каузально предшествует dp; выберем в качестве f последнее событие Cq, которое предшествует dp. Чтобы показать, что f - событие send, отметим, что из определения каузальности (Определение 2.20) следует, что существует последовательность (каузальная цепочка)
f = e0, e1, ..., ek = dp,
такая, что для любого i < k, ei и ei+1 - либо последовательные события в одном процессе, либо пара соответствующих событий send-receive. Т.к. f - последнее событие в q, которое предшествует dp, e1 происходит в процессе, отличном от q, следовательно f - событие send.
Рис.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 p 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, причем он:
(1) коммутативен, т.е. a * b = b * a,
(2) ассоциативен, т.е. (a * b) * c = a * (b * c), и
(3) идемпотентен, т.е. a * a = a
то существует отношение частичного порядка £ на X такое, что * - функция инфимума.
Среди операторов, удовлетворяющих этим трем критериям - логическая конъюнкция и дизъюнкция, минимум и максимум целых чисел, наибольший общий делитель и наименьшее общее кратное целых чисел, пересечение и объединение множеств.
Заключение 6.14 &, Ú, min, max, НОД, НОК, Ç и È величин, локальных по отношению к процессам, могут быть вычислены за одну волну.
Вычисление операторов, которые являются коммутативными и ассоциативными, но не идемпотентны, рассматривается в Подразделе 6.5.2.
В следующих трех разделах будет представлено несколько волновых алгоритмов и алгоритмов обхода. Все тексты алгоритмов даны для процесса p.
В этом разделе будет приведен алгоритм для кольцевой сети. Этот же алгоритм может быть применен для Гамильтоновых сетей, где один фиксированный Гамильтонов цикл проходит через все процессы. Предположим, что для каждого процесса p задан сосед Nextp такой, что все каналы, выбранные таким образом, составляют Гамильтонов цикл.
Алгоритм является централизованным; инициатор посылает сообщение <tok> (называемое маркером) вдоль цикла, каждый процесс передает его дальше и когда оно возвращается к инициатору, инициатор принимает решение; см. Алгоритм 6.2.
Для инициатора:
begin send <tok> to Nextp; receive <tok>; decide end
Для не-инициатора:
begin receive <tok>; send <tok> to Nextp end
Алгоритм 6.2 Кольцевой алгоритм.
Теорема 6.15 Кольцевой алгоритм (Алгоритм 6.2) является волновым алгоритмом.
Доказательство. Обозначим инициатор через p0. Так как каждый процесс посылает не более одного сообщения, алгоритм передает в целом не больше N сообщений.
За ограниченное количество шагов алгоритм достигает заключительной конфигурации. В этой конфигурации p0 уже переслал маркер, т.е. выполнил оператор send в своей программе. Кроме того, ни одно сообщение <tok> не передается ни по одному каналу, иначе оно может быть получено и конфигурация не будет заключительной. Также, ни один процесс, кроме p0, не «задерживает» маркер (т.е. получил, но не передал дальше <tok>), иначе процесс может послать <tok> и конфигурация не будет конечной. Следовательно, (1) p0 отправил маркер, (2) для любого p, пославшего маркер, Nextp получил маркер, и (3) каждый p ¹ p0, получивший маркер, отправил маркер. Из этого и свойства Next следует, что каждый процесс отправил и получил маркер. Т.к. p0 получил маркер и конфигурация конечна, p0 выполнил оператор decide.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62
