Будет показана сложность обнаружения завершения в наихудшем случае. Как для централизованных, так и для децентрализованных вычислений, она ограничена снизувеличиной М. Затем будет показано, что сложность обнаружения завершения для децентрализованных основных вычислений ограничена снизу величиной 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) Если основное вычисление заканчивается после такой конфигурации, по крайней мере одно управляющее сообщение должно быть передано для обнаружения завершения.
Теорема таким образом доказана. -
Теорема 8.3 Обнаружение завершение децентрализованного основного вычисления требует в худшем случае передачи по крайней мере W управляющих сообщений.
Доказательство. Рассмотрим основное вычисление, в котором не происходи обмен сообщениями и где каждый активный процесс становится пассивным после его первого события. Это основное вычисление требует, чтобы алгоритм обнаружения был волновым алгоритмом, если обнаружение (вызов алгоритма объявления) расценить как принятие решения. Действительно, вызов алгоритма объявления должен произойти за конечное число шагов, что доказывает, что алгоритм обнаружения сам заканчивается и принимает решение. Если решению не предшествует событие в некотором процессе q, рассматривается другое основное вычисление, где q не станет пассивным. Решение каузально не зависит не от какого события в q, так что алгоритм обнаружения может ошибочно вызвать алгоритм объявления, в то время как q все еще активен. Поскольку алгоритм обнаружения является волновым алгоритмом, он использует по крайней мере W сообщений. -
Начало алгоритма обнаружения. 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
begin SentStopp := true;
forall q Î Outp do send ( stop ) to q
end
end
{ Сообщение ( stop ) пришло в p }
begin receive (stop) ; RecStopp := RecStopp + 1 ;
Announce ;
if RecStopp = #Inp then halt
end
Алгоритм 8.2 алгоритм объявления.
Это сообщение не замечается управляющим алгоритмом, из которого выводится неверное обнаружение. Алгоритм Chandrasekaran и Venkatesan посылает управляющее сообщение через каждый канал, таким образом отправка всех сообщений происходит до начала работы управляющего алгоритма и получение сообщений происходит до обнаружения.
Можно показать,используя аргументы подобные тем, что использовались в [CV90], что проблема не имеет решение вообще, если предположение C2 действует, а предположение C1 - нет. В этой главе мы предполагаем, что управляющий алгоритм начинает работу в начальной конфигурации основного вычисления, то есть основное вычисление не исполняет никакое незамеченное событие до начала работы управляющего алгоритма. Если это предположение заменить на предположением C2, проблема имеет решение, тогда и только тогда, когда каналы - fifo, и решение найдено в [CV90] для этого случая.
Чтобы объявить о завершение всем процессам, им посылается сообщение ( stop ). Каждый процесс посылает такое сообщение всем соседям, но делает это не более одного раза при локальном вызове алгоритма объявления или при получении сообщения ( stop ).При получении сообщения ( stop ) от каждого соседа, процесс выполняет оператор stop , переводя процесс конечное состояние. Процедура объявления представлена Алгоритмом 8.2.
Алгоритм 8.2 может использоваться для произвольной связной топологии, включая направленные сети, и не требует ни лидера, ни идентификаторов, ни знания топологии вообще.
8.2 Деревья Вычислений и Леса
Решения, описанные в этом разделе основаны на динамическом поддержании направленных графов, называемых графом вычисления, узлы которого включают все активные процессы и все основные сообщения, находящиеся впроцессе пердачи. Завершение считается обнаруженным, если граф вычисления становится пустым. Решения этого раздела требуют, чтобы сеть была ненаправлена, то есть, сообщения могут передаваться в двух направлениях через каждый канал. Подраздел 8.2.1 описывает решение для централизованного основным вычисления, для которого граф вычисления является деревом с инициатором в качестве корня. Подраздел 8.2.2 обобщает это решение для децентрализованных основных вычислений и использует лес, в котором каждый инициатор основного вычисления является корнем дерева.
8.2.1 Dijkstra-Scholten Алгоритм
Алгоритм Dijkstra и Scholten [DS80] обнаруживает завершение централизованного основного вычисления (называемого диффузийным вычислением в [DS80]). Инициатор основного вычисления (называемого окружением в [DS80]), также играет специальную роль в алгоритме обнаружения и обозначается p0.
Алгоритм обнаружения динамически поддерживает дерево вычислений T = (VT, ET) со следующими двумя свойствами.
(1) T пусто или T - направленное дерево с корнем p0.
(2) Множество VT включает все активные процессы и все основные сообщения, находящиеся в процессе передачи.
Инициатор p0 вызывает алгоритм объявления когда p0 Ï VT согласно первому свойству, T пусто в этом случае, и согласно второму свойству, предикат term принимает значение истина .
Для сохранения свойств дерева вычислений во время выполнения основного вычисления, T должно расширятся при отправке основного сообщения или при переходе процесса, не принадлежащего дереву, в активное состояние. Когда p посылает основное сообщение (mes), (mes) вставляется в дерево, и отцом (mes) является p. Когда процесс p, не принадлежащий дереву, становится активным получая сообщения от q, q становится отцом p. Для того, чтобы представить отправителя сообщения явно, основное сообщение (mes) послаемой q будем обозначать (mes, q).