Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 77

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 77)

Предпосылка Р является инвариантом алгоритма Дейкстры— Шолтена.Доказательство.Первоначально для всех процессов р, отличных отРо, выполняется равенство statep = passive, и при этом верно, что fatherPo фф udef; отсюда следует соотношение (1). Кроме того, Ер — 0 , и отсюда следуетсоотношение (2).

Соотношение (3) выполняется, поскольку scp = 0 для каждогопроцесса р. Так как Vp = {ро} и Ер = 0 , граф Т является деревом с корнем ро,и это подтверждает соотношение (4). В множестве Vp есть только один процесс/?о, и он является активным.Sр. При выполнении блока Sp никакой процесс не становится активным, ниодин процесс не удаляется из множества Vp, и поэтому соотношение (1) сохра­няет свою справедливость.Применимость действий этого блока означает, что родительская вершина рвновь появившейся вершины (mes, р) принадлежит множеству Vp, и это дока­зывает, что соотношение (2) соблюдается.В результате выполнения указанного действия к множеству Vp добавляетсяновая вершина (mes, р), а к множеству Ер — новая дуга ((mes, р), р). Это озна­чает, что граф Т будет по-прежнему оставаться деревом, а значение переменнойscp правильным образом увеличилось на единицу в соответствии с появлениему вершины р новой вершины-последователя. Таким образом, соотношения (3)и (4) сохраняются.Ни один из процессов не становится пассивной листовой вершиной в дереве Т,и ни один из процессов не заносится в множество Vp; поэтому соотношение (5)сохраняет свою справедливость.Rp.

Процесс р либо уже содержался в множестве Vp (в случае fatherр фф udef), либо был занесен в Vp в результате выполнения рассматриваемого дей­ствия. Поэтому соотношение (1) сохраняется.Если переменная fatherp изменяет значение, то ее новым значением будет q,а если сигнал послан процессом р, то его родительской вершиной также являетсяпроцесс q, и поскольку q содержится в Vp, соотношение (2) сохраняется.У процесса q число вершин-последователей не изменяется, ввиду того что по­следователь (mes, q) вершины q замещается либо вершиной-последователем р,либо вершиной-последователем (sig, q). А это означает, что значение scq оста­ется корректным и соотношение (3) по-прежнему выполняется.Структура графа не изменяется, и поэтому соотношение (4) сохраняется.8.2.

Деревья и леса вычислений293В любом случае после выполнения рассматриваемого действия процесс р ока­зывается принадлежащим множеству Vp, и, следовательно, соотношение (5) со­храняется.Iр. Если процесс р становится пассивным, то соотношения (1), (2), (3) и (4)сохраняются. То, что процесс р ранее был активным, означает, что он входилв состав множества Vp. Если scp = 0, то р удаляется из Vp и соотношение (5)будет также выполнено.Далее мы рассмотрим, что произойдет, когда процесс р будет удален из гра­фа Т, т.

е. когда процесс р станет пассивной листовой вершиной графа Т.Если сигнал был отправлен процессом р, то родительской вершиной для вер­шины сигнала в нашем графе является последняя родительская вершина для р.Эта вершина содержится в множестве Vp, и, следовательно, соотношение (2)сохраняется. В этом случае указанный сигнал занимает место процесса р в каче­стве последователя процесса fatherp. Поэтому значение scfatherp остается неиз­менным, и соотношение (3) сохраняет справедливость. Структура графа при этомне изменяется, и, значит, соотношение (4) также остается верным.В противном случае, т. е. когда имеет место равенство fatherр = р, выпол­няется условие р = ро, и, коль скоро р является листовой вершиной, процесс роставался единственной вершиной графа Т. Поэтому после удаления этой вер­шины граф Т становится пустым, и соотношение (4) сохраняет справедливость.Ар. Получение сигнала приводит к уменьшению на единицу числа вершинпоследователей процесса р.

Поскольку при этом выполняется соответствующийоператор присваивания, соотношение (3) сохраняет справедливость. То, что про­цесс р был родительской вершиной для вершины, соответствующей указанномусигналу, означает, что р принадлежит множеству Vp. Если выполнено условиеstatep = passive и после получения сигнала будет выполняться равенство scp == 0, то вершина р будет удалена.

Поэтому соотношение (5) остается верным.Если процесс р будет удален из множества Vp, то инвариант сохранится в силутех же самых соображений, которые были приведены, когда речь шла о дей­ствии Iр.□Теорема 8.5. Алгоритм Дейкстры—Шолтена (алгоритм 8.3) являет­ся корректным алгоритмом обнаружения завершения вычисления; в немиспользуется М обменов контрольными сообщениями.Д о к а з а т е л ь с т в о .

Обозначим символом S суммарное значение всехсчетчиков числа вершин-последователей, т. е. 5 =g]P scp- Первоначально Sравно нулю. Значение 5 увеличивается при отправлении базового сообщения,которое совершает действие Sp, и уменьшается, когда происходит прием кон­трольного сообщения (см. действие Ар). При этом S всегда остается неотрица­тельным числом (это следует из соотношения (3)). Значит, в каждом вычислениичисло контрольных сообщений не превосходит числа базовых сообщений.Чтобы обосновать необходимое условие корректности алгоритма, предполо­жим, что базовое вычисление уже завершилось.

После такого завершения вы­числения могут выполняться только действия Ар. А так как S уменьшается наединицу при совершении каждого такого перехода, алгоритм достигнет заклю-294Гл. 8. Обнаружение завершениячитальной конфигурации. Отметим, что в этой конфигурации в множестве Vротсутствуют сообщения.

Кроме того, согласно соотношению (5) в множестве Vpотсутствуют пассивные листовые вершины. Следовательно, дерево Т не имеетлистовых вершин, а это означает, что граф Т является пустым. Указанное деревостановится пустым, как только процесс ро удаляет из этого дерева самого се­бя, а программа устроена так, что на этом шаге процесс ро вызывает процедуруAnnounce.Чтобы обосновать достаточное условие корректности алгоритма, заметим, чтотолько процесс ро может вызвать процедуру Announce и это может быть сделанотолько тогда, когда ро удаляет самого себя из множества Vp.

Когда это происхо­дит, граф Т согласно соотношению (4) становится пустым. Отсюда следует, чтовыполняется предикат term .□В алгоритме Дейкстры—Шолтена достигнут замечательный баланс междуконтрольными и базовыми сообщениями; для каждого базового сообщения, от­правленного процессом р процессу q, рассмотренный алгоритм отправляет в точ­ности одно сообщение от процесса q к процессу р. Сложность по числу контроль­ных сообщений достигает нижней оценки, указанной в теореме 8 .2 , и поэтомуданный алгоритм является оптимальным по сложности в наихудшем случае ал­горитмом обнаружения завершения централизованных вычислений.При описании алгоритма, приведенном в этом параграфе, во всех сообще­ниях явно указывались их родительские вершины.

Однако обычно в этом нетнеобходимости, так как родительской вершиной базового (или контрольного) со­общения всегда является процесс-отправитель (соответственно процесс-адресат)этого сообщения.8.2.2. Алгоритм Шави—ФранчезаДля случая децентрализованных базовых вычислений алгоритм Дейкстры—Шол­тена был обобщен Шави и Франчезом в работе [175]. В предложенном ими алго­ритме граф вычислений является лесом, каждое дерево которого имеет в качествекорня один из инициаторов базового вычисления.

Для обозначения дерева, кор­нем которого служит процесс р, будем использовать запись Тр.В алгоритме Шави—Франчеза строится такой граф F = (Vp, Ер), что (1) ли­бо F пуст, либо F представляет собой лес, каждое дерево которого имеет одиниз инициаторов в качестве корня, и (2 ) множество Vp содержит все активныепроцессы и все базовые с о о б щ е н и я б.

