Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 76
Текст из файла (страница 76)
Обнаружение завершенияТеорема 8.2. Для всякого алгоритма обнаружения завершения вычисления существует такое базовое вычисление, осуществляющее M обменовбазовыми сообщениями, для обнаружения завершения которого рассматриваемый алгоритм совершает не менее M обменов контрольными сообщениями.Д о к а з а т е л ь с т в о. Если наша система способна достичь такой конфигурации, начиная с которой в контрольном алгоритме может происходить обменбесконечно большим числом сообщений, и при этом не будет осуществляться ниодного базового события, то утверждение теоремы, очевидно, справедливо. Поэтому далее в доказательстве этой теоремы мы будем полагать, что контрольныйалгоритм откликается только конечным числом сообщений на каждое базовоесобытие.Рассмотрим конфигурацию , в которой активны два процесса p и q и нетникаких сообщений, находящихся на этапе пересылки. Если базовый алгоритмявляется централизованным, то такая конфигурация может быть достигнута изначальной конфигурации посредством обмена одним базовым сообщением; в противном случае в число таких конфигураций входит и начальная конфигурация.Вначале рассмотрим такое вычисление, в котором, начиная с конфигурации ,оба процесса становятся пассивными после параллельного выполнения своихдействий, т.
е. система достигает конфигурации = I p (Iq ( )). Завершение вычисления должно быть обнаружено спустя конечное число шагов, но при этом ни p,ни q не могут вызвать процедуру Announce, не получив предварительно сообщения от своего напарника, ибо в противном случае произойдет ошибочное обнаружение завершения вычисления в конфигурации, в которой один из процессоввсе еще остается активным.
А если завершение вычисления обнаруживает третий процесс, то для этого необходимы по меньшей мере два сообщения. Значит,прежде чем завершение базового вычисления будет обнаружено, должен бытьсовершен обмен по крайней мере одним контрольным сообщением в конфигурации .Не ограничивая общности, предположим, что в конфигурации процесс pотправляет контрольное сообщение.
Рассмотрим вычисление, в котором, начиная с конфигурации , пассивным становится только процесс p, т. е. системадостигает конфигурации p = Ip ( ). Состояние процесса p будет одним и темже в конфигурациях p и , и, следовательно, p также отправит контрольноесообщение в конфигурации p . Контрольный алгоритм может проработать ещенекоторое время, однако завершения базового вычисления он не обнаружит, поскольку процесс q все еще остается активным. После того как контрольный алгоритм прекратит обмен сообщениями, процесс q отправит базовое сообщениепроцессу p, и, таким образом, мы вернемся к конфигурации, в которой оба процесса p и q будут активны.
Контрольный алгоритм снова вступит в действие, нопосле конечного числа шагов вновь будет достигнута конфигурация, в которойоба процесса p и q будут активны и никакие сообщения не будут находиться наэтапе пересылки. Подводя итог сказанному, отметим следующее:1) конфигурация, в которой оба процесса p и q активны и нет сообщенийна этапе пересылки, может быть достигнута из начальной конфигурациипосле обмена не более чем одним базовым сообщением;2) базовый алгоритм может перейти из одной такой конфигурации в другую после обмена всего лишь одним сообщением, вынуждая контрольныйалгоритм совершить обмен по меньшей мере одним контрольным сообщением;3) если базовое вычисление после пребывания в такой конфигурации завершится, то для обнаружения этого понадобится совершить обмен по крайней мере одним контрольным сообщением.Из этих замечаний и следует утверждение теоремы.Сложность алгоритмов обнаружения завершения вычисления выражается,как и прежде, посредством параметров N и |E|, а также числа M сообщений,которыми обмениваются процессы при выполнении базового вычисления.
Сложность обнаружения завершения вычисления связана также с затратами на выполнение волнового алгоритма; мы обозначим символом W сложность по числуобменов сообщениями наилучшего волнового алгоритма. Безусловно, величинаW зависит от таких характеристик рассматриваемого класса сетей, как топология сети, наличие процесса-лидера, а также от сведений, которыми изначальнорасполагают процессы.Мы покажем, что в наихудшем случае сложность задачи обнаружения завершения вычисления, как для централизованных так и для децентрализованныхалгоритмов ограничена снизу величиной M. Мы покажем также, что сложностьзадачи обнаружения завершения децентрализованных базовых вычислений ограничена снизу величиной W. Мы завершим этот параграф обсуждением нижнейоценки величины |E| по числу обменов сообщениями, установленную Чандрасекараном и Венкатесаном в работе [43] .2878.1.2. Две нижние оценки8.1.
Основные понятия286Теорема 8.3. Для обнаружения завершения децентрализованного базового вычисления в худшем случае требуется совершить обмен не менеечем W контрольными сообщениями.Д о к а з а т е л ь с т в о. Рассмотрим базовое вычисление, в котором вообще не происходит обмена сообщениями и каждый активный процесс становитсяпассивным после осуществления первого же события. Для обнаружения того, чтотакое базовое вычисление завершилось, требуется применить волновой алгоритм,если истолковывать обнаружение завершения вычисления (вызов процедуры Announce) как событие решения. И в самом деле, вызов процедуры Announce должен произойти спустя конечное число шагов, откуда следует, что сам алгоритмобнаружения завершится и примет решение. Если решению не будет предшествовать хоть одно событие в каком-либо процессе, то окажется возможным другоебазовое вычисление, в котором процесс q не станет пассивным.
Событие решения не будет связано причинно-следственной зависимостью ни с одним событиемв процессе q, а это означает, что алгоритм обнаружения завершения вычисления может ошибочно вызвать процедуру Announce в то время, когда процесс q288Гл. 8. Обнаружение завершенияеще остается активным. И поскольку алгоритм обнаружения завершения вычисления оказывается волновым, ему потребуется совершить не менее W обменовсообщениями.Запуск алгоритма обнаружения завершения вычисления. Чандрасекарани Венкатесан в работе [43] сумели установить нижнюю оценку числа обменовсообщениями, равную |E|, налагая следующие два дополнительных ограничения.C1. В каналах поддерживается очередность сообщений.C2.
Алгоритм обнаружения завершения вычисления может начать работу в любой момент, после того как было запущено базовое вычисление, т. е. начинаяс произвольной конфигурации базового вычисления.Если соблюдаются эти допущения, то алгоритм обнаружения завершения вычисления, не отправивший контрольного сообщения по некоторому особо выделенному ребру, например pq, будет вынужден принять неверное решение. Непосредственно перед запуском контрольного алгоритма базовое вычисление отправляет одно дополнительное сообщение по каналу pq. Это сообщение не будетзарегистрировано контрольным алгоритмом, в результате чего он придет к ошибочному выводу о завершении вычисления. Алгоритм Чандрасекарана и Венкатесана отправляет контрольные сообщения по каждому каналу, вследствие чеговсе сообщения, отправленные перед запуском контрольного алгоритма, будут доставлены по назначению еще до того, как будет принято решение о завершениивычисления.Проводя рассуждения, аналогичные тем, которые применялись в работе [43] ,можно показать, что задача вообще не имеет решения, если соблюдается допущение C2, а допущение C1 не имеет места.
В этой главе мы будем предполагать, чтоконтрольный алгоритм начинает работу в начальной конфигурации базового вычисления, т. е. в базовом вычислении до начала работы контрольного алгоритмане происходит ни одного незарегистрированного события. Если принять указанное предположение вместо допущения C2, то наша задача будет иметь решениетогда и только тогда, когда во всех каналах соблюдается очередность сообщений,и такое решение найдено в работе [43] .8.1.3. Как остановить процессыЧтобы оповестить о завершении вычисления все процессы, по сети широковещательно распространяется сообщение hstopi. Каждый процесс отправляеттакое сообщение всем своим соседям, но делает это не более одного раза, либосовершая локальный вызов процедуры Announce, либо после получения первогосообщения hstopi. Когда сообщение hstopi будет получено от всех соседей, процесс выполняет оператор stop и в результате этого переходит в заключительноесостояние.
Указанный метод оповещения представлен в алгоритме 8.2.Алгоритм 8.2 можно применять для связных сетей произвольной топологии,включая ориентированные сети; в нем не предусматривается наличия лидера, отличительных признаков и какой-либо осведомленности об особенностях топологии.8.2. Деревья и леса вычисленийvar SentStoppRecStopp289: boolinit false ;: integer init 0 ;Procedure Announce:begin if not SentStopp thenbegin SentStopp := true ;forall q ∈ Outp do send hstopi to qendend{Сообщение hstopi поступило процессу p}begin receive hstopi ; RecStopp := RecStopp + 1 ;Announce ;if RecStopp = #Inp then haltendАлгоритм 8.2. Алгоритм оповещения8.2. Деревья и леса вычисленийРешения задачи обнаружения завершения вычисления, описанные в этом параграфе, основаны на построении и динамическом обновлении ориентированногографа, который называется графом вычисления.
В число вершин этого графавходят все активные процессы и все базовые сообщения, находящиеся на этапепересылки. Завершение вычисления будет обнаружено, как только граф вычисления становится пустым. Все те решения задачи, которые приведены в настоящемпараграфе, требуют, чтобы сеть была неориентированной, т. е. чтобы сообщенияпо каждому каналу можно было отправлять в обе стороны. В § 8.2.1 описанорешение рассматриваемой задачи для централизованных базовых вычислений,в которых граф вычислений представляет собой дерево, корнем которого являетсяинициатор. В § 8.2.2 приведено обобщение этого решения для децентрализованных базовых вычислений с использованием леса, в котором каждый инициаторбазового вычисления является корнем одного из деревьев.8.2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
