Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 74
Текст из файла (страница 74)
Явное завершение вычисления называют такжезавершением работы процессов, потому что работа процессов завершается,если алгоритм явно завершает работу.Обычно проще спроектировать алгоритм, завершающий вычисления неявно,чем алгоритм, работа которого завершается явно. Действительно, при проектировании алгоритма можно не обращать внимания на те детали, которые касаются завершения работы процессов; наше внимание сосредоточено на том, чтобыограничить общее число событий, которые могут произойти по ходу вычисления.С другой стороны, в приложениях алгоритма может потребоваться, чтобы процессы завершали работу явно.
Только после явного завершения работы можнобудет сбросить значения используемых переменных и рассматривать результаты вычисления как окончательные. Кроме того, к заключительной конфигурацииможет привести и блокировка распределенного алгоритма; в этом случае придостижении заключительной конфигурации вычисление должно быть перезапущено.В настоящей главе будут исследованы общие методы преобразования алгоритмов, в которых вычисления оканчиваются по завершении обмена сообщениями, в алгоритмы, в которых вычисления оканчиваются завершением работы процессов.
Располагая такими методами, можно проектировать алгоритм, принимаяв расчет лишь неявное завершение его вычислений (т. е. следя лишь за тем, чтобы282Гл. 8. Обнаружение завершениявсе вычисления нашего алгоритма были конечны), после чего, используя один изэтих методов, привести алгоритм к такому виду, в котором вычисления оканчиваются по завершении работы процессов. Указанные методы предусматриваютвведение двух дополнительных алгоритмов, которые взаимодействуют друг с другом, а также с заданным алгоритмом, имеющим неявное завершение вычислений.Один из этих алгоритмов анализирует текущее вычисление исходного алгоритмаи каким-либо образом обнаруживает, что это вычисление достигло заключительной конфигурации.
После этого вызывается второй алгоритм, который рассылаетсообщение о завершении вычисления всем процессам, призывая их перейти в заключительное состояние.Самой сложной частью такого преобразования оказывается алгоритм, обнаруживающий завершение вычисления. Процедура рассылки весьма проста, и мыобсудим ее в §8.1.3. В этой главе будет показано, что обнаружение завершениявозможно для всех классов сетей, для которых можно разработать волновой алгоритм.
Эти классы включают сети, допускающие избрание лидера, сети, процессы которых обладают отличительными признаками, древесные сети, а также сети,в которых процессам доступны сведения о таких топологических параметрах, какдиаметр сети или число процессов. С другой стороны, в гл. 9 будет показано,что для безымянных сетей, размер которых заранее неизвестен процессам, существует неявно завершающийся алгоритм вычисления максимума входных данныхвсех процессов, но нет явно завершающегося алгоритма решения указанной задачи. И это означает, что обнаружение завершения невозможно для безымянныхсетей, размер которых неизвестен.В тех случаях, когда обнаружение завершения возможно, мы установим нижние оценки для числа сообщений, которыми обмениваются процессы при работеалгоритма обнаружения завершения.
Будет показано также, что существуют алгоритмы, сложность которых соответствует указанным оценкам. В разд. 8.5.1 дается формальная постановка задачи на основе модели поведения распределенныхвычислений, устанавливаются нижние оценки и описывается процедура рассылкиоповещающих сообщений. В §8.5.2 приводится несколько решений поставленнойзадачи, предполагающих использование дерева (или леса) процессов, включающего все процессы, в которых вычисление еще продолжается.
Решения, приведенные в этом параграфе, не очень сложны и соответствуют нижним оценкам из§8.5.1. В этих двух параграфах представлены все основополагающие результаты,касающиеся существования и сложности алгоритмов обнаружения завершения.По ряду причин один алгоритм обнаружения завершения может оказаться длятех или иных приложений предпочтительнее другого. Поэтому в §§8.5.3 и 8.5.4представлен ряд других решений рассматриваемой задачи.8.1.
Основные понятия8.1.1. ОпределенияВ этом параграфе мы введем в рассмотрение модель распределенных вычислений, опираясь на которую будем исследовать задачу завершения распределен8.1. Основные понятия283ных вычислений. В основу этой модели положена модель вычислений, введеннаяв гл. 2 , однако, мы будем опускать все детали, не имеющие отношения к проблемеобнаружения завершения вычислений.Множество всех состояний Zp процесса р разбивается на два подмножестваактивных и пассивных состояний. Состояние ср процесса р считается активным, если процесс р в состоянии ср может выполнить внутреннее действие илиотправить сообщение; в противном случае это состояние считается пассивным.В пассивном состоянии ср возможен только прием сообщений, или в нем вообще не будет происходить никаких событий, и в этом случае ср будет относитьсяк заключительным состояниям процесса р.
Говорят, что процесс р активен, еслион пребывает в одном из активных состояний; в противном случае процесс рназывают пассивным. Ясно, что отправлять сообщения может только активныйпроцесс, а пассивный процесс может стать активным только после получениясообщения. Активный процесс может стать пассивным, если он перейдет в пассивное состояние.
Чтобы облегчить описание алгоритмов в этой главе, сделаемряд упрощений.1. Активный процесс становится пассивным только после осуществления внутреннего события. Всякий процесс легко видоизменить так, чтобыон удовлетворял указанному требованию. Рассмотрим такое событие (с, т, d )отправления (или получения) сообщения процессом р, в котором состояние dявляется пассивным. Заменим это событие в процессе р на (с, т, d'), где d! —новое состояние, в котором возможно только одно событие (d1, d), и это событие является внутренним. Так как состояние d' активное, процесс р становитсяпассивным в результате осуществления внутреннего события (d1, d).2. Процесс всегда становится активным после получения сообщения.Всякий процесс легко видоизменить так, чтобы он удовлетворял указанному требованию. Рассмотрим такое событие (с, т, d) получения сообщения процессомр, в котором состояние d является пассивным. Заменим в процессе р это событиена (с, т, d'), где d' — новое состояние, в котором может произойти только однособытие (d1, d), и это событие является внутренним.
Так как состояние d' активное, процесс р становится активным после получения сообщения, а пассивнымв результате осуществления внутреннего события (d1, d).3. Внутренние события, приводящие к тому, что процесс р становится пассивным, — это единственно возможные внутренние событияв процессе р. Внутренние события, переводящие процесс р из одного активногосостояния в другое активное состояние, игнорируются, поскольку алгоритм обна ружения завершения не должен заниматься выведыванием ; ему не разрешаетсяиспользовать информацию о том, как организованы локальные вычисления процессов.
Таким образом, для алгоритма обнаружения завершения все внутренниесостояния процессов неразличимы.Сведения о каком-либо состоянии р ограничиваются лишь знанием того, является это состояние активным или пассивным; эта информация представленазначением переменной statep. Все переходы вычисления представлены на примере алгоритма 8 .1. Как обычно, предполагается, что в начальной конфигурации284Гл.
8. Обнаружение завершенияникакое сообщение не находится на этапе пересылки. Первоначально процессымогут быть как активными, так и пассивными.var statep: (active, passive) ;Sp: { statep = active }begin send (mes) endRp: { Сообщение (mes) доставлено процессу p }begin receive (mes) ; statep := active endIp. { statep = active }begin statep := passive endАлгоритм 8.1. Базовый распределенный алгоритмЧтобы отличать анализируемый алгоритм от алгоритма обнаружения завершения, мы будем называть его базовым алгоритмом, и вычисление базовогоалгоритма будем называть базовым вычислением или основным вычислением.Алгоритм обнаружения завершения будет носить название контрольного илинадзирающего алгоритма, а его вычисление будем называть контрольнымиили надзирающим вычислением. Подобным же образом сообщения будут подразделяться на базовые сообщения и контрольные сообщения.Будем полагать, что предикат term обращается в истину на всякой конфигурации, на которой не может произойти ни одного события в базовом вычислении;согласно приведенной ниже теореме это возможно только в том случае, когда всепроцессы пассивны и ни одно базовое сообщение не находится на этапе пересылки.Теорема 8.1.
Справедливо следующее соотношение:term -<==>(V/7 € Р : statep = passive)A (\/pq € E: Mpq не содержит сообщения(mes)).Д о к а з а т е л ь с т в о . Если все процессы пассивны, никакое внутреннеесобытие или событие отправления сообщения невозможно. Если, кроме того, нипо одному из каналов не передается какое-либо сообщение (mes), то ни одно событие приема сообщения также не может произойти. Значит, невозможно вообщеникакое базовое событие.Если какой-нибудь процесс активен, то в этом процессе может произойтивнутреннее событие или событие отправления сообщения, а если в одном из каналов содержится какое-либо сообщение (mes), то может осуществиться приемэтого сообщения.□В заключительной конфигурации базового алгоритма каждый процесс ожидает поступления сообщения и будет всегда пребывать в этом ожидании.
Задача,которую мы обсуждаем в этой главе, состоит в том, чтобы присоединить к нашей8.1. Основные понятия285системе контрольный алгоритм, который приведет все процессы в заключительные состояния, после того как базовое вычисление достигнет заключительнойконфигурации. Для составного алгоритма (образованного за счет присоединенияконтрольного алгоритма к базовому) конфигурация, удовлетворяющая предикату term , не обязательно является заключительной; в общем случае в ней могутпроизойти события контрольного алгоритма. В контрольном алгоритме происходит обмен (контрольными) сообщениями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
