Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 77
Текст из файла (страница 77)
Алгоритм Дейкстры—ШолтенаАлгоритм Дейкстры—Шолтена [65] обнаруживает завершение централизованного базового вычисления (такое вычисление в работе [65] называют диффузным вычислением). Инициатор базового вычисления (который в работе [65]называется окружением) играет также особую роль в алгоритме обнаружениязавершения вычисления; мы будем обозначать этот процесс символом p 0 .Алгоритм обнаружения завершения строит и постоянно обновляет дерево вычисления T = (VT , ET), которое обладает следующими двумя свойствами.1. Граф T либо является пустым, либо представляет собой ориентированноедерево, корнем которого является вершина p0 .290Гл. 8.
Обнаружение завершения2. Множество VT включает все активные процессы и все базовые сообщения,находящиеся на этапе пересылки.Инициатор p0 вызывает процедуру Announce, если p0 6 ∈VT ; согласно первомусвойству граф T в таком случае является пустым, а согласно второму свойствуэто означает, что вычисление завершилось.Чтобы указанные свойства дерева вычислений сохранялись по мере продвижения базового вычисления, граф T должен быть расширен в случае отправления базового сообщения или в том случае, когда процесс, не входящий в составдерева, становится активным.
Когда процесс p отправляет базовое сообщениеhmesi, это сообщение добавляется к дереву в качестве вершины hmesi, причем родительской вершиной для нее становится процесс p. Когда процесс p, невходящий в состав дерева, становится активным после получения сообщения отпроцесса q, вершина q становится родительской вершиной для процесса p.
Чтобы обозначить явно отправителя сообщения, всякое базовое сообщение hmesi,отправленное процессом q, будет обозначаться записью hmes, qi.var statepscpfatherp: (active, passive): integer:Pinit if p = p0 then active else passive ;init 0 ;init if p = p0 then p else udef ;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 из T *)begin if fatherp = pthen Announceelse send hsig, fatherp i to fatherp ;fatherp := udefendendAp : { Сигнал hsig, pi достигает p }begin receive hsig, pi ; scp := scp − 1 ;if scp = 0 and statep = passive thenbegin if fatherp = pthen Announceelse send hsig, fatherp i to fatherp ;fatherp := udefendendАлгоритм 8.3.
Алгоритм Дейкстры—Шолтена8.2. Деревья и леса вычислений291Удалять вершины из дерева T также необходимо, и на то есть две причины.Во-первых, базовое сообщение удаляется, как только оно будет получено. Вовторых, чтобы контрольный алгоритм сработал, дерево должно исчезнуть спустяконечное число шагов после завершения базового алгоритма. Сообщения являются листьями дерева T; в каждом процессе есть переменная, используемаядля подсчета числа вершин-последователей этого процесса в дереве T. Удалениеиз дерева вершины, являющейся последователем процесса p, осуществляетсясовсем в другом процессе q; это происходит в результате того, что вершинапоследователь либо соответствует сообщению, которое достигло процесса q, либосоответствует самому процессу q.
Чтобы в процессе p не нарушался учет вершинпоследователей, этому процессу может быть отправлено сигнальное сообщениеhsig, pi, когда удаляется вершина-последователь процесса p. Это сообщение замещает удаленную вершину-последователя процесса p, а удаление этой вершиныиз дерева осуществляется самим процессом p после получения указанного сигнала; при этом p уменьшает значение счетчика последователей на единицу.Все эти действия описаны в алгоритме 8.3. Каждый процесс p наделен переменной fatherp .
Значение этой переменной полагается равным udef, если p 6 ∈V T .Если же p является корнем дерева, то значением переменной father p являетсяимя процесса p. И наконец, если p является некорневой вершиной дерева T, тозначением переменной fatherp служит имя родительской вершины данного процесса. Переменная scp служит для подсчета числа последователей вершины pв дереве T.При обосновании корректности алгоритма мы покажем строго формально, чтоопределенный таким образом граф T является деревом и при этом становитсяпустым только в том случае, когда базовое вычисление завершилось. Для всякойконфигурации алгоритма 8.3 определим два множестваVT =и{p : fatherp 6= udef} ∪ {hmes, pi на этапе пересылки}∪ {hsig, pi на этапе пересылки}ET ={ (p, fatherp) : fatherp 6= udef ∧ fatherp 6= p}∪ { (hmes, pi, p) : hmes, pi на этапе пересылки}∪ { (hsig, pi, p) : hsig, pi на этапе пересылки}.Свойство безопасности нашего алгоритма обеспечивается предпосылкой P, которая определяется следующим образом:P≡statep = active =⇒ p ∈ VT∧ (u, v) ∈ ET =⇒ u ∈ VT ∧ v ∈ VT ∩ P∧ scp = #{v : (v, p) ∈ ET }∧ VT 6= ∅ =⇒ T — дерево с корнем p0∧ (statep = passive ∧ scp = 0) =⇒ p ∈6 VT .(1)(2)(3)(4)(5)Содержательный смысл этого инварианта таков.
Cогласно определению множество вершин графа T включает все сообщения (как базовые, так и контрольные),а также, согласно соотношению (1), все активные процессы. Соотношение (2)292Гл. 8. Обнаружение завершенияиграет вспомогательную роль; в нем утверждается, что T действительно являетсяграфом и все дуги направлены к процессам. Соотношение (3) гласит о том, чтоподсчет вершин-последователей проводится каждым процессом корректно, а всоотношении (4) утверждается, что T является деревом и процесс p 0 — это егокорень.
Соотношение (5) служит для того, чтобы показать, что это дерево действительно исчезает, если базовое вычисление завершится. Для доказательствакорректности нужно иметь в виду, что из предпосылки P следует, что равенствоfatherp = p соблюдается только тогда, когда p = p0 .Лемма 8.4. Предпосылка P является инвариантом алгоритма Дейкстры—Шолтена.Д о к а з а т е л ь с т в о. Первоначально для всех процессов p, отличных отp0 , выполняется равенство statep = passive, и при этом верно, что fatherp0 6=6= udef; отсюда следует соотношение (1). Кроме того, E T = ∅, и отсюда следуетсоотношение (2).
Соотношение (3) выполняется, поскольку sc p = 0 для каждогопроцесса p. Так как VT = {p0 } и ET = ∅, граф T является деревом с корнем p0 ,и это подтверждает соотношение (4). В множестве V T есть только один процессp0 , и он является активным.Sp . При выполнении блока Sp никакой процесс не становится активным, ниодин процесс не удаляется из множества VT , и поэтому соотношение (1) сохраняет свою справедливость.Применимость действий этого блока означает, что родительская вершина pвновь появившейся вершины hmes, pi принадлежит множеству V T , и это доказывает, что соотношение (2) соблюдается.В результате выполнения указанного действия к множеству V T добавляетсяновая вершина hmes, pi, а к множеству ET — новая дуга (hmes, pi, p). Это означает, что граф T будет по-прежнему оставаться деревом, а значение переменнойscp правильным образом увеличилось на единицу в соответствии с появлениему вершины p новой вершины-последователя. Таким образом, соотношения (3)и (4) сохраняются.Ни один из процессов не становится пассивной листовой вершиной в дереве T,и ни один из процессов не заносится в множество V T ; поэтому соотношение (5)сохраняет свою справедливость.Rp .
Процесс p либо уже содержался в множестве VT (в случае fatherp 6=6= udef), либо был занесен в VT в результате выполнения рассматриваемого действия. Поэтому соотношение (1) сохраняется.Если переменная fatherp изменяет значение, то ее новым значением будет q,а если сигнал послан процессом p, то его родительской вершиной также являетсяпроцесс q, и поскольку q содержится в VT , соотношение (2) сохраняется.У процесса q число вершин-последователей не изменяется, ввиду того что последователь hmes, qi вершины q замещается либо вершиной-последователем p,либо вершиной-последователем hsig, qi. А это означает, что значение sc q остается корректным и соотношение (3) по-прежнему выполняется.Структура графа не изменяется, и поэтому соотношение (4) сохраняется.8.2.
Деревья и леса вычислений293В любом случае после выполнения рассматриваемого действия процесс p оказывается принадлежащим множеству VT , и, следовательно, соотношение (5) сохраняется.Ip . Если процесс p становится пассивным, то соотношения (1), (2), (3) и (4)сохраняются. То, что процесс p ранее был активным, означает, что он входилв состав множества VT . Если scp = 0, то p удаляется из VT и соотношение (5)будет также выполнено.Далее мы рассмотрим, что произойдет, когда процесс p будет удален из графа T, т. е. когда процесс p станет пассивной листовой вершиной графа T.Если сигнал был отправлен процессом p, то родительской вершиной для вершины сигнала в нашем графе является последняя родительская вершина для p.Эта вершина содержится в множестве VT , и, следовательно, соотношение (2)сохраняется.
В этом случае указанный сигнал занимает место процесса p в качестве последователя процесса fatherp . Поэтому значение scfatherp остается неизменным, и соотношение (3) сохраняет справедливость. Структура графа при этомне изменяется, и, значит, соотношение (4) также остается верным.В противном случае, т. е. когда имеет место равенство father p = p, выполняется условие p = p0 , и, коль скоро p является листовой вершиной, процесс pоставался единственной вершиной графа T. Поэтому после удаления этой вершины граф T становится пустым, и соотношение (4) сохраняет справедливость.Ap .
Получение сигнала приводит к уменьшению на единицу числа вершинпоследователей процесса p. Поскольку при этом выполняется соответствующийоператор присваивания, соотношение (3) сохраняет справедливость. То, что процесс p был родительской вершиной для вершины, соответствующей указанномусигналу, означает, что p принадлежит множеству V T . Если выполнено условиеstatep = passive и после получения сигнала будет выполняться равенство sc p == 0, то вершина p будет удалена.
Поэтому соотношение (5) остается верным.Если процесс p будет удален из множества VT , то инвариант сохранится в силутех же самых соображений, которые были приведены, когда речь шла о действии Ip .Теорема 8.5. Алгоритм Дейкстры—Шолтена (алгоритм 8.3) является корректным алгоритмом обнаружения завершения вычисления; в немиспользуется M обменов контрольными сообщениями.Д о к а з а т е л ь с т в о. Обозначим символом SPсуммарное значение всехсчетчиков числа вершин-последователей, т.
е. S =p∈P scp . Первоначально Sравно нулю. Значение S увеличивается при отправлении базового сообщения,которое совершает действие Sp , и уменьшается, когда происходит прием контрольного сообщения (см. действие Ap). При этом S всегда остается неотрицательным числом (это следует из соотношения (3)). Значит, в каждом вычислениичисло контрольных сообщений не превосходит числа базовых сообщений.Чтобы обосновать необходимое условие корректности алгоритма, предположим, что базовое вычисление уже завершилось. После такого завершения вычисления могут выполняться только действия A p .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
