Реферат: Распределенные алгоритмы
(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) ;
begin send (mes) end
Rp: { A message ( mes) has arrived at p }
begin receive ( mes ) ; statep := active end
begin statep := passive end
Алгоритм 8.1 ОСНОВНОЙ распределенный алгоритм.
Как обычно, предполагается, что в начальной конфигурации нет сообщений, которые находились бы в процессе передачи. Первоначально процессы могут быть активны или пассивны.
Чтобы отличить этот алгоритм от алгоритма обнаружения завершения, его часто называют основным алгоритмом, и вычисление тогда называется основным вычислением. Алгоритм обнаружения завершения также называют управляющим или добавочным алгоритмом, и его вычисление называют управляющими или добавочными вычислениями. Аналогично, сообщения называются основные или управляющими.
Предикат term определен так, что принимает значение истина в каждой конфигурации, в которой не применимо никакое событие основного вычисления; согласно следующей теореме, в этом случае все процессы пассивны и ни одно основное сообщение не находится в процессе передачи.
Теорема 8.1
term <==> ("p ÎP : statep = passive)
Ù("pq Î E : Mpq не содержит сообщений (mes)).
Доказательство. Если все процессы пассивны, внутренние события и события посылки не применимы. Если, кроме того, ни один канал не содержит сообщение (mes), то ни одно событие получения не применимо, следовательно ни один основной случай не применим вообще.
Если некоторый процесс активен, событие посылки или внутреннее событие возможно в том процессе, и если некоторый канал содержит сообщение (mes), событие получения этого сообщения применимо. o
В конечной конфигурации основного алгоритма каждый процесс ожидает получения сообщения и остается ожидающим навсегда. Проблема, обсуждаемая в этой главе - какой управляющий алгоритм нужно добавить в систему, чтобы перевести процессы в конечное состояние после того, как основное вычисление достигло конечной конфигурации. Для объединенного алгоритма (основного алглоритма вместе с управляющим алгоритмом) конфигурация, удовлетворяющая предикату term не обязательно является конечной: в общем случае могут иметься применимые события для управляющегоалгоритма. В управляющем алгоритме происходит обмен сообщениями, они могут быть посланы пассивными процессами и не переводить пассивный процесс в активное состояние после получения сообщения.
Управляющий алгоритм состоит из алгоритма обнаружения завершения и алгоритма объявления завершения. Алгоритм обнаружения завершения вызывает алгоритм объявления, и этот алгоритм переводит процессы в конечное состояние. Алгоритм обнаружения должен удовлетворять следующим трем требованиям.
(1) Невмешательство.Он не должен влиять на вычисление основного алгоритма.
(2) Живучесть. Если предикат term истинен , алгоритм объявления должен быть вызван за конечное число шагов.
(3) Безопасность. Если алгоритм объявления вызыван, конфигурация должна удовлетворить предикату term.
Проблема обнаружения завершения была впервые сформулирована Francez [Fra80]. Francez предложил решение, которое не удовлетворяет приципу невмешательства; сначала вычисление основного алгоритма "замораживалось" блокировкой всех событий, затем проверялось является ли конфигурация конечной. При положительном ответе вызывался алгоритм объявления; в противном случае, основное вычисление "размораживалось", и процедура повторялась спустя некоторое время. Вышеупомянутые требования не выполняются при таком решении проблемы.Они требуют, чтобы алгоритм обнаружения работал "непрерывно", то есть, во время работы основного вычисления. В доказательствах правильности обнаружения завершения в этой главе не дается объяснений по поводу выполнения требования невмешательства, потому что из самого описания алгоритма обычно вполне ясно, что это требование удовлетворено.
Основное вычисление называется централизованным если в каждом начальном состоянии имеется точно один активный процесс и децентрализованным, если число активных процессов в начальной конфигурации произволено. Централизованные основные вычисления часто называют в литературе по обнаружения завершения диффузийными вычислениями. Управляющие вычисление называют централизованными, если имеется один специальный процесс для управления вычислением, и децентрализованными, если процессы все выполняют один и тот же управляющий алгоритм .
Сложность алгоритма обнаружения завершения выражается как и ранее параметрами 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 одинаково конфигурациях gp и 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 ;
RecStopp : integer init 0;
Procedure Announce;
begin if not SentStopp then
forall q Î Outp do send ( stop ) to q
end
end
{ Сообщение ( stop ) пришло в p }
begin receive (stop) ; RecStopp := RecStopp + 1 ;
Announce ;
end
Алгоритм 8.2 алгоритм объявления.
Это сообщение не замечается управляющим алгоритмом, из которого выводится неверное обнаружение. Алгоритм Chandrasekaran и Venkatesan посылает управляющее сообщение через каждый канал, таким образом отправка всех сообщений происходит до начала работы управляющего алгоритма и получение сообщений происходит до обнаружения.
Можно показать,используя аргументы подобные тем, что использовались в [CV90], что проблема не имеет решение вообще, если предположение C2 действует, а предположение C1 - нет. В этой главе мы предполагаем, что управляющий алгоритм начинает работу в начальной конфигурации основного вычисления, то есть основное вычисление не исполняет никакое незамеченное событие до начала работы управляющего алгоритма. Если это предположение заменить на предположением C2, проблема имеет решение, тогда и только тогда, когда каналы - fifo, и решение найдено в [CV90] для этого случая.
Чтобы объявить о завершение всем процессам, им посылается сообщение ( stop ). Каждый процесс посылает такое сообщение всем соседям, но делает это не более одного раза при локальном вызове алгоритма объявления или при получении сообщения ( stop ).При получении сообщения ( stop ) от каждого соседа, процесс выполняет оператор stop , переводя процесс конечное состояние. Процедура объявления представлена Алгоритмом 8.2.
Алгоритм 8.2 может использоваться для произвольной связной топологии, включая направленные сети, и не требует ни лидера, ни идентификаторов, ни знания топологии вообще.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62
