Реферат: Распределенные алгоритмы
В Главе 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 такое, что * - функция инфимума.
Страницы: 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, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
