Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 76
Текст из файла (страница 76)
Алгоритм обнаружения завершения вычисления может начать работу в любой момент, после того как было запущено базовое вычисление, т. е. начинаяс произвольной конфигурации базового вычисления.Если соблюдаются эти допущения, то алгоритм обнаружения завершения вычисления, не отправивший контрольного сообщения по некоторому особо выделенному ребру, например pq, будет вынужден принять неверное решение. Непосредственно перед запуском контрольного алгоритма базовое вычисление отправляет одно дополнительное сообщение по каналу pq.
Это сообщение не будетзарегистрировано контрольным алгоритмом, в результате чего он придет к ошибочному выводу о завершении вычисления. Алгоритм Чандрасекарана и Венкатесана отправляет контрольные сообщения по каждому каналу, вследствие чеговсе сообщения, отправленные перед запуском контрольного алгоритма, будут доставлены по назначению еще до того, как будет принято решение о завершениивычисления.Проводя рассуждения, аналогичные тем, которые применялись в работе [43],можно показать, что задача вообще не имеет решения, если соблюдается допущение С2, а допущение С1 не имеет места. В этой главе мы будем предполагать, чтоконтрольный алгоритм начинает работу в начальной конфигурации базового вычисления, т.
е. в базовом вычислении до начала работы контрольного алгоритмане происходит ни одного незарегистрированного события. Если принять указанное предположение вместо допущения С2, то наша задача будет иметь решениетогда и только тогда, когда во всех каналах соблюдается очередность сообщений,и такое решение найдено в работе [43].8.1.3.
Как остановить процессыЧтобы оповестить о завершении вычисления все процессы, по сети широковещательно распространяется сообщение (stop). Каждый процесс отправляеттакое сообщение всем своим соседям, но делает это не более одного раза, либосовершая локальный вызов процедуры Announce , либо после получения первогосообщения (stop). Когда сообщение (stop) будет получено от всех соседей, процесс выполняет оператор stop и в результате этого переходит в заключительноесостояние. Указанный метод оповещения представлен в алгоритме 8.2.Алгоритм 8.2 можно применять для связных сетей произвольной топологии,включая ориентированные сети; в нем не предусматривается наличия лидера, отличительных признаков и какой-либо осведомленности об особенностях топологии.8.2.
Деревья и леса вычисленийvar SentStoppRecStopp289: boolinit false ;: integer init 0 ;Procedure Announce:begin if not SentStopp thenbegin SentStopp := true ;fоrail q € Outp do send (stop) to qendend{Сообщение (stop) поступило процессу p}begin receive (stop) ; RecStopp := RecStopp + 1 ;Announce ;if RecStopp=#!nP then haltendАлгоритм 8.2. Алгоритм оповещения8.2.
Деревья и леса вычисленийРешения задачи обнаружения завершения вычисления, описанные в этом параграфе, основаны на построении и динамическом обновлении ориентированногографа, который называется графом вычисления. В число вершин этого графавходят все активные процессы и все базовые сообщения, находящиеся на этапепересылки. Завершение вычисления будет обнаружено, как только граф вычисления становится пустым. Все те решения задачи, которые приведены в настоящемпараграфе, требуют, чтобы сеть была неориентированной, т. е.
чтобы сообщенияпо каждому каналу можно было отправлять в обе стороны. В §8.2.1 описанорешение рассматриваемой задачи для централизованных базовых вычислений,в которых граф вычислений представляет собой дерево, корнем которого являетсяинициатор. В §8.2.2 приведено обобщение этого решения для децентрализованных базовых вычислений с использованием леса, в котором каждый инициаторбазового вычисления является корнем одного из деревьев.8.2.1. Алгоритм Дейкстры—ШолтенаАлгоритм Дейкстры—Шолтена [65] обнаруживает завершение централизованного базового вычисления (такое вычисление в работе [65] называют диффузным вычислением).
Инициатор базового вычисления (который в работе [65]называется окружением) играет также особую роль в алгоритме обнаружениязавершения вычисления; мы будем обозначать этот процесс символом ро.Алгоритм обнаружения завершения строит и постоянно обновляет дерево вычисления Т = [Vj, Ej), которое обладает следующими двумя свойствами.1. Граф Т либо является пустым, либо представляет собой ориентированноедерево, корнем которого является вершина ро.Гл.
8. Обнаружение завершения2902. Множество Vj включает все активные процессы и все базовые сообщения,находящиеся на этапе пересылки.Инициатор ро вызывает процедуру Announce , если ро /eVp, согласно первомусвойству граф Т в таком случае является пустым, а согласно второму свойствуэто означает, что вычисление завершилось.Чтобы указанные свойства дерева вычислений сохранялись по мере продвижения базового вычисления, граф Т должен быть расширен в случае отправления базового сообщения или в том случае, когда процесс, не входящий в составдерева, становится активным.
Когда процесс р отправляет базовое сообщение(mes), это сообщение добавляется к дереву в качестве вершины (mes), причем родительской вершиной для нее становится процесс р. Когда процесс р, невходящий в состав дерева, становится активным после получения сообщения отпроцесса q, вершина q становится родительской вершиной для процесса р. Чтобы обозначить явно отправителя сообщения, всякое базовое сообщение (mes),отправленное процессом q, будет обозначаться записью (mes, q).var statepscpfatherp: (active , passive): integer:Pinit if p = po then active else passive ;init 0 ;init if p = po then p else udef ;Sp: { statep = active }begin send (mes, p) ; scp := scp + 1 endR^: {Сообщение (mes, q ) достигло процесса p }begin receive (mes, q ) ; statep := active ;if fatherp = udef then fatherp := q else send (sig, q) to qendlp: { statep = active }begin statep := passive ;if scp = 0 then(* Удалить p из T *)begin if fatherp = pthen Announceelse send (sig, fatherp) to fatherp ;fatherp := udefendendAp: { Сигнал (sig, p) достигает p }begin receive (sig, p) ; scp := scp — 1 ;if scp = 0 and statep = passive thenbegin if fatherp = pthen Announceelse send (sig, fatherp) to fatherp ;fatherp ■= udefendАлгоритм 8.3.
Алгоритм Дейкстры— Шолтена8.2. Деревья и леса вычислений291Удалять вершины из дерева Т также необходимо, и на то есть две причины.Во-первых, базовое сообщение удаляется, как только оно будет получено. Вовторых, чтобы контрольный алгоритм сработал, дерево должно исчезнуть спустяконечное число шагов после завершения базового алгоритма. Сообщения являются листьями дерева Т\ в каждом процессе есть переменная, используемаядля подсчета числа вершин-последователей этого процесса в дереве Т. Удалениеиз дерева вершины, являющейся последователем процесса р, осуществляетсясовсем в другом процессе q\ это происходит в результате того, что вершинапоследователь либо соответствует сообщению, которое достигло процесса q, либосоответствует самому процессу q.
Чтобы в процессе р не нарушался учет вершинпоследователей, этому процессу может быть отправлено сигнальное сообщение(sig, р), когда удаляется вершина-последователь процесса р. Это сообщение замещает удаленную вершину-последователя процесса р, а удаление этой вершиныиз дерева осуществляется самим процессом р после получения указанного сигнала; при этом р уменьшает значение счетчика последователей на единицу.Все эти действия описаны в алгоритме 8.3. Каждый процесс р наделен переменной fatherp. Значение этой переменной полагается равным udef, если р £УтЕсли же р является корнем дерева, то значением переменной fatherp являетсяимя процесса р.
И наконец, если р является некорневой вершиной дерева Т, тозначением переменной fatherр служит имя родительской вершины данного процесса. Переменная scp служит для подсчета числа последователей вершины рв дереве Т.При обосновании корректности алгоритма мы покажем строго формально, чтоопределенный таким образом граф Т является деревом и при этом становитсяпустым только в том случае, когда базовое вычисление завершилось.
Для всякойконфигурации у алгоритма 8.3 определим два множестваVj ={р : fatherp ф udef} U {(mes, р) на этапе пересылки}U {(sig, р) на этапе пересылки}Ет={(р, fatherp): fatherр ф udef A fatherр ф р}U {((mes, р), р): (mes, р) на этапе пересылки}U {((sig, р), р): (sig, р) на этапе пересылки}.Свойство безопасности нашего алгоритма обеспечивается предпосылкой Р, которая определяется следующим образом:Р=statep = active ==>• p e V jA (и, v) € Ет ==>• и € Vt A v € Vt П PA scp = ф{и: (u, p) e ET}(1)(2)(3)A Vt ф 0 => T — дерево с корнем poA (statep = passive A scp = 0) ==>• p£ Vt.(4)(5)Содержательный смысл этого инварианта таков. Согласно определению множество вершин графа Т включает все сообщения (как базовые, так и контрольные),а также, согласно соотношению (1), все активные процессы. Соотношение (2)292Гл.
8. Обнаружение завершенияиграет вспомогательную роль; в нем утверждается, что Т действительно являетсяграфом и все дуги направлены к процессам. Соотношение (3) гласит о том, чтоподсчет вершин-последователей проводится каждым процессом корректно, а всоотношении (4) утверждается, что Т является деревом и процесс р о — это егокорень. Соотношение (5) служит для того, чтобы показать, что это дерево действительно исчезает, если базовое вычисление завершится. Для доказательствакорректности нужно иметь в виду, что из предпосылки Р следует, что равенствоfatherp = р соблюдается только тогда, когда р = ро.Лемма 8.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
