Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 75
Текст из файла (страница 75)
Эти сообщения могут быть отправленыпассивными процессами, и получение контрольного сообщения не будет переводить пассивный процесс в разряд активных.Контрольный алгоритм состоит из алгоритма обнаружения завершения вычисления и алгоритма оповещения о завершении вычисления. Алгоритм обнаружения завершения вычисления вызывает алгоритм Announce , и этот алгоритм оповещения переводит все процессы в заключительные состояния.
Всякийрассматриваемый алгоритм обнаружения завершения вычисления должен удовлетворять следующим трем требованиям.1. Невмешательство. Алгоритм обнаружения завершения вычисления недолжен оказывать влияния на вычисления базового алгоритма.2. Живость. Если выполняется условие term , то алгоритм Announce долженбыть вызван спустя конечное число шагов.3. Безопасность. Если вызван алгоритм Announce , то конфигурация должнаудовлетворять условию term .Задача обнаружения завершения вычисления была впервые поставлена Франчезом в работе [87].
Франчез предложил решение, которое, однако, не удовлетворяло требованию невмешательства; его решение предусматривало первоначальное «замораживание» базового вычисления путем отмены всех событий, а затемпроведение анализа сложившейся конфигурации с целью определения того, является ли она заключительной. Если конфигурация оказывалась заключительной, то вызывался алгоритм Announce; в противном случае базовое вычисление«размораживалось» и описанная процедура повторялась некоторое время спустя. Перечисленные выше требования не допускают такого решения и заставляютвыявлять завершение вычисления «на лету», т. е.
по ходу работы базового алгоритма. В этой главе при проведении доказательства корректности алгоритмовобнаружения завершения мы не касаемся вопроса о невмешательстве, посколькуиз описания рассматриваемого алгоритма ясно видно, что это требование соблюдается.Базовое вычисление называется централизованным, если в каждом начальной конфигурации в точности один процесс является активным, и децентрализованным, если число активных процессов в начальной конфигурации может бытьпроизвольным. Централизованные базовые вычисления в работах, посвященнымзадаче обнаружения завершения, часто называют диффузными вычислениями.Контрольное вычисление называется централизованным, если для его выполнения выделен один специальный процесс, и децентрализованным, если все процессы выполняют один и тот же контрольный алгоритм.286Гл.
8. Обнаружение завершения8.1.2. Две нижние оценкиСложность алгоритмов обнаружения завершения вычисления выражается,как и прежде, посредством параметров N и |£|, а также числа М сообщений,которыми обмениваются процессы при выполнении базового вычисления. Сложность обнаружения завершения вычисления связана также с затратами на выполнение волнового алгоритма; мы обозначим символом W сложность по числуобменов сообщениями наилучшего волнового алгоритма.
Безусловно, величинаW зависит от таких характеристик рассматриваемого класса сетей, как топология сети, наличие процесса-лидера, а также от сведений, которыми изначальнорасполагают процессы.Мы покажем, что в наихудшем случае сложность задачи обнаружения завершения вычисления, как для централизованных так и для децентрализованныхалгоритмов ограничена снизу величиной М. Мы покажем также, что сложностьзадачи обнаружения завершения децентрализованных базовых вычислений ограничена снизу величиной W. Мы завершим этот параграф обсуждением нижнейоценки величины |£| по числу обменов сообщениями, установленную Чандрасекараном и Венкатесаном в работе [43].Теорема 8.2. Для всякого алгоритма обнаружения завершения вычисления существует такое базовое вычисление, осуществляющее М обменовбазовыми сообщениями, для обнаружения завершения которого рассматриваемый алгоритм совершает не менее М обменов контрольными сообщениями.Д о к а з а т е л ь с т в о .
Если наша система способна достичь такой конфигурации, начиная с которой в контрольном алгоритме может происходить обменбесконечно большим числом сообщений, и при этом не будет осуществляться ниодного базового события, то утверждение теоремы, очевидно, справедливо. Поэтому далее в доказательстве этой теоремы мы будем полагать, что контрольныйалгоритм откликается только конечным числом сообщений на каждое базовоесобытие.Рассмотрим конфигурацию у, в которой активны два процесса р и q и нетникаких сообщений, находящихся на этапе пересылки. Если базовый алгоритмявляется централизованным, то такая конфигурация может быть достигнута изначальной конфигурации посредством обмена одним базовым сообщением; в противном случае в число таких конфигураций входит и начальная конфигурация.Вначале рассмотрим такое вычисление, в котором, начиная с конфигурации у,оба процесса становятся пассивными после параллельного выполнения своихдействий, т.
е. система достигает конфигурации 8 = 1Д 1Ду)). Завершение вычисления должно быть обнаружено спустя конечное число шагов, но при этом ни р,ни q не могут вызвать процедуру Announce, не получив предварительно сообщения от своего напарника, ибо в противном случае произойдет ошибочное обнаружение завершения вычисления в конфигурации, в которой один из процессоввсе еще остается активным. А если завершение вычисления обнаруживает третий процесс, то для этого необходимы по меньшей мере два сообщения. Значит,8.1. Основные понятия287прежде чем завершение базового вычисления будет обнаружено, должен бытьсовершен обмен по крайней мере одним контрольным сообщением в конфигурации 8 .Не ограничивая общности, предположим, что в конфигурации 8 процесс ротправляет контрольное сообщение.
Рассмотрим вычисление, в котором, начиная с конфигурации у, пассивным становится только процесс р, т. е. системадостигает конфигурации ур = 1Ду). Состояние процесса р будет одним и темже в конфигурациях ур и 8 , и, следовательно, р также отправит контрольноесообщение в конфигурации j p. Контрольный алгоритм может проработать ещенекоторое время, однако завершения базового вычисления он не обнаружит, поскольку процесс q все еще остается активным. После того как контрольный алгоритм прекратит обмен сообщениями, процесс q отправит базовое сообщениепроцессу р, и, таким образом, мы вернемся к конфигурации, в которой оба процесса р и q будут активны. Контрольный алгоритм снова вступит в действие, нопосле конечного числа шагов вновь будет достигнута конфигурация, в которойоба процесса р и q будут активны и никакие сообщения не будут находиться наэтапе пересылки. Подводя итог сказанному, отметим следующее:1 ) конфигурация, в которой оба процесса р и q активны и нет сообщенийна этапе пересылки, может быть достигнута из начальной конфигурациипосле обмена не более чем одним базовым сообщением;2 ) базовый алгоритм может перейти из одной такой конфигурации в другую после обмена всего лишь одним сообщением, вынуждая контрольныйалгоритм совершить обмен по меньшей мере одним контрольным сообщением;3) если базовое вычисление после пребывания в такой конфигурации завершится, то для обнаружения этого понадобится совершить обмен по крайней мере одним контрольным сообщением.Из этих замечаний и следует утверждение теоремы.□Теорема 8.3.
Для обнаружения завершения децентрализованного базового вычисления в худшем случае требуется совершить обмен не менеечем W контрольными сообщениями.Д о к а з а т е л ь с т в о . Рассмотрим базовое вычисление, в котором вообще не происходит обмена сообщениями и каждый активный процесс становитсяпассивным после осуществления первого же события. Для обнаружения того, чтотакое базовое вычисление завершилось, требуется применить волновой алгоритм,если истолковывать обнаружение завершения вычисления (вызов процедуры Announce) как событие решения. И в самом деле, вызов процедуры Announce должен произойти спустя конечное число шагов, откуда следует, что сам алгоритмобнаружения завершится и примет решение. Если решению не будет предшествовать хоть одно событие в каком-либо процессе, то окажется возможным другоебазовое вычисление, в котором процесс q не станет пассивным.
Событие решения не будет связано причинно-следственной зависимостью ни с одним событиемв процессе q, а это означает, что алгоритм обнаружения завершения вычисления может ошибочно вызвать процедуру Announce в то время, когда процесс q288Гл. 8. Обнаружение завершенияеще остается активным. И поскольку алгоритм обнаружения завершения вычисления оказывается волновым, ему потребуется совершить не менее W обменовсообщениями.□Запуск алгоритма обнаружения завершения вычисления. Чандрасекарани Венкатесан в работе [43] сумели установить нижнюю оценку числа обменовсообщениями, равную |£|, налагая следующие два дополнительных ограничения.С1. В каналах поддерживается очередность сообщений.С2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
