Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 78
Текст из файла (страница 78)
А так как S уменьшается наединицу при совершении каждого такого перехода, алгоритм достигнет заклю-294Гл. 8. Обнаружение завершениячительной конфигурации. Отметим, что в этой конфигурации в множестве V Tотсутствуют сообщения. Кроме того, согласно соотношению (5) в множестве V Tотсутствуют пассивные листовые вершины. Следовательно, дерево T не имеетлистовых вершин, а это означает, что граф T является пустым. Указанное деревостановится пустым, как только процесс p0 удаляет из этого дерева самого себя, а программа устроена так, что на этом шаге процесс p 0 вызывает процедуруAnnounce.Чтобы обосновать достаточное условие корректности алгоритма, заметим, чтотолько процесс p0 может вызвать процедуру Announce и это может быть сделанотолько тогда, когда p0 удаляет самого себя из множества VT .
Когда это происходит, граф T согласно соотношению (4) становится пустым. Отсюда следует, чтовыполняется предикат term.В алгоритме Дейкстры—Шолтена достигнут замечательный баланс междуконтрольными и базовыми сообщениями; для каждого базового сообщения, отправленного процессом p процессу q, рассмотренный алгоритм отправляет в точности одно сообщение от процесса q к процессу p. Сложность по числу контрольных сообщений достигает нижней оценки, указанной в теореме 8.2, и поэтомуданный алгоритм является оптимальным по сложности в наихудшем случае алгоритмом обнаружения завершения централизованных вычислений.При описании алгоритма, приведенном в этом параграфе, во всех сообщениях явно указывались их родительские вершины. Однако обычно в этом нетнеобходимости, так как родительской вершиной базового (или контрольного) сообщения всегда является процесс-отправитель (соответственно процесс-адресат)этого сообщения.8.2.
Деревья и леса вычисленийсобственного дерева, но это еще не будет означать, что весь лес стал пустымграфом.Проверка того, что все деревья исчезли, проводится при помощи одной-единственнойволны. Упомянутый лес строится так, чтобы всякое дерево T p , ставшее пустым,оставалось пустым и в дальнейшем. Отметим, что это не препятствует процессу pвновь становиться активным; однако если процесс p становится активным послеисчезновения его собственного дерева, то он заносится в дерево другого инициатора. Каждый процесс принимает участие в распространении волны толькотогда, когда его дерево исчезает; и если волна приводит к тому, что принимается решение, то вызывается процедура оповещения Announce.
(Вызов процедурыAnnounce будет излишним, если волновой алгоритм устроен так, что решениепринимает каждый процесс; в таком случае процесс просто останавливается после принятия решения, и этим завершается работа волнового алгоритма.)Все эти действия описаны в алгоритме 8.4; в приведенном описании волновойалгоритм в явном виде не выделен.
Каждый процесс p располагает переменнойfatherp . Значение этой переменной полагается равным udef, если p 6 ∈V T . Еслиже p является корнем дерева, то значением переменной father p является имяпроцесса p. И наконец, если p является некорневой вершиной дерева T, то значением переменной fatherp служит имя родительской вершины данного процесса.Переменная scp используется для подсчета числа последователей вершины p вдереве T. Булева переменная emptyp принимает значение true тогда и толькотогда, когда дерево, в котором содержится вершина p, становится пустым.Доказательство корректности рассматриваемого алгоритма весьма сходно с доказательством корректности алгоритма Дейкстры —Шолтена.
Для всякой конфигурации алгоритма 8.4 определим следующее множество вершин:8.2.2. Алгоритм Шави—ФранчезаДля случая децентрализованных базовых вычислений алгоритм Дейкстры —Шолтена был обобщен Шави и Франчезом в работе [175] . В предложенном ими алгоритме граф вычислений является лесом, каждое дерево которого имеет в качествекорня один из инициаторов базового вычисления. Для обозначения дерева, корнем которого служит процесс p, будем использовать запись T p .В алгоритме Шави—Франчеза строится такой граф F = (VF , EF), что (1) либо F пуст, либо F представляет собой лес, каждое дерево которого имеет одиниз инициаторов в качестве корня, и (2) множество V F содержит все активныепроцессы и все базовые сообщения 1) .
Как и в алгоритме Дейкстры—Шолтена,завершение базового вычисления будет обнаружено, когда указанный граф становится пустым. К сожалению, если граф представляет собой лес, то совсем непросто убедиться в том, что этот граф стал пустым. И в самом деле, посколькукорнем дерева вычислений служит процесс p0 , именно процесс p0 может оценить,является ли дерево пустым, и вызвать в этом случае процедуру Announce. Когда мы имеем дело с лесом, каждый инициатор может установить пустоту своего1) Пребывающиена этапе пересылки. — Прим. перев.295VT = {p : fatherp 6= udef} ∪ {hmes, pi на этапе пересылки}∪{hsig, pi на этапе пересылки}и дугEF ={ (p, fatherp) : fatherp 6= udef ∧ fatherp 6= p}∪ { (hmes, pi, p) : hmes, pi на этапе пересылки}∪ { (hsig, pi, p) : hsig, pi на этапе пересылки}.Достаточные условия корректности (так называемое свойство безопасности алгоритма) обеспечиваются предпосылкой Q, которая будет определена ниже.
Этапредпосылка является инвариантом алгоритма, и обоснование этого факта, конечно, в точности следует схеме доказательства леммы 8.4. Смысл соотношений(1) – (5) предпосылки Q остается тем же самым, что и у инварианта алгоритмаДейкстры—Шолтена, а соотношение (6) выражает свойство корректной оценкипроцессом того, является ли он корнем одного из деревьев в рассматриваемом296Гл. 8. Обнаружение завершения8.2. Деревья и леса вычисленийлесе. Лес, несомненно, пуст, если ни один из процессов не является корнем:Q ⇐⇒∧∧∧∧∧statep = active =⇒ p ∈ VF(u, v) ∈ EF =⇒ u ∈ VF ∧ v ∈ VF ∩ P)scp = #{v : (v, p) ∈ EF })VF 6= ∅ =⇒ F является лесом(statep = passive ∧ scp = 0) =⇒ p 6 ∈ VFemptyp ⇐⇒ Tp пусто(1)(2)(3)(4)(5)(6)Лемма 8.6. Предпосылка Q является инвариантом алгоритма Шави—Франчеза.Д о к а з а т е л ь с т в о. Первоначально для каждого процесса p, не являющегося инициатором, справедливо равенство state p = passive, а для каждого инициатора p выполняется условие fatherp = p; отсюда следует соотношение (1).
Кроме того, EF = ∅, и отсюда следует соотношение (2). Поскольку scp = 0 для каждого процесса p, верно соотношение (3). Так как V F == {p : p является инициатором} и EF = ∅, граф F является лесом, образованным из деревьев, состоящих из одной-единственной вершины-инициатора; отсюда следует соотношение (4). Процессы из множества V F являются инициаторами,и эти процессы активны; значит, верно соотношение (5). Первоначально условие emptyp равносильно утверждению «p не является инициатором», и деревоTp действительно пусто в том и только том случае, когда процесс p не являетсяинициатором.
Это служит обоснованием соотношения (6).Sp . Ни один процесс не становится активным при выполнении блока S p , и ниодин процесс не удаляется из множества VF ; значит, соотношение (1) сохраняетсправедливость.Тот факт, что этот блок выполняется, означает, что процесс p, порождающийновую вершину, которая становится его последователем, принадлежит множествуVF , и поэтому соотношение (2) сохраняется.В результате выполнения рассматриваемого блока к множеству V F присоединяется вершина hmes, pi, а к множеству EF — дуга (hmes, pi, p). Следовательно,граф F по-прежнему остается лесом, а переменная scp , увеличивая свое значение, отмечает тем самым появление у вершины p нового последователя.
Значит,соотношения (3) и (4) также соблюдаются.Ни один процесс не становится пассивной листовой вершиной, и ни одинновый процесс не включается в VF ; поэтому соотношение (5) остается верным.Коль скоро к непустому дереву добавляется новая листовая вершина, никакоедерево не становится пустым, а так как никакая переменная empty не изменяетсвоего значения, справедливость соотношения (6) сохраняется.Rp . Процесс p либо уже содержался в множестве VF (в случае fatherp 6=6= udef), либо присоединяется к этому множеству в результате выполнения рассматриваемого блока. Значит, соотношение (1) остается справедливым.Если переменной fatherp присваивается новое значение, то им является имяпроцесса q, а если отправляется сигнал, то родительской вершиной для него ста-297новится все тот же процесс q, который содержится в V T .
Поэтому соотношение(2) сохраняется.Число последователей процесса q не изменяется, поскольку последовательhmes, qi вершины q замещается либо вершиной p, либо вершиной hsig, qi. А этозначит, что равенство (3) остается верным.Структура нашего графа не изменяется, и поэтому соотношение (4) такжесоблюдается.Ни один процесс не становится пассивной листовой вершиной, и ни одинновый процесс не включается в VF . Поэтому соотношение (5) остается верным.Ни одно дерево не исчезает, и никакое новое дерево не появляется. Значит,соотношение (6) сохраняется.var statep : (active, passive ) init if p is initiator then active else passive ;scp: integerinit 0 ;fatherp : Pinit if p is initiator then p else udef ;emptyp : boolinit if p is initiator then false else true ;Sp : { statep = active }begin send hmes, pi ; scp := scp + 1 endRp : {Сообщение hmes, qi поступило процессу p }begin receive hmes, qi ; statep := active ;if fatherp = udef then fatherp := q else send hsig, qi to qendIp : { statep = active }begin statep := passive ;if scp = 0 then (* Удалить p из F *)beginif fatherp = p then emptyp := true else send hsig, fatherp i to fatherp ;fatherp := udefendendAp : { Сигнал hsig, pi достигает p }begin receive hsig, pi ; scp := scp − 1 ;if scp = 0 and statep = passive thenbeginif fatherp = p then emptyp := true else send hsig, fatherp i to fatherp ;fatherp := udefendendВсе процессы проводят параллельное выполнение волнового алгоритма, причемотправление сообщений или принятие решения разрешается только тем процессам p,у которых переменная emptyp имеет значение true.При осуществлении события decide вызывается процедура Announce.Алгоритм 8.4.
Алгоритм Шави—ФранчезаIp . Если процесс p становится пассивным, то соотношения (1), (2), (3) и (4)остаются справедливыми. Тот факт, что процесс p ранее был активным, означает,298Гл. 8. Обнаружение завершениячто он принадлежал множеству VF . Если scp = 0, то процесс p будет удален изVF , и поэтому соотношение (5) остается верным.Посмотрим теперь, что произойдет, когда процесс p будет исключен из F,т. е. когда он станет пассивной листовой вершиной графа F.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
