Реферат: Распределенные алгоритмы
Чтобы доказывать безопасность, обратим внимание на то, что алгоритм объявления вызывается после принятия решения в волновом алгоритме. Это означает, что каждый процесс p послал сообщение волны или принял решение, и из алгоритма следует, что emptyp истина, когда p сделает это. Никакое действие не присваивает переменной empty значение ложь повторно, так что (для каждого p) emptyp истина, когда вызывается алгоритм объявления. Из (6), VF пусто, что имеет следствием term. o
Число управляющих сообщений, используемых алгоритмом Shavit-Francez имеет тот же порядок, что и нижнии границы, выведенные в Теоремах 8.2 и 8.3. Алгоритм является оптимальным алгоритмом для обнаружения завершения децентрализованных вычислений для худшего случая (если используется оптимальный волновой алгоритм).
Применение алгоритмов, рассматриваемых в этом разделе требует, чтобы каналы связи были двунаправленными; для каждого основного сообщения, посланного от p в q сигнал должен быть послан от q в p. Сложность с средним случаем равняется сложности в худшем случае; каждое выполнение требует одного сигнального сообщения на одно основное сообщение и, в случае Shavit-Francez алгоритма, точно одного выполнение волны.
8.3 Решения, основанные на волнах
По двум причинам полезно рассмотреть некоторые другие алгоритмы для обнаружения завершения кроме двух алгоритмов, данных в Разделе 8.2. Во первых,
Описанные алгоритмы могут использоваться только когда каналы двунаправленные. Во вторых, хотя сложность по сообщениям этих алгоритмов оптимальна в худшем случае, существуют алгоритмы, которые имеют лучшую сложность в среднем случае. Алгоритмы предыдущего раздела используют их число сообщений в наихудшем случае в каждом выполнении.
В этом разделе будут изучаться некоторые алгоритмы, основанные на повторном выполнении алгоритма волны; в конце каждой волны, либо обнаружевается завершение, либо начинается новая волна. Завершение обнаружено, если локальное условие окажется удовлетворенным в каждом процессе.
Сначала мы рассмотрим конкретные примеры алгоритмов, в которых во всех случаях волновой алгоритм является кольцевым алгоритмом. Для этого предположим, что кольцо вложено как подтопология сети ; но обмен основными сообщениями не ограничен каналам, принадлежащими к кольцу. Процессы перенумерованы с po до pN -1 и кольцевой алгоритм начинается процессом po , посылая маркер процессу pN -1. Процесс pi + 1 (для i < N -1) передает маркер процессу pi. Передвижение маркера заканчивается, когда маркер получает процесс p0.
Первое решение, обсуждаемое в этом классе - алгоритм Dijkstra, Feijen, и Van Gasteren (Подраздел 8.3.1); этот алгоритм обнаруживает завершение вычислений с синхронным прохождением сообщений. Несколько авторов обобщили алгоритм для вычислений с асинхронным прохождением сообщений; главная проблема здесь состоит в том, чтобы проверить, что каналы связи пусты. Мы обсуждаем решение Safra (Подраздел 8.3.2), в котором в каждом процессе подсчитывается число сообщений, которые посланы и получены; сравнивая счетчики можно определить действительно ли каналы являются пустыми. Также возможно использовать подтверждения для этой цели (Подраздел 8.3.3); но это решение снова требует, чтобы каналы были двунаправленными и чтобы число управляющих сообщений равнялось по крайней мере числу, используемому алгоритмом Shavit-Francez.
В Подразделе 8.3.4 принцип обнаружения будет обобщен для использования произвольного волнового алгоритма.
8.3.1 Алгоритм Dijkstra-Feijen-Van Gasteren
Алгоритм Dijkstra, Feijen, и Van Gasteren [DFG83] обнаруживает завершение основного вычисления, используя синхронное прохождение сообщений; действия такого вычисления даются как Алгоритм 8.5. В этих вычислениях, завершение описано с помощью предиката
term Û "p : statep = passive
var statep : (active, passive);,
begin (* p посылает основное сообщение, которое получает q *)
statep := active
end
begin statep := passive end
Алгоритм 8.5 основной алгоритм с синхронными сообщениями.
Сравните алгоритм и term с Алгоритмом 8.1 и Теоремой 8.1.
Алгоритм разработан как последовательность небольших шагов, каждый шаг прост для понимания, и правильность следует из инварианта, который разработан вместе с алгоритмом. Обработка взята из [DFG83]. Обзначим номер процесса, содержащего маркер t ,или если маркер находится в процессе передачи, номер процесса, к которому направляется является маркер. Отправление маркера может быть выполнено только процессом pt, при этом t уменьшается на 1. Волна заканчивает когда t = 0; следовательно инвариант P должен быть выбран такой, что можно было сделать заклющение о наличии завершения из P, t = 0, и другой информации в p0. Инвариант должен сохранятся, когда p0 начинает волну, то есть, когда t = N - 1.
Сначала положим P = P0, где
P0 º "i (N > i> t) : statep = passive.
Действительно, P0 истинен когда t = N - 1, и если t = 0 и statepp0 = passive, из этого утверждения можно сделать заключение о завершение. Отправление маркера сохраняет P0, если только маркер отправляют пассивные процессы, поэтому мы принимаем следующее правило.
Правило 1. Процесс только тогда управляет маркером, когда он пассивен.
В этом режиме, P сохраняется с помощью отправления маркера и также с помощью внутренних действи1; к сожалению, P не сохраняется действиями связи. Предикат P0 может принимать значение ложь, когда процесс pj активизируется процессом pi, где j > t и i £ t; см. Упражнение 8.4. Так как P0 может принять значение ложь, P заменяется более слабым утверждением (P0 Ú P1), где P1 выбирается так, что каждый раз когда P0 принимает значение ложь, P1 является истинным. Каждому процессу присваивается цвет, белый или черный, и пусть P = (P0 Ú P1) где
P1 º $ j (t ³ j ³ 0) : colorpj = black.
Каждый раз, когда P0 принимает значение ложь , P1 является или становится истинным, если цвет посылающего процесса черный.
Правило 2. Посылающие процессы становятся черными.
Так как (P Ù colorp0 = white Ù t = 0) Þ Ø P1, все еще возможно обнаружить завершение с новым инвариантом, а именно, смотря является ли p0 белым (и пассивным) когда он обрабатывает маркер.
Ослабление P предотвращает обращение предиката в ложь при совершении собыий получения и передачи сообщений; но более слабое утверждение может принять значение ложь при отправлении маркера, а именно, если процесс t - единственный черный процесс и он передает маркер. Ситуация исправляется дальнейшим ослаблением P. Пусть маркер тоже имеет цвет (белый или черный), и P ослабим до (P0 Ú P1 Ú P2), где
P2 º маркер черный.
Отправление маркера сохраняет P2, если черные процессы отправляют черный маркер.
Правило 3. Когда черный процесс отличный от p0 посылает маркер, маркер становится черным.
Так как (маркер белый) Þ Ø P2, завершение все еще может обнаружиться процессом p0, а именно, по тому получает ли он белый маркер (и белый ли он сам и пассивный).
Действительно, теперь можно проверить, что внутренние действия, основная соммуникации, и отправление маркера сохраняют P. Присвоение маркеру черного цвета представляет явление неудачных волн; завершение не может быть определено процессом p0, если возвращающийся маркер черный. Если волна заканчивается неудачно, должна быть начата новая.
Страницы: 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
