Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 78
Текст из файла (страница 78)
Первоначально для каждого процесса р , не являющегося инициатором, справедливо равенство s t a t e p = p a s s i v e , а для каждого инициатора р выполняется условие f a t h e r р = р; отсюда следует соотношение (1). Кроме того, Е р = 0 , и отсюда следует соотношение (2). Поскольку s c p = 0 для каждого процесса р , верно соотношение (3). Так как Vp == { р : р является инициатором} и Е р = 0 , граф F является лесом, образованным из деревьев, состоящих из одной-единственной вершины-инициатора; отсюда следует соотношение (4).
Процессы из множества Vp являются инициаторами,и эти процессы активны; значит, верно соотношение (5). Первоначально условие empty}о равносильно утверждению «р не является инициатором», и деревоТр действительно пусто в том и только том случае, когда процесс р не являетсяинициатором. Это служит обоснованием соотношения (6 ).Sp. Ни один процесс не становится активным при выполнении блока Sp, и ниодин процесс не удаляется из множества VF; значит, соотношение (1) сохраняетсправедливость.Тот факт, что этот блок выполняется, означает, что процесс р, порождающийновую вершину, которая становится его последователем, принадлежит множествуVp, и поэтому соотношение (2) сохраняется.В результате выполнения рассматриваемого блока к множеству Vp присоединяется вершина (mes, р), а к множеству Ер — дуга ((mes, р), р). Следовательно,граф F по-прежнему остается лесом, а переменная scp, увеличивая свое значение, отмечает тем самым появление у вершины р нового последователя.
Значит,соотношения (3) и (4) также соблюдаются.Ни один процесс не становится пассивной листовой вершиной, и ни одинновый процесс не включается в Vp; поэтому соотношение (5) остается верным.Коль скоро к непустому дереву добавляется новая листовая вершина, никакоедерево не становится пустым, а так как никакая переменная empty не изменяетсвоего значения, справедливость соотношения (6 ) сохраняется.Rp. Процесс р либо уже содержался в множестве Vp (в случае fatherp фф udef), либо присоединяется к этому множеству в результате выполнения рассматриваемого блока. Значит, соотношение (1) остается справедливым.Если переменной fatherр присваивается новое значение, то им является имяпроцесса q, а если отправляется сигнал, то родительской вершиной для него ста-2978.2.
Деревья и леса вычисленийновится все тот же процесс q, который содержится в Vp. Поэтому соотношение(2 ) сохраняется.Число последователей процесса q не изменяется, поскольку последователь(mes, q) вершины q замещается либо вершиной р, либо вершиной (sig, q).
А этозначит, что равенство (3) остается верным.Структура нашего графа не изменяется, и поэтому соотношение (4) такжесоблюдается.Ни один процесс не становится пассивной листовой вершиной, и ни одинновый процесс не включается в Vp. Поэтому соотношение (5) остается верным.Ни одно дерево не исчезает, и никакое новое дерево не появляется. Значит,соотношение (6 ) сохраняется.var s t a t e p:scp:fa th e rpe m p ty p( a c t iv e , p a s s i v einteger:P: bool) init if p is initiator then a c t iv e else p a s s i v e ;init 0;init if p is initiator then p else u d e f ;init if p is initiator then f a l s e elset r u e ;{ sta te p =a c t iv e }begin send (mes, p ) ; s c p := s c p + 1 endR^: {Сообщение (mes, q ) поступило процессу p }begin receive (mes, q ) ; s t a t e p := a c t iv e ;if f a t h e r p = u d e f then f a t h e r p := q else send (sig, q ) to qendIp \ { s t a t e p = a c t iv e }begin s t a t e p := p a s s i v e ;if s c p = 0 then (* Удалить p из F *)beginif f a t h e r p = p then e m p t y p := t r u e else send (sig, f a t h e r p ) toSp:fa th e rp;f a t h e r p := u d e fendendAp: { Сигнал (sig, p ) достигает p }begin receive (sig, p ) ; s c p := s c p — 1 ;if s c p = 0 and s t a t e p = p a s s i v e thenbeginif f a t h e r p = p then e m p t y p :=tru eelse send (sig,fa t h e r p)to f a t h e r p ;f a t h e r p := u d e fendendВсе процессы проводят параллельное выполнение волнового алгоритма, причемотправление сообщений или принятие решения разрешается только тем процессам р ,у которых переменная e m p t y р имеет значение true.При осуществлении события d e c id e вызывается процедура A n n o u n c e .Алгоритм 8.4.
Алгоритм Шави— Франчеза1р. Если процесс р становится пассивным, то соотношения (1), (2), (3) и (4)остаются справедливыми. Тот факт, что процесс р ранее был активным, означает,298Гл. 8. Обнаружение завершениячто он принадлежал множеству Vp. Если scp = 0, то процесс р будет удален изVp, и поэтому соотношение (5) остается верным.Посмотрим теперь, что произойдет, когда процесс р будет исключен из F,т. е. когда он станет пассивной листовой вершиной графа F. Если был отправленсигнал, то родительской вершиной этого сигнала становится последняя родительская вершина процесса р, которая принадлежит Vp. Следовательно, соотношение(2) остается верным.
В этом случае указанный сигнал замещает р в качестве последователя вершины fatherp. Поэтому значение scfatherp остается правильным,и равенство (3) будет по-прежнему верным. Структура графа не изменяется, и,значит, соотношение (4) также соблюдается. Никакие деревья не становятся пустыми, и поэтому соотношение (6 ) сохраняется. В противном случае, т. е. в томслучае, когда имеет место равенство fatherр = р, процесс р играл роль корневойвершины, и тот факт, что р оказался листовой вершиной, означает, что р былединственной вершиной дерева Тр.
Поэтому при удалении этой вершины дерево Тр становится пустым, и, благодаря тому что оператор присваивания придаетпеременной emptyp значение true, соотношение (6 ) сохраняется.Ар. При получении сигнала число последователей вершины р уменьшаетсяна единицу, и соответствующий оператор присваивания обеспечивает выполнимость равенства (3). Тот факт, что процесс р был родительской вершиной этогосигнала, означает, что он принадлежал множеству Vp. Если выполнялось равенство statep = passive и после получения сигнала обнаружилось, что scp = 0 , товершина р удаляется из графа.
Значит, соотношение (5) по-прежнему соблюдается.Если вершина р была удалена из множества Vp, то, повторив те же рассуждения, которые применялись при анализе блока \р, можно убедиться в том, чтоинвариант по-прежнему сохраняется.□Теорема 8.7. Алгоритм Шави— Франчеза (алгоритм 8.4) является корректным алгоритмом обнаружения завершения вычисления; в нем используется М + W обменов контрольными сообщениями.Д о к а з а т е л ь с т в о .
Как при доказательстве теоремы 8.5, можно показать, что число сигналов не превосходит числа базовых сообщений. Кроме сигналов контрольный алгоритм отправляет только сообщения для одной волны.Значит, всего будет отправлено не более М + W контрольных сообщений.Чтобы обосновать необходимое условие корректности алгоритма, предположим, что базовое вычисление завершилось. Спустя конечное число шагов рассматриваемый алгоритм обнаружения завершения вычисления достигает заключительной конфигурации, и точно так же, как в теореме 8.5, можно показать, чтов этой конфигурации граф F пуст. Следовательно, в распространении волны может участвовать каждый процесс.
И коль скоро была достигнута заключительнаяконфигурация, все события, присущие этой волне, осуществились, включая хотябы одно событие решения, которое было обязано вызвать процедуру Announce.Чтобы обосновать достаточное условие корректности алгоритма, напомним,что процедура Announce вызывается только тогда, когда в волновом алгоритмепринимается решение.
Это означает, что каждый процесс р уже отправил сооб-8.3. Решения на основе волновых алгоритмов299щение по волне или принял решение. А рассматриваемый нами алгоритм устроентак, что процесс р совершает это только тогда, когда emptyр имеет значениеtrue. Никакое действие не может вновь придать переменной emptyр значениеfalse, и поэтому, когда вызывается процедура Announce , для каждого процесса р переменная emptyp имеет значение true. Тогда согласно соотношению (6 )множество Vp пусто, и отсюда следует, что предикат term выполнен.□Число обменов контрольными сообщениями в алгоритме Шави—Франчеза —это величина такого же порядка, что и нижняя оценка, установленная в теоремах 8.2 и 8.3.
Этот алгоритм является оптимальным по сложности в наихудшем случае алгоритмом обнаружения завершения децентрализованных вычислений (при условии, что он снабжен оптимальным волновым алгоритмом).Для применения всех алгоритмов, рассмотренных в этом параграфе, требуется, чтобы каналы связи были двунаправленными; для каждого сообщения,отправленного от р к q, должен быть отправлен сигнал от q к р. Сложностьв среднем будет такой же, как и сложность в наихудшем случае: для каждоговыполнения алгоритма на одно базовое сообщение приходится одно сигнальноесообщение, а в случае алгоритма Шави—Франчеза, еще и проход ровно однойволны.8.3. Решения на основе волновых алгоритмовЕсть две причины, по которым полезно рассмотреть некоторые другие алгоритмы обнаружения завершения вычисления, помимо тех двух алгоритмов, которые были приведены в §8.5.2. Во-первых, рассмотренные ранее алгоритмыможно применять только в том случае, когда каналы являются двунаправленными.
А во-вторых, хотя эти алгоритмы имеют оптимальную сложность по числу сообщений в наихудшем случае, существуют алгоритмы, имеющие лучшуюсложность в среднем. Все алгоритмы из предыдущего параграфа используют прикаждом выполнении такое же число сообщений, что и в наихудшем случае.В этом параграфе мы изучим некоторые алгоритмы, в основу которых положен принцип многократного выполнения волнового алгоритма; в конце каждойволны либо обнаруживается завершение вычисления, либо запускается новаяволна. Завершение вычисления обнаруживается, если в каждом процессе будутвыполнено некоторое локальное условие.Начнем с того, что рассмотрим конкретные примеры таких алгоритмов, в которых в качестве волнового алгоритма выступает кольцевой алгоритм. Предполагается, что топология нашей сети допускает выделение некоторого кольца; однакообмен базовыми сообщениями не ограничивается каналами, входящими в составкольца.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
