Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 75
Текст из файла (страница 75)
В § 8.5.2 приводится несколько решений поставленнойзадачи, предполагающих использование дерева (или леса) процессов, включающего все процессы, в которых вычисление еще продолжается. Решения, приведенные в этом параграфе, не очень сложны и соответствуют нижним оценкам из§ 8.5.1. В этих двух параграфах представлены все основополагающие результаты,касающиеся существования и сложности алгоритмов обнаружения завершения.По ряду причин один алгоритм обнаружения завершения может оказаться длятех или иных приложений предпочтительнее другого. Поэтому в §§ 8.5.3 и 8.5.4представлен ряд других решений рассматриваемой задачи.8.1. Основные понятия8.1.1. ОпределенияВ этом параграфе мы введем в рассмотрение модель распределенных вычислений, опираясь на которую будем исследовать задачу завершения распределен-8.1.
Основные понятия283ных вычислений. В основу этой модели положена модель вычислений, введеннаяв гл. 2, однако, мы будем опускать все детали, не имеющие отношения к проблемеобнаружения завершения вычислений.Множество всех состояний Zp процесса p разбивается на два подмножестваактивных и пассивных состояний. Состояние cp процесса p считается активным, если процесс p в состоянии cp может выполнить внутреннее действие илиотправить сообщение; в противном случае это состояние считается пассивным.В пассивном состоянии cp возможен только прием сообщений, или в нем вообще не будет происходить никаких событий, и в этом случае c p будет относитьсяк заключительным состояниям процесса p.
Говорят, что процесс p активен, еслион пребывает в одном из активных состояний; в противном случае процесс pназывают пассивным. Ясно, что отправлять сообщения может только активныйпроцесс, а пассивный процесс может стать активным только после получениясообщения. Активный процесс может стать пассивным, если он перейдет в пассивное состояние. Чтобы облегчить описание алгоритмов в этой главе, сделаемряд упрощений.1. Активный процесс становится пассивным только после осуществления внутреннего события. Всякий процесс легко видоизменить так, чтобыон удовлетворял указанному требованию.
Рассмотрим такое событие (c, m, d)отправления (или получения) сообщения процессом p, в котором состояние dявляется пассивным. Заменим это событие в процессе p на (c, m, d 0), где d0 —новое состояние, в котором возможно только одно событие (d 0 , d), и это событие является внутренним. Так как состояние d0 активное, процесс p становитсяпассивным в результате осуществления внутреннего события (d 0 , d).2. Процесс всегда становится активным после получения сообщения.Всякий процесс легко видоизменить так, чтобы он удовлетворял указанному требованию.
Рассмотрим такое событие (c, m, d) получения сообщения процессомp, в котором состояние d является пассивным. Заменим в процессе p это событиена (c, m, d0), где d0 — новое состояние, в котором может произойти только однособытие (d0 , d), и это событие является внутренним. Так как состояние d 0 активное, процесс p становится активным после получения сообщения, а пассивнымв результате осуществления внутреннего события (d 0 , d).3.
Внутренние события, приводящие к тому, что процесс p становится пассивным, — это единственно возможные внутренние событияв процессе p. Внутренние события, переводящие процесс p из одного активногосостояния в другое активное состояние, игнорируются, поскольку алгоритм обнаружения завершения не должен заниматься выведыванием; ему не разрешаетсяиспользовать информацию о том, как организованы локальные вычисления процессов. Таким образом, для алгоритма обнаружения завершения все внутренниесостояния процессов неразличимы.Сведения о каком-либо состоянии p ограничиваются лишь знанием того, является это состояние активным или пассивным; эта информация представленазначением переменной statep .
Все переходы вычисления представлены на примере алгоритма 8.1. Как обычно, предполагается, что в начальной конфигурации284Гл. 8. Обнаружение завершенияникакое сообщение не находится на этапе пересылки. Первоначально процессымогут быть как активными, так и пассивными.var statep: (active, passive) ;Sp : { statep = active }begin send hmesi endRp : { Сообщение hmesi доставлено процессу p }begin receive hmesi ; statep := active endIp : { statep = active }begin statep := passive endАлгоритм 8.1.
Базовый распределенный алгоритмЧтобы отличать анализируемый алгоритм от алгоритма обнаружения завершения, мы будем называть его базовым алгоритмом, и вычисление базовогоалгоритма будем называть базовым вычислением или основным вычислением.Алгоритм обнаружения завершения будет носить название контрольного илинадзирающего алгоритма, а его вычисление будем называть контрольнымиили надзирающим вычислением. Подобным же образом сообщения будут подразделяться на базовые сообщения и контрольные сообщения.Будем полагать, что предикат term обращается в истину на всякой конфигурации, на которой не может произойти ни одного события в базовом вычислении;согласно приведенной ниже теореме это возможно только в том случае, когда всепроцессы пассивны и ни одно базовое сообщение не находится на этапе пересылки.Теорема 8.1.
Справедливо следующее соотношение:term ⇐⇒(∀p ∈ P : statep = passive)∧ (∀pq ∈ E : Mpq не содержит сообщения hmesi).Д о к а з а т е л ь с т в о. Если все процессы пассивны, никакое внутреннеесобытие или событие отправления сообщения невозможно. Если, кроме того, нипо одному из каналов не передается какое-либо сообщение hmesi, то ни одно событие приема сообщения также не может произойти. Значит, невозможно вообщеникакое базовое событие.Если какой-нибудь процесс активен, то в этом процессе может произойтивнутреннее событие или событие отправления сообщения, а если в одном из каналов содержится какое-либо сообщение hmesi, то может осуществиться приемэтого сообщения.В заключительной конфигурации базового алгоритма каждый процесс ожидает поступления сообщения и будет всегда пребывать в этом ожидании.
Задача,которую мы обсуждаем в этой главе, состоит в том, чтобы присоединить к нашей8.1. Основные понятия285системе контрольный алгоритм, который приведет все процессы в заключительные состояния, после того как базовое вычисление достигнет заключительнойконфигурации. Для составного алгоритма (образованного за счет присоединенияконтрольного алгоритма к базовому) конфигурация, удовлетворяющая предикату term, не обязательно является заключительной; в общем случае в ней могутпроизойти события контрольного алгоритма. В контрольном алгоритме происходит обмен (контрольными) сообщениями.
Эти сообщения могут быть отправленыпассивными процессами, и получение контрольного сообщения не будет переводить пассивный процесс в разряд активных.Контрольный алгоритм состоит из алгоритма обнаружения завершения вычисления и алгоритма оповещения о завершении вычисления.
Алгоритм обнаружения завершения вычисления вызывает алгоритм Announce, и этот алгоритм оповещения переводит все процессы в заключительные состояния. Всякийрассматриваемый алгоритм обнаружения завершения вычисления должен удовлетворять следующим трем требованиям.1. Невмешательство. Алгоритм обнаружения завершения вычисления недолжен оказывать влияния на вычисления базового алгоритма.2. Живость. Если выполняется условие term, то алгоритм Announce долженбыть вызван спустя конечное число шагов.3. Безопасность. Если вызван алгоритм Announce, то конфигурация должнаудовлетворять условию term.Задача обнаружения завершения вычисления была впервые поставлена Франчезом в работе [87] .
Франчез предложил решение, которое, однако, не удовлетворяло требованию невмешательства; его решение предусматривало первоначальное «замораживание» базового вычисления путем отмены всех событий, а затемпроведение анализа сложившейся конфигурации с целью определения того, является ли она заключительной. Если конфигурация оказывалась заключительной, то вызывался алгоритм Announce; в противном случае базовое вычисление«размораживалось» и описанная процедура повторялась некоторое время спустя.
Перечисленные выше требования не допускают такого решения и заставляютвыявлять завершение вычисления «на лету», т. е. по ходу работы базового алгоритма. В этой главе при проведении доказательства корректности алгоритмовобнаружения завершения мы не касаемся вопроса о невмешательстве, посколькуиз описания рассматриваемого алгоритма ясно видно, что это требование соблюдается.Базовое вычисление называется централизованным, если в каждом начальной конфигурации в точности один процесс является активным, и децентрализованным, если число активных процессов в начальной конфигурации может бытьпроизвольным. Централизованные базовые вычисления в работах, посвященнымзадаче обнаружения завершения, часто называют диффузными вычислениями.Контрольное вычисление называется централизованным, если для его выполнения выделен один специальный процесс, и децентрализованным, если все процессы выполняют один и тот же контрольный алгоритм.Гл. 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
