Реферат: Распределенные алгоритмы
В этом подразделе будет определена модель распределенных вычислений для изучения проблемы завершения распределенных вычислений. Модель получена из модели в Главе 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) ;
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],.
Страницы: 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, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
