Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Часть 2 Фундаментальные алгоритмы 9 глава

Обычно более легкое разрабатывать алгоритм, который заканчивается неявно чем алгоритм, который заканчивается явно. Действительно, в время разработки алгоритма все аспекты надлежащего завершения процессов могут игнорироваться; пр разработке концентрируются на ограничении полного числа событий, которые могут произойти. С другой стороны, применение алгоритма может потребовать, чтобы процессы закончились явно. Только после явного завершения результаты вычисления могут быть расцененным как заключительные, и переменные используемые в вычислении освобождены. Тупик распределенного алгоритма также приводит конечной конфигурации; в этом случае после достижения конечной конфигурации вычисление должно быть начато снова.

В основных методах этой главы будет исследовано для преобразование заканчивающихся неявно в явно заканчивающиеся. Зная такой метод, алгоритм можно разрабатывать беря во внимание только завершение сообщений (то есть, гарантируя только то, что алгоритм закончит вычисления), после чего алгоритм преобразуется в алгоритм завершения процессов с помощью использования одного из предложенных методов. Методы состоят из двух дополнительных алгоритмов, которые взаимодействуют с данным алгоритмом завершения сообщений и друг с другом. Один из этих алгоритмов наблюдает за вычислением и некоторым образом обнаруживает, что вычисление основного алгоритма достигло конечной конфигурации. После обнаружения такого завершения он вызывает второй алгоритм, который отправляет сообщения завершения всем процессам, заставляя их войти в конечное состояние.

Наиболее трудной частью преобразования оказывается алгоритм, обнаруживающий завершение. Процедура отправки сообщений завершения довольно тривиальна и будет обсуждена кратко в Подразделе 8.1.3. В этой главе будет показано, что обнаружение завершения возможно для всех классов сетей, для которых можно получить волновой алгоритм. Эти классы включают сети, где лидер доступен, сети, где процессы имеют идкентификаторы, древовидные сети, и сети, в которых доступна топологическая информация, типа диаметра или количества процессов. С другой стороны, в Главе 9 будет показано, что для анонимных сетей неизвестного размера существует неявно заканчивающийся алгоритм, но нет явно заканчивающегося алгоритма для вычисления максимума по входам процессов. Следовательно, обнаружение завершения невозможно в анонимных сетях где неизвестен размер.

Для тех случаев, в которых возможно обнаружение завершения, мы установим нижении границы числа сообщений, используемых алгоритмом обнаружения завершения. Будет показано, что существуют алгоритмы, которые удовлетворяют этим границам. Раздел 8.1 представляет проблему формально, предлагая модель поведения распределенного вычисления и представляя низшую границу и процедуру посылки сообщений завершения. Раздел 8.2 представляет несколько решений, основанные на использовании дерева (или леса) процессов, включающего по крайней мере все процессы, которые все еще производят вычисление. Решения в этом разделе не слишком сложны и удовлетворяют низшей границе Разделе 8.1. Эти первые два раздела содержат все фундаментальные результаты касающиеся существования и сложности алгоритмов обнаружения завершения. По различным причинам один алгоритм обнаружения завершения может быть более подходящий для конкретного применения чем другой алгоритм. Поэтому, Разделы 8.3 и 8.4 представляют некоторые другие решения. 

 

8.1 Предварительные замечания

8.1.1 Определения

В этом подразделе будет определена модель распределенных вычислений для изучения проблемы завершения распределенных вычислений. Модель получена из модели в Главе 2, но все аспекты не имеющие отношения к проблеме завершения отброшены.

Множество состояний процесса p - Zp, разделено в два подмножества - активных и пассивных состояний. Состояние процесса p - Сp активно если в нем к процессу p применимо внутреннее событи или событие посылки, и пассивено в остальных случаях. В пассивном состоянии Сp применимо только событие приема или вообще нет применимого события, т.е. Сp - конечное состояние процессо p. Процесс p будем называть активным, если он находится в активном состоянии и пассивным в противном случае. Очевидно, что сообщение может быть послано только активным процессом, и пассивный процесс может стать активным только, после получения сообщения. Активный процесс может стать пассивным, если он войдет в пассивное состояние. Сделаем некоторые из предположения для упрощения описания алгоритмов в этой главе.

(1) Активный процесс становится пассивным только после внутреннего события. Любой процесс можно достаточно просто модифицировать, для того чтобы он удовлетворял этому предположению. Пусть (c, m, d) событие посылки (или получения) процесса p, где d - пассивное состояние. Заменим это событие процесса p на (c, m, d'), где d' является новым состоянием, и единственным событием, применимым в d' является внутреннее ссобытие (d', d). Так как d' является активным состоянием, p становится пассивным после внутреннего события (d', d).

(2) Процесс всегда становится активным после получения сообщения. Любой процесс можно достаточно просто модифицировать, для того чтобы он удовлетворял этому предположению. Пусть (c, m, d) событие получения процесса  p, где d - пассивное состоянием. Заменим это событие на (c, m, d'), где d' является новым состоянием, и единственным событием, применимым в d' является внутреннее событие (d', d). Так как d' является активным состоянием, p становится активным после события получения и пассивным в его следующем событии (d', d).

(3 ) Внутреннее событие, после которого p становится пассивным является единственным внутренним событием процесса p. Внутренние события, после которых p переходит из одного активного состояния в другое активное состояние игнорируются, потому что алгоритм обнаружения завершения должен быть забывающий; использовать информацию о том, как будет происходить локальное вычисление процесса не представляется возможным. Все активные состояния поэтому одинаковы для алгоритма обнаружения завершения.

Из состояния процесса p нас интересует только активное оно или пассивное; эта информация будет представлена переменной statep. Все переходы вычисления представлены в алгоритме 8.1

 

var statep: (active, passim);

S p: { statep = active }

begin send (mes) end

R p: { A message (mes) has arrived at p }

begin receive (mes); statep:= active end

I p: { statep = active }

begin statep:= passive end

Алгоритм 8.1 ОСНОВНОЙ распределенный алгоритм.

 

Как обычно, предполагается, что в начальной конфигурации нет сообщений, которые находились бы в процессе передачи. Первоначально процессы могут быть активны или пассивны.

Чтобы отличить этот алгоритм от алгоритма обнаружения завершения, его часто называют основным алгоритмом, и вычисление тогда называется основным вычислением. Алгоритм обнаружения завершения также называют управляющим или добавочным алгоритмом, и его вычисление называют управляющими или добавочными вычислениями. Аналогично, сообщения называются основные или управляющими.

Предикат term определен так, что принимает значение истина в каждой конфигурации, в которой не применимо никакое событие основного вычисления; согласно следующей теореме, в этом случае все процессы пассивны и ни одно основное сообщение не находится в процессе передачи.

 

Теорема 8.1