Пак и в алгоритме Дейкстры—Шолтена,завершение базового вычисления будет обнаружено, когда указанный граф ста­новится пустым. К сожалению, если граф представляет собой лес, то совсем непросто убедиться в том, что этот граф стал пустым. И в самом деле, посколькукорнем дерева вычислений служит процесс ро, именно процесс ро может оценить,является ли дерево пустым, и вызвать в этом случае процедуру Announce. Ко­гда мы имеем дело с лесом, каждый инициатор может установить пустоту своего'^Пребывающие на этапе пересылки. — Прим, перев.8.2.

Деревья и леса вычислений295собственного дерева, но это еще не будет означать, что весь лес стал пустымграфом.Проверка того, что все деревья исчезли, проводится при помощи одной-единственнойволны. Упомянутый лес строится так, чтобы всякое дерево Тр, ставшее пустым,оставалось пустым и в дальнейшем. Отметим, что это не препятствует процессу рвновь становиться активным; однако если процесс р становится активным послеисчезновения его собственного дерева, то он заносится в дерево другого ини­циатора. Каждый процесс принимает участие в распространении волны толькотогда, когда его дерево исчезает; и если волна приводит к тому, что принимает­ся решение, то вызывается процедура оповещения Announce.

(Вызов процедурыAnnounce будет излишним, если волновой алгоритм устроен так, что решениепринимает каждый процесс; в таком случае процесс просто останавливается по­сле принятия решения, и этим завершается работа волнового алгоритма.)Все эти действия описаны в алгоритме 8.4; в приведенном описании волновойалгоритм в явном виде не выделен. Каждый процесс р располагает переменнойfatherp. Значение этой переменной полагается равным udef, если р £Ур.

Еслиже р является корнем дерева, то значением переменной fatherp является имяпроцесса р. И наконец, если р является некорневой вершиной дерева Т, то зна­чением переменной fatherp служит имя родительской вершины данного процесса.Переменная scp используется для подсчета числа последователей вершины р вдереве Т. Булева переменная emptyp принимает значение true тогда и толькотогда, когда дерево, в котором содержится вершина р, становится пустым.Доказательство корректности рассматриваемого алгоритма весьма сходно с до­казательством корректности алгоритма Дейкстры—Шолтена. Для всякой конфи­гурации у алгоритма 8.4 определим следующее множество вершин:Vp ={р\ fatherp ф udef} U {(mes, р) на этапе пересылки}U{(sig, р) на этапе пересылки}и дугЕр ={(р, fatherp): fatherp ф udef Л fatherp ф р}U {((mes, р), р): (mes, р) на этапе пересылки}U {((sig, р), р): (sig, р) на этапе пересылки}.Достаточные условия корректности (так называемое свойство безопасности ал­горитма) обеспечиваются предпосылкой Q, которая будет определена ниже.

Этапредпосылка является инвариантом алгоритма, и обоснование этого факта, ко­нечно, в точности следует схеме доказательства леммы 8.4. Смысл соотношений(1)—(5) предпосылки Q остается тем же самым, что и у инварианта алгоритмаДейкстры—Шолтена, а соотношение (6 ) выражает свойство корректной оценкипроцессом того, является ли он корнем одного из деревьев в рассматриваемом296Гл. 8. Обнаружение завершениялесе. Лес, несомненно, пуст, если ни один из процессов не является корнем:QАААААЛемма 8 .6 .statep = a c t i v e = £ - р Е Vp(u, v) e Ef => и Е Vp A v Е Vp OF)scp = #{o: ( , p) e Ef })Vp Ф 0 => F является лесом(,statep = p a s s i v e A scp = 0) ==>• p £ V Femptyp 4=^ Tp пустоv(1)(2)(3)(4)(5)(6)П редпосы лка Q являет ся инвариант ом алгорит м а Ш ави— Ф ран-чеза.Д о к а з а т е л ь с т в о .

Характеристики

Список файлов книги