Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 79
Текст из файла (страница 79)
Если был отправленсигнал, то родительской вершиной этого сигнала становится последняя родительская вершина процесса p, которая принадлежит V F . Следовательно, соотношение(2) остается верным. В этом случае указанный сигнал замещает p в качестве последователя вершины fatherp . Поэтому значение scfatherp остается правильным,и равенство (3) будет по-прежнему верным. Структура графа не изменяется, и,значит, соотношение (4) также соблюдается. Никакие деревья не становятся пустыми, и поэтому соотношение (6) сохраняется. В противном случае, т. е. в томслучае, когда имеет место равенство fatherp = p, процесс p играл роль корневойвершины, и тот факт, что p оказался листовой вершиной, означает, что p былединственной вершиной дерева Tp .
Поэтому при удалении этой вершины дерево Tp становится пустым, и, благодаря тому что оператор присваивания придаетпеременной emptyp значение true, соотношение (6) сохраняется.Ap . При получении сигнала число последователей вершины p уменьшаетсяна единицу, и соответствующий оператор присваивания обеспечивает выполнимость равенства (3). Тот факт, что процесс p был родительской вершиной этогосигнала, означает, что он принадлежал множеству V F .
Если выполнялось равенство statep = passive и после получения сигнала обнаружилось, что sc p = 0, товершина p удаляется из графа. Значит, соотношение (5) по-прежнему соблюдается.Если вершина p была удалена из множества VF , то, повторив те же рассуждения, которые применялись при анализе блока I p , можно убедиться в том, чтоинвариант по-прежнему сохраняется.Теорема 8.7. Алгоритм Шави—Франчеза (алгоритм 8.4) является корректным алгоритмом обнаружения завершения вычисления; в нем используется M + W обменов контрольными сообщениями.Д о к а з а т е л ь с т в о. Как при доказательстве теоремы 8.5, можно показать, что число сигналов не превосходит числа базовых сообщений.
Кроме сигналов контрольный алгоритм отправляет только сообщения для одной волны.Значит, всего будет отправлено не более M + W контрольных сообщений.Чтобы обосновать необходимое условие корректности алгоритма, предположим, что базовое вычисление завершилось. Спустя конечное число шагов рассматриваемый алгоритм обнаружения завершения вычисления достигает заключительной конфигурации, и точно так же, как в теореме 8.5, можно показать, чтов этой конфигурации граф F пуст. Следовательно, в распространении волны может участвовать каждый процесс.
И коль скоро была достигнута заключительнаяконфигурация, все события, присущие этой волне, осуществились, включая хотябы одно событие решения, которое было обязано вызвать процедуру Announce.Чтобы обосновать достаточное условие корректности алгоритма, напомним,что процедура Announce вызывается только тогда, когда в волновом алгоритмепринимается решение. Это означает, что каждый процесс p уже отправил сооб-8.3.
Решения на основе волновых алгоритмов299щение по волне или принял решение. А рассматриваемый нами алгоритм устроентак, что процесс p совершает это только тогда, когда empty p имеет значениеtrue. Никакое действие не может вновь придать переменной empty p значениеfalse, и поэтому, когда вызывается процедура Announce, для каждого процесса p переменная emptyp имеет значение true. Тогда согласно соотношению (6)множество VF пусто, и отсюда следует, что предикат term выполнен.Число обменов контрольными сообщениями в алгоритме Шави —Франчеза —это величина такого же порядка, что и нижняя оценка, установленная в теоремах 8.2 и 8.3. Этот алгоритм является оптимальным по сложности в наихудшем случае алгоритмом обнаружения завершения децентрализованных вычислений (при условии, что он снабжен оптимальным волновым алгоритмом).Для применения всех алгоритмов, рассмотренных в этом параграфе, требуется, чтобы каналы связи были двунаправленными; для каждого сообщения,отправленного от p к q, должен быть отправлен сигнал от q к p.
Сложностьв среднем будет такой же, как и сложность в наихудшем случае: для каждоговыполнения алгоритма на одно базовое сообщение приходится одно сигнальноесообщение, а в случае алгоритма Шави—Франчеза, еще и проход ровно однойволны.8.3. Решения на основе волновых алгоритмовЕсть две причины, по которым полезно рассмотреть некоторые другие алгоритмы обнаружения завершения вычисления, помимо тех двух алгоритмов, которые были приведены в § 8.5.2. Во-первых, рассмотренные ранее алгоритмыможно применять только в том случае, когда каналы являются двунаправленными. А во-вторых, хотя эти алгоритмы имеют оптимальную сложность по числу сообщений в наихудшем случае, существуют алгоритмы, имеющие лучшуюсложность в среднем.
Все алгоритмы из предыдущего параграфа используют прикаждом выполнении такое же число сообщений, что и в наихудшем случае.В этом параграфе мы изучим некоторые алгоритмы, в основу которых положен принцип многократного выполнения волнового алгоритма; в конце каждойволны либо обнаруживается завершение вычисления, либо запускается новаяволна.
Завершение вычисления обнаруживается, если в каждом процессе будутвыполнено некоторое локальное условие.Начнем с того, что рассмотрим конкретные примеры таких алгоритмов, в которых в качестве волнового алгоритма выступает кольцевой алгоритм. Предполагается, что топология нашей сети допускает выделение некоторого кольца; однакообмен базовыми сообщениями не ограничивается каналами, входящими в составкольца.
Процессы занумерованы, нумерация ведется от p 0 до pN−1 , и кольцевой алгоритм инициируется процессом p0 путем отправления маркера процессуpN−1 . Процесс pi+1 (для i < N − 1) переправляет этот маркер процессу p i . Обходмаркером кольца завершается, как только он будет возвращен обратно процессуp0 .Первое решение такого рода, которое мы обсудим, — это алгоритм Дейкстры—Фейджена—ван Гастерена (§ 8.3.1). Этот алгоритм обнаруживает заверше-300Гл. 8. Обнаружение завершенияние вычислений с синхронным обменом сообщениями. Сразу нескольким авторамудалось обобщить этот алгоритм для случая вычислений с асинхронным обменомсообщениями; главная проблема здесь состоит в проверке того, что каналы связи пусты.
Мы обсудим решение, предложенное Сафрой (см. § 8.3.2), в которомкаждый процесс проводит подсчет числа отправленных и полученных сообщений. Сравнивая показания счетчиков, можно на самом деле убедиться в том, чтоканалы пусты. Для этой цели можно также воспользоваться подтверждениями(§ 8.3.3); но это решение вновь требует, чтобы каналы были двунаправленными,и число контрольных сообщений будет по меньшей мере равно тому количествусообщений, которое используется алгоритмом Шави —Франчеза.В § 8.3.4 указанный принцип обнаружения завершения вычислений будет обобщен для случая произвольного волнового алгоритма.8.3.1. Алгоритм Дейкстры—Фейджена—ван Гастеренаvar statep : (active, passive) ;Cpq : { statep = active }begin (* процесс p отправляет базовое сообщение,и оно сразу же принимается процессом q *)stateq := activeendIp :{ statep = active }begin statep := passive endАлгоритм 8.5.
Базовый алгоритм с синхронным обменом сообщениямиАлгоритм Дейкстры, Фейджена и ван Гастерена [66] обнаруживает завершениебазового вычисления, в котором используется синхронный обмен сообщениями;действия подобного вычисления приведены на примере алгоритма 8.5. Для такихвычислений условие их завершения имеет следующий вид:term ⇐⇒ ∀p : statep = passive.Можно сравнить приведенный алгоритм и условие term с алгоритмом 8.1 и теоремой 8.1.Построение алгоритма состоит из ряда небольших шагов. Каждый шаг можнолегко понять, а корректность алгоритма является следствием одного инварианта,который мы построим вместе с самим алгоритмом. Такой подход заимствован изстатьи [66] . В дальнейшем символом t условимся обозначать номер того процесса, который удерживает маркер или должен получить маркер, если этот маркерпребывает на этапе пересылки.
Только процесс p t может осуществить передачумаркера, и при этом t уменьшится на 1. Волна угасает, когда t = 0, и, следовательно, инвариант P должен быть выбран так, чтобы о завершении вычисленияможно было судить на основе самого P, того факта, что t = 0, и дополнительной8.3. Решения на основе волновых алгоритмов301информации, представленной в процессе p0 . Инвариантное соотношение должнособлюдаться, когда p0 запускает волну, т. е. когда t = N − 1.В качестве первого приближения будем полагать, что P = P 0 , где P0 задаетсяследующим соотношением:P0 ≡ ∀i (N > i > t) : statepi = passive.И в самом деле, P0 обращается в истину, когда t = N − 1, и если выполняютсяравенства t = 0 и statep0 = passive, то отсюда мы заключаем, что вычислениезавершилось. При передаче маркера P0 сохраняет справедливость только тогда,когда в передаче участвуют одни лишь пассивные процессы; значит, нам приходится ввести следующее правило.Правило 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