term <==> ("p ÎP: statep = passive)

              Ù("pq Î E: M pq не содержит сообщений (mes) ).

Доказательство. Если все процессы пассивны, внутренние события и события посылки не применимы. Если, кроме того, ни один канал не содержит сообщение (mes), то ни одно событие получения не применимо, следовательно ни один основной случай не применим вообще.

Если некоторый процесс активен, событие посылки или внутреннее событие возможно в том процессе, и если некоторый канал содержит сообщение (mes), событие получения этого сообщения применимо. o                                                      

В конечной конфигурации основного алгоритма каждый процесс ожидает получения сообщения и остается ожидающим навсегда. Проблема, обсуждаемая в этой главе - какой управляющий алгоритм нужно добавить в систему, чтобы перевести процессы в конечное состояние после того, как основное вычисление достигло конечной конфигурации. Для объединенного алгоритма (основного алглоритма вместе с управляющим алгоритмом) конфигурация, удовлетворяющая предикату term не обязательно является конечной: в общем случае могут иметься применимые события для управляющегоалгоритма. В управляющем алгоритме происходит обмен сообщениями, они могут быть посланы пассивными процессами и не переводить пассивный процесс в активное состояние после получения сообщения.

Управляющий алгоритм состоит из алгоритма обнаружения завершения и алгоритма объявления завершения. Алгоритм обнаружения завершения вызывает алгоритм объявления, и этот алгоритм переводит процессы в конечное состояние. Алгоритм обнаружения должен удовлетворять следующим трем требованиям.

(1) Невмешательство. Он не должен влиять на вычисление основного алгоритма.

(2) Живучесть. Если предикат term истинен, алгоритм объявления должен быть вызван за конечное число шагов.

(3) Безопасность. Если алгоритм объявления вызыван, конфигурация должна удовлетворить предикату term.

Проблема обнаружения завершения была впервые сформулирована Francez [Fra80]. Francez предложил решение, которое не удовлетворяет приципу невмешательства; сначала вычисление основного алгоритма "замораживалось" блокировкой всех событий, затем проверялось является ли конфигурация конечной. При положительном ответе вызывался алгоритм объявления; в противном случае, основное вычисление "размораживалось", и процедура повторялась спустя некоторое время. Вышеупомянутые требования не выполняются при таком решении проблемы.Они требуют, чтобы алгоритм обнаружения работал "непрерывно", то есть, во время работы основного вычисления. В доказательствах правильности обнаружения завершения в этой главе не дается объяснений по поводу выполнения требования невмешательства, потому что из самого описания алгоритма обычно вполне ясно, что это требование удовлетворено.

Основное вычисление называется централизованным если в каждом начальном состоянии имеется точно один активный процесс и децентрализованным, если число активных процессов в начальной конфигурации произволено. Централизованные основные вычисления часто называют в литературе по обнаружения завершения диффузийными вычислениями. Управляющие вычисление называют централизованными, если имеется один специальный процесс для управления вычислением, и децентрализованными, если процессы все выполняют один и тот же управляющий алгоритм.

 

8.1.2 Две нижних границы

Сложность алгоритма обнаружения завершения выражается как и ранее параметрами N и ú E ú и числом сообщений М, используемых основным вычислением. Сложность обнаружения завершения также связана со сложностью алгоритма волны; обозначим сложность по сообщениям лучшего алгоритма волны W. W конечно зависит от характеристик класса сетей, которые мы рассматриваем, например, характеристики типа, является ли лидер доступным, топологии, и начального знания процессов.

Будет показана сложность обнаружения завершения в наихудшем случае. Как для централизованных, так и для децентрализованных вычислений, она ограничена снизувеличиной М. Затем будет показано, что сложность обнаружения завершения для децентрализованных основных вычислений ограничена снизу величиной W. В конце этого подраздела будет обсуждена ниняя граница по сообщениям ú E ú, выведенная Chandrasekaran и Venkatesan [CV90],.

Теорема 8.2 Для каждого алгоритма обнаружения завершения существует основное вычисление, которое использует М основных сообщений и для которого алгоритм обнаружения использует по крайне мере М управляющих сообщений.

Доказательство. Если система может достигнуть конфигурации, в которой управляющий алгоритм может обмениваться бесконечным числом управляющих сообщений без наступления основного события, результат следует тривиально. Поэтому предположим, что далее при доказательстве управляющий алгоритм реагирует на каждое основное событие конечным числом сообщений.

Пусть g конфигурация в который два процесса, p и q, активные и нет сообщений, находящихся в процессе передачи. Если основной алгоритм централизован, такая конфигурация может быть достигнута из начальной конфигурации, обменом одного основного сообщения; в остальных случаях, такие конфигурации включены как начальные.

Сначала рассмотрите вычисление где, начиная с конфигурации g, оба процесса станут одновременно пассивными, то есть, система достигнет d = Ip(Iq (g)). Завершение должно быть обнаружено за конечное число шагов; но ни p ни q не могут вызвать алгоритм объявления не получа сначала сообщение от другого процесса. Иначе, завершение могло бы быть обнаружено ошибочно в конфигурации, где некоторый другой процесс все еще активен. (Если завершение обнаружено третьим процессом, необходимы по крайней мере два сообщения.) Следовательно, по крайней мере одно управляющее сообщение должно быть использовано в конфигурации d прежде, чем завершение может быть обнаружено.

Без потери общности, предположите, что p пошлет управляющее сообщение в конфигурации d. Рассмотрим вычисление, в котором, начинающийся с конфигурации g, только p становится пассивным, то есть, система достигает конфигурации gp= I p (g). Состояние p одинаково конфигурациях g p и d, и следовательно, p также посылает управляющее сообщение в конфигурации gp. Управляющий алгоритм может продолжать свою работу, но это не приведет к обнаружению завершения, т.к. q все еще активен. После того, как управляющий алгоритм прекратит обмен сообщениями, q посылает основное сообщение p, чтобы возвратиться конфигурацию, где p и q активены. Управляющий алгоритм может продолжать свою работу, но после конечного числа шагов будет снова достигнута конфигурация, в котором p и q являются активными и нет сообщений, которые находятся в процессе передачи. Подведем итог,

(1) Конфигурация, в которой p и q являются активными и нет сообщений, которые находятся в процессе передачи, может быть достигнута из начальной конфигурации передачей по крайней мере одного основного сообщения;

(2) Основной алгоритм может переходить из одной такой конфигурации в другую, передачей одного сообщения и вынуждая управляющий алгоритм передать по крайней мере одно управляющее сообщение;

(3) Если основное вычисление заканчивается после такой конфигурации, по крайней мере одно управляющее сообщение должно быть передано для обнаружения завершения.

Теорема таким образом доказана. o                                  

Теорема 8.3 Обнаружение завершение децентрализованного основного вычисления требует в худшем случае передачи по крайней мере W управляющих сообщений.

Доказательство. Рассмотрим основное вычисление, в котором не происходи обмен сообщениями и где каждый активный процесс становится пассивным после его первого события. Это основное вычисление требует, чтобы алгоритм обнаружения был волновым алгоритмом, если обнаружение (вызов алгоритма объявления) расценить как принятие решения. Действительно, вызов алгоритма объявления должен произойти за конечное число шагов, что доказывает, что алгоритм обнаружения сам заканчивается и принимает решение. Если решению не предшествует событие в некотором процессе q, рассматривается другое основное вычисление, где q не станет пассивным. Решение каузально не зависит не от какого события в q, так что алгоритм обнаружения может ошибочно вызвать алгоритм объявления, в то время как q все еще активен. Поскольку алгоритм обнаружения является волновым алгоритмом, он использует по крайней мере W сообщений. o

Начало алгоритма обнаружения. Chandrasekaran и Venkate-Сан [CV90] получили нижнюю границу управляющих сообщений ôE ô полагаясь два следующих дополнительных предположения.

Cl. Каналы - fifo.

C2. Алгоритм обнаружения завершения может начинать выполнение в любое время после того, как началось основное вычисление, то есть, в произвольной конфигурации основного вычисления.

Согласно этим предположениям неправильное обнаружение может произойти, если алгоритм обнаружения не пошлет управляющее сообщение через одно специальное ребро, скажем pq. Только перед началом алгоритма обнаружения, основное вычисление посылает одно дополнительное сообщение через канал pq.

 

var SentStopp: boolean init false;

RecStop p: integer init 0;

 

Procedure Announce;

  begin if not SentStop p then

           begin SentStopp:= true;

                     forall q Î Out p do send (stop) to q

          end

  end

 

{ Сообщение (stop) пришло в p }

  begin receive (stop); RecStop p:= RecStop p + 1;

            Announce;

            if RecStopp = #Inp then halt

  end

 

Алгоритм 8.2 алгоритм объявления.

 

 

Это сообщение не замечается управляющим алгоритмом, из которого выводится неверное обнаружение. Алгоритм Chandrasekaran и Venkatesan посылает управляющее сообщение через каждый канал, таким образом отправка всех сообщений происходит до начала работы управляющего алгоритма и получение сообщений происходит до обнаружения.

Можно показать,используя аргументы подобные тем, что использовались в [CV90], что проблема не имеет решение вообще, если предположение C2 действует, а предположение C1 - нет. В этой главе мы предполагаем, что управляющий алгоритм начинает работу в начальной конфигурации основного вычисления, то есть основное вычисление не исполняет никакое незамеченное событие до начала работы управляющего алгоритма. Если это предположение заменить на предположением C2, проблема имеет решение, тогда и только тогда, когда каналы - fifo, и решение найдено в [CV90] для этого случая.

 

8.1.3 Завершение Процессов

Чтобы объявить о завершение всем процессам, им посылается сообщение (stop). Каждый процесс посылает такое сообщение всем соседям, но делает это не более одного раза при локальном вызове алгоритма объявления или при получении сообщения (stop).При получении сообщения (stop) от каждого соседа, процесс выполняет оператор  stop, переводя процесс конечное состояние. Процедура объявления представлена Алгоритмом 8.2.

Алгоритм 8.2 может использоваться для произвольной связной топологии, включая направленные сети, и не требует ни лидера, ни идентификаторов, ни знания топологии вообще.

Деревья Вычислений и Леса

Решения, описанные в этом разделе основаны на динамическом поддержании направленных графов, называемых графом вычисления, узлы которого включают все активные процессы и все основные сообщения, находящиеся впроцессе пердачи. Завершение считается обнаруженным, если граф вычисления становится пустым. Решения этого раздела требуют, чтобы сеть была ненаправлена, то есть, сообщения могут передаваться в двух направлениях через каждый канал. Подраздел 8.2.1 описывает решение для централизованного основным вычисления, для которого граф вычисления является деревом с инициатором в качестве корня. Подраздел 8.2.2 обобщает это решение для децентрализованных основных вычислений и использует лес, в котором каждый инициатор основного вычисления является корнем дерева.

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...