Наиболее трудной частью преобразования оказывается алгоритм, обнаруживающий завершение. Процедура отправки сообщений завершения довольно тривиальна и будет обсуждена кратко в Подразделе 8.1.3. В этой главе будет показано, что обнаружение завершения возможно для всех классов сетей, для которых можно получить волновой алгоритм. Эти классы включают сети, где лидер доступен, сети, где процессы имеют идкентификаторы, древовидные сети, и сети, в которых доступна топологическая информация, типа диаметра или количества процессов. С другой стороны, в Главе 9 будет показано, что для анонимных сетей неизвестного размера существует неявно заканчивающийся алгоритм, но нет явно заканчивающегося алгоритма для вычисления максимума по входам процессов. Следовательно, обнаружение завершения невозможно в анонимных сетях где неизвестен размер.
Для тех случаев, в которых возможно обнаружение завершения, мы установим нижении границы числа сообщений, используемых алгоритмом обнаружения завершения. Будет показано, что существуют алгоритмы, которые удовлетворяют этим границам. Раздел 8.1 представляет проблему формально, предлагая модель поведения распределенного вычисления и представляя низшую границу и процедуру посылки сообщений завершения. Раздел 8.2 представляет несколько решений, основанные на использовании дерева (или леса) процессов, включающего по крайней мере все процессы, которые все еще производят вычисление. Решения в этом разделе не слишком сложны и удовлетворяют низшей границе Разделе 8.1. Эти первые два раздела содержат все фундаментальные результаты касающиеся существования и сложности алгоритмов обнаружения завершения. По различным причинам один алгоритм обнаружения завершения может быть более подходящий для конкретного применения чем другой алгоритм. Поэтому, Разделы 8.3 и 8.4 представляют некоторые другие решения.
В этом подразделе будет определена модель распределенных вычислений для изучения проблемы завершения распределенных вычислений. Модель получена из модели в Главе 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) ;
Sp: { statep = active }
begin send (mes) end
Rp: { A message ( mes) has arrived at p }
begin receive ( mes ) ; statep := active end
Ip: { statep = active }
begin statep := passive end
Алгоритм 8.1 ОСНОВНОЙ распределенный алгоритм.
Как обычно, предполагается, что в начальной конфигурации нет сообщений, которые находились бы в процессе передачи. Первоначально процессы могут быть активны или пассивны.
Чтобы отличить этот алгоритм от алгоритма обнаружения завершения, его часто называют основным алгоритмом, и вычисление тогда называется основным вычислением. Алгоритм обнаружения завершения также называют управляющим или добавочным алгоритмом, и его вычисление называют управляющими или добавочными вычислениями. Аналогично, сообщения называются основные или управляющими.
Предикат term определен так, что принимает значение истина в каждой конфигурации, в которой не применимо никакое событие основного вычисления; согласно следующей теореме, в этом случае все процессы пассивны и ни одно основное сообщение не находится в процессе передачи.
Теорема 8.1
term <==> ("p ÎP : statep = passive)
Ù("pq Î E : Mpq не содержит сообщений (mes)).
Доказательство. Если все процессы пассивны, внутренние события и события посылки не применимы. Если, кроме того, ни один канал не содержит сообщение (mes), то ни одно событие получения не применимо, следовательно ни один основной случай не применим вообще.
Если некоторый процесс активен, событие посылки или внутреннее событие возможно в том процессе, и если некоторый канал содержит сообщение (mes), событие получения этого сообщения применимо. -
В конечной конфигурации основного алгоритма каждый процесс ожидает получения сообщения и остается ожидающим навсегда. Проблема, обсуждаемая в этой главе - какой управляющий алгоритм нужно добавить в систему, чтобы перевести процессы в конечное состояние после того, как основное вычисление достигло конечной конфигурации. Для объединенного алгоритма (основного алглоритма вместе с управляющим алгоритмом) конфигурация, удовлетворяющая предикату term не обязательно является конечной: в общем случае могут иметься применимые события для управляющегоалгоритма. В управляющем алгоритме происходит обмен сообщениями, они могут быть посланы пассивными процессами и не переводить пассивный процесс в активное состояние после получения сообщения.
Управляющий алгоритм состоит из алгоритма обнаружения завершения и алгоритма объявления завершения. Алгоритм обнаружения завершения вызывает алгоритм объявления, и этот алгоритм переводит процессы в конечное состояние. Алгоритм обнаружения должен удовлетворять следующим трем требованиям.
(1) Невмешательство.Он не должен влиять на вычисление основного алгоритма.
(2) Живучесть. Если предикат term истинен , алгоритм объявления должен быть вызван за конечное число шагов.
(3) Безопасность. Если алгоритм объявления вызыван, конфигурация должна удовлетворить предикату term.
Проблема обнаружения завершения была впервые сформулирована Francez [Fra80]. Francez предложил решение, которое не удовлетворяет приципу невмешательства; сначала вычисление основного алгоритма "замораживалось" блокировкой всех событий, затем проверялось является ли конфигурация конечной. При положительном ответе вызывался алгоритм объявления; в противном случае, основное вычисление "размораживалось", и процедура повторялась спустя некоторое время. Вышеупомянутые требования не выполняются при таком решении проблемы.Они требуют, чтобы алгоритм обнаружения работал "непрерывно", то есть, во время работы основного вычисления. В доказательствах правильности обнаружения завершения в этой главе не дается объяснений по поводу выполнения требования невмешательства, потому что из самого описания алгоритма обычно вполне ясно, что это требование удовлетворено.
Основное вычисление называется централизованным если в каждом начальном состоянии имеется точно один активный процесс и децентрализованным, если число активных процессов в начальной конфигурации произволено. Централизованные основные вычисления часто называют в литературе по обнаружения завершения диффузийными вычислениями. Управляющие вычисление называют централизованными, если имеется один специальный процесс для управления вычислением, и децентрализованными, если процессы все выполняют один и тот же управляющий алгоритм .
Сложность алгоритма обнаружения завершения выражается как и ранее параметрами N и ú Eú и числом сообщений М, используемых основным вычислением. Сложность обнаружения завершения также связана со сложностью алгоритма волны; обозначим сложность по сообщениям лучшего алгоритма волны W. W конечно зависит от характеристик класса сетей, которые мы рассматриваем , например, характеристики типа, является ли лидер доступным, топологии, и начального знания процессов.