 |
Часть 2 Фундаментальные алгоритмы 8 глава
|
|
|
|
Объединение фрагментов. После того как исходящее ребро с наименьшим весом фрагмента F = (name, level) было определено, сообщение á connect, level ñ посылается через это ребро, и получается узлом, принадлежащим к фрагменту F ' - = (name', level'). Назовем процесс, посылающий сообщение á connect, level ñ p и процесс, получающий его q. Узел q ранее послал сообщение á accept ñ к p в ответ на сообщение á test, level, name ñ, потому что поиск лучшего исходящегоребра во фрагменте p закончился. Ожидание, организованное перед ответом на сообщения test (см. (5)) дает level' £ level.
Согласно правилам объединения, обсужденным ранее, ответ á connect, level ñ на сообщение á initiate, L, F, S ñ имеет местов двух случаях.
Случай A: если level' > level, фрагмент p поглощается; узлам в этом фрагменте сообщается новое имя фрагмента и уровень с помощью сообщения á initiate, level', name', S ñ, которое отправляется всем узлам во фрагменте F. Полный поглощенный фрагмент F становится поддеревом q в дереве охватов фрагмента F ' и если q в настоящее время занят в поиске лучшего исходящего ребра фрагмента F', все процессы в F должны участвовать. Вот почему q включает состояние (find или found) в сообщение á initiate, level', name', S ñ.
Случай B: если два фрагмента имеют один и тот же уровень и лучшее исходящее ребро фрагмента F ' также pq, новый фрагмент формируется с уровнем наимбольшим из двух и именем - вес ребра pq: см. (2). Этот случай происходит, если два уровня равны, и сообщение connect получено через ребро branch: заметьте, что статус ребра становится branch, если сообщение connect послано через него.
Если ни один из этих двух случаев не происходит, фрагмент F должен ждать, пока q посылает сообщение á connect, Lñ, или уровень фрагмента q увеличился достаточно, чтобы делать Случай применимым.
|
|
|
Правильность и сложность. Из детального описания алгоритма должно быть ясно, что ребро через которое фрагмент посылает сообщение á connect, Lñ является действительно исходящим ребром фрагмента с наименьшим весом. Вместе с Суждением 7.19 это означает, что MST вычислен правильно, если каждый фрагмент действительно посылает такое сообщение и присоединяется к другому фрагменту, несмотря на ожидание, вызванного алгоритмом. Наиболее сложное сообщение содержит вес одного ребра, один уровень (до logN) и постоянное числа бит, чтобы указать тип сообщения и состояние узла.
Теорема 7.21 Gallager-Humblet-Spira алгоритм (7.11/7.12 7.10/ Алгоритма) вычисляет минимальное дерево охватов, используя не более 5 N log N + 2 ½E ½ сообщений.
Доказательство. Тупик потенциально возникает в ситуациях, где узлы или фрагменты должны ждать, пока некоторое условие не происходит в другом узле или фрагменте. Ожидание, вставляное для сообщения á report, wñ на основном ребре не ведет к тупику, потому что каждый основной узел в конечном счете получает сообщения от всех сыновей (если фрагмент в целом не ждет другой фрагмент), после чего сообщение будет обработано.
Рассмотрите случай когда сообщение фрагмента F1 = (level1, name1) достигает узла фрагмента F2 = (level2, name2). Сообщение (connect, level 1) должно ждать, если level1 ³ level2 и сообщение (connect, level2) не было послано через то же самое ребро фрагментом F2, см. (2). Сообщение(test, level1, narne1) должно ждать, если level1 > level2, см. (5). Во всех случаях, где F1 ждет F2, верно одно из следующих утверждений.
(1) level 1 > level2 ,
(2) level1 = level 2 Ù w (eF1) > w (eF2);
(3) level1 = level2 Ù w (eF1) = w (eF2) и F 2 все еще ищет исходящее ребро с наименьшим весом. (Т.к. eF1 - исходящее ребро F2, не возможно чтобы w (eF2) > w (eF1).)
Таким образом никакой тупиковый цикл не может возникнуть.
Каждое ребро отклоняется не более одного раза, и это требует двух сообщений, который ограничивает число сообщений reject и сообщений test как следствий отклонений к 2 ½E ½. На любом уровне, узел получает не более одного сообщения initiate и accept, и посылает не более одного сообщения report, и одно changeroot или connect сообщение, и одно test сообщение, не ведущее к отклонению. На нулевом уровнени одно сообщение accept не получается и не одно сообщение report или test не посылается. На высшем уровне каждый узел только посылает сообщение report и получает одно сообщение initiate. Общее количество сообщений поэтому ограничено 2 ½E ½ + 5N log N. o
|
|
|
7.3.5 Обсуждения и Варианты GHS Алгоритма
Gallager-Humblet-Spira алгоритм - один из наиболее сложных волновых алгоритмов, требует только локальное знание и имеет оптимальную сложность по сообщениям. Алгоритм может легко быть расширен так, чтобы он выбрал лидера, используя только на два больше сообщений. Алгоритм заканчивает в двух узлах, а именно основных узлах последнего фрагмента (охватывающего полную сеть). Вместо выполнения остановки, основные узлы обменивают их идентификаторами, и меньший из них становится лидером.
Было опубликовано множество разновидностей и родственных алгоритмов. GHS алгоритм может требовать время Ω (N2), если некоторые узлы начинают алгоритм очень поздно. Если используется дополнительная процедура пробуждения (требующая не более ½E ½ сообщений) сложность алгоритма по времени 5N log N; см. Упражнение 7.11. Awerbuch [Awe87] показал, что сложность алгоритма по времени может быть улучшена од 0 (N), при сохранение оптимального порядка сложности по сообщениям,то есть 0 (½E ½ + N log N).
Afek и другие [ALSY90] приспособили алгоритм, для вычисления леса охвата с благоприятными свойствами, а именно, что диаметр каждого дерева и количество деревьев - 0 (N1/2). Их алгоритм распределенно вычисляет кластеризацию сети как показано в Lemma 4.47 и дерево охвата и центр каждого кластера.
Читатель может спрасить, могут ли произвольные деревя охватов быть построены более эффективно чем минимальные деревя охватов, но Теорема 7.15 также дает низкую границу Ω (N logN + ½E ½) на построение произвольных деревьев охватов. Johansen и другие [JJN ^ 87] дают алгоритм для вычисления произвольного дерева охватов, который использует 3N log N + 2 ½E ½ +0(N) сообщений, таким образом улучшая GHS алгоритме на постоянный множитель, если сеть редка. Barllan и Zernik [BIZ89] представили алгоритм, который вычисляет случайные деревья охватов, где каждое возможное дерево охватов выбрано с равной вероятностью. Алгоритм - рандомизирован и использует ожидаемое число сообщений, которое находится в границах между 0 (NlogN + ½E ½)) и 0 (N3), в зависимости от топологии сети.
|
|
|
В то время как строительство произвольных и минимальных деревьев охватов имеет равную сложность в произвольных сетях, это не так в кликах. Korach, Moran и Zaks [KMZ85] показали, что строительство минимального дерева охватов в взвешенной клике требует обмена Ω (N2) сообщениями. Этот результат указывает, что знание топологии не помогает уменьшать сложность обнаружения MST ниже границы из Теоремы 7.15. Произвольное дерево охватов клики может быть построено в 0 (N log N) сообщения, как мы покажем в следующем разделе; см. также [KMZ84].
7.4 Алгоритм Korach-Kutten-Moran
Много результатов были получены для проблемы выбора, не только для случая кольцевых сетей и произвольных сетей, но также и для случая другой специализированной топологии, типа сетей клик, и т.д. В нескольких случаях лучшие известные алгоритмы имеют сложность по сообщениям 0(N log N) и в некоторых случаях этот результат достигает Ω (NlogN). Korach, Kutten, и Moran [KKM90] показали, что имеется тесная связь между сетеми выбора и обхода. Их главный результат - общее строительство эффективного алгоритма выбора для класса сетей, учитывая алгоритм обхода для этого класса. Они показывают, что когда строительство снабжено лучшим алгоритмом обхода, известным для класса сетей, результирующий алгоритм благоприятно сравним с лучшим алгоритмом выбора, известным для того класса в большинстве случаев. Дело обстоит не так для сложности по времени; Сложность времени алгоритма равняется сложности по сообщениям, и в некоторых случаях известны другие алгоритмы с той же самой сложностью по сообщениям и более низкой сложностью времени.
|
|
|
7.4.1 Модульное Строительство
Korach-Kutten-Moran алгоритм использует идеи преобразования вырождения (Подраздел 7.3.1) и идеи Peterson/Dolev-Klawe-Rodeh алгоритма (Подраздел 7.2.2). Подобно преобразованию вырождения инициаторы выбора начинают обход сети с маркера, помеченного их идентификатором. Если обход заканчивается (разрешается), инициатор обхода становится избранным; алгоритм подразумевает, что это случается для точно одного обхода. В этом подразделе алгоритм описан для случая, где каналы удовлетворяют fifo предположение, но, поддерживая немного больше информации в каждом маркере и в каждом процессе алгоритм, может быть приспособлен к не - fifo случай; см. [KKM90].
Чтобы иметь дело с ситуацией больше чем одного инициатора, алгоритм работает на уровнях, которые могут быть сравнены с раундами Peterson/Dolev-Klawe-Rodeh алгоритма. Если по крайней мере два обхода начаты, маркеры достигнут процесса, который уже был посещен другим маркером. Если эта ситуация возникает, обход прибывшего маркера будет прерван. Цель алгоритма теперь становится, чтобы свести вместе два маркера в одном процессе, где они будут убиты и новый обход будет начат. Сравните это с Peterson/Dolev и другими алгоритмами, где по крайней мере один из каждых двух идентификаторов проходит круг и продолжает проходить следующий. Понятие раундов заменено в Korach-Kutten-Moran алгоритме понятием уровней; два маркера вызовут новый обход только если они имеют один и тот же уровень, и вновь произведенный маркер имеет уровень на единицу больше. Если маркер встречается с маркером более высокого уровня, или достигает узла, уже посещенного маркером более высокого уровня, прибывающий маркер просто убит без того, чтобы влиять на маркер на более высоком уровне.
Алгоритм дается как Алгоритм 7.13. Чтобы свести вместе маркеры одного и того же уровня в одном процессе, каждый маркер может быть в одном из трех режимов: annexing, chasing, или waiting. Маркер представляется (q, l), где q - инициатор маркера и l - уровень. Переменная levp дает уровень процесса p, и переменная catp дает инициатора последнего маркера annexing, отправленного p (в настоящее время активный обход p). Переменная waitp - udef, если никакой маркер не ожидает в p, и его значение q, если маркер (q, levp) ожидает в p. Переменная lastp используется для маркеров в режиме chasing: она дает соседа, которому p отправил маркер annexing уровня levp, если маркер chasing не был послан сразу после этого; в этом случае lastp = udef. Алгоритм взаимодействует с алгоритмом обхода запросом к функции trav: эта функция возвращает соседа, которому маркер должен быть отправлен или decide, если обход заканчивается.
|
|
|
Маркер (q, l) вводится в режиме annexing и в этом режиме он начинает исполнять алгоритм обхода (в случае IV Алгоритма 7.13) пока не произойдет одна из следующих ситуаций.
(1) Алгоритм обхода заканчивается: q становится лидером в этом случае (см. Случай IV в Алгоритме 7.13).
(2) Маркер достигает узла p уровня levp > l: маркер убит в этом случае, (Этот случай неявен в Алгоритме 7.13; все условия в том алгоритме требуют l > levp или l = levp.)
(3) Маркер прибывает в узел, где ожидает маркер уровня l: два маркера убиты в этом случае, и новый обход начинается с того узла (см. Случай II в Алгоритме 7.13).
(4) Маркер достигает узла с уровнем l, который был наиболее недавно посещен маркером с идентификатором catp > q (см. Случай VI) или маркером chasing (см. Случай III): маркер ожидает в том узле.
(5) Маркер достигает узла уровня l, который был наиболее недавно посещен маркером annexing с идентификатором catp < q: маркер становится маркером chasing в этом случае и посылается через тот же самый канал что и предыдущий маркер (см. Случай V).
Маркер chasing (g, l) отправляется в каждом узле через канал, через который наиболее недавно переданный маркер был послан, пока одна из следующих ситуаций не происходит.
(1) Маркер прибывает в процесс уровня levp > l: маркер убит в этом случае.
(2) Маркер прибывает в процесс с маркером waiting уровня l: два маркера удалены, и новый обход начат этим процессом (см. Случай II).
(3) Маркер достигает процесса уровня l, где наиболее недавно передан маркер chasing: маркер становится waiting (см. Случай III).
Маркер waiting находится в процессе, пока одна из следующих ситуаций не происходит.
(1) Маркер более высокого уровня достигает того же самого процесса: маркер waiting убит (см. Случай 1).
(2) Маркер равного уровня прибывает: два маркера удалены, и обход более высокого уровня начат (см. Случай II).
В Алгоритме 7.13 переменные и информация маркеров, используемая алгоритмом обхода игнорируются. Заметьте, что если p получает маркер уровня выше чем levp, это маркер annexing, инициатор которого не p. Если обход заканчивается в p, p становится лидером и отправляет сообщение всем процессам, заставляя их закончиться.
Правильность и сложность. Для того чтобы продемонстрировать правильность Korach-Kutten-Moran алгоритма, покажем, что число маркеров, произведенных на каждом уровне уменьшается до одного, на некотором уровне чей инициатор будет избран.
Lemma 7.22 Если произведены k> 1 маркеров на уровне l, по крайней мере один и не более k/2 маркеров произведены на уровне l + 1.
var levp : integer init – 1;
catp , waitp : P init udef',
last p : Neighp init udef:
begin if p is initiator then
begin lev p:= levp + 1; lastp:= trav(p. levp);
catp:= p; send (annex, p, levp) to lastp
end;
while... (* Условие завершения, смотри текст *) do
begin receive token (q,l);
if token is annexing then t:= A else t:= C;
if l > levp then (* Case I *)
begin levp:= l; catp:= q;
waitp:= udef; lastp:= trav(q, l);
send (annex, q, l) to lastp
end
else if l == levp and waitp ¹udef then (* Случай II *)
begin waitp:= udef; levp:= levp + 1;
lastp:= trav(p, levp); catp:= p;
send (annex, p, levp) to lastp
end
else if l = levp and lastp = udef then (* Случай III *)
waitp:= q
else if l = l evp and t = A and q = catp then (* Случай IV *)
begin lastp:= trav(q, t);
if lastp = decide then p объявляет себя лидером
else send ( annex, q,l) to lastp
end
else if l = levp and ((t = A and q > catp) or t = C) then (* Cлучай V *)
begin send (chase, q, t) to lastp; lastp:= udef end
else if l = levp then (* Cлучай VI *)
waitp:= q
end
End
Алгоритм 7.13 korach-kutten-moran алгоритм.
Доказательство. Не более k/2 маркеров произведены на уровне l + 1, потому что, когда такой маркер произведен, два маркера уровня l убиты в то же самое время.
Предположим, что имеется уровень l такой, что k> l маркеров произведены на уровне l, но никаком маркер не произведен на уровне l + 1. Пусть q процесс с максимальным идентификатором, который производит маркер на уровне l.Маркер (q, l) не заканчивает обход, потому что он будет получен процессом p, который уже отправил другой маркер уровня l.Когда это случается впервые (q, l) становится chasing или, если p уже отправил маркер chasing, (q, l) становится waiting. В любом случае, уровне l есть маркеры chasing.
Пусть (r, l) маркер с минимальным идентификатором после, которого посылается маркер chasing. Маркер (r, l) сам не может быть chasing, потому что маркер chasing преследует только маркеры с меньшим идентификатором. Мы можем поэтому предполагать, что (r, 1) стал waiting, когда он впервые достиг процесса p¢, который уже отправил другой маркер уровня l.Пусть p " последний процесс на пути следования (r, l), который получил маркер annexing, после того как он отправил
(r, l), и маркер сменил режим на chasing r. Этот маркер chasing встретит (r, 1) в p ', или откажется от преследования, если маркер waiting был найден прежде, чем маркер достиг p '. В обоих случаях маркер на уровне l + 1 произведен, т.е. мы пришли к противоречию.
Теорема 7.23 Korach-Kutten-Moran алгоритм (Алгоритм 7.13) - алгоритм выбора.
Доказательство Предположим, что по крайней мере один процесс начинает алгоритм. Согдасно предыдущей лемме, число маркеров, произведенных на каждом уровня уменьшается, и будет иметься уровень, на котором точно один маркер, скажем (q, 1) произведен. Никакой маркер уровня l ' < l не заканчивает обход, следовательно ни один из этих маркеров не заставляет процесс стать избранным. Уникальный маркер на уровне l только сталкивается с процессами на уровнях меньше чем l, или с cat = q (если он достигает процесса, который уже посещал), и отправляется в обоих случаях. Следовательно обход этого маркера заканчивается, и q избран.
Функция f, как считается выпуклой если f (a) + f (b) £ f (+ b). Сложность алгоритма проанализирована здесь согласно предположению что f (x) - алгоритм обхода(см. Раздел 6.3), где f - выпуклая функция.
Теорема 7.24 если f (x) - используется алгоритмом обхода, где f выпуклая, KKM алгоритм выбора не более (1+log k)[f(N)+N] сообщений если он начинается k процессами.
Доказательство. Если алгоритм начат k процессами, не более 2- l маркеров произведены на уровне l, что означает, что самый высокий уровень - не более ëlogkû.
Каждый процесс посылает маркеры annexing не более одного идентификатора на каждом уровне. Если на некотором уровне l имеются маркеры с идентификаторами p1, …, pj и имеются процессы Ni, которые отправили маркер annexing (pi, l), то из этого следует что S1j Ni £ N. Т.к. алгоритм обхода является f (x) - алгоритмом обхода, маркер annexing (pj, l) был послан не более f (Nj) раз, что дает общее количество сообщений передающих маркеры annexing уровня l не более S1j f(Ni), что не превышает f (N), потому что f выпуклая. Каждый процесс посылает не более одного маркера chasing на каждом уровне, что дает не более N маркеров chasing на уровень.
Таким образом имеется не более (1 + log k) различных уровней, и не более f (N) + N сообщений посылаются на каждом уровене, что доказывает результат. o
Построение Attiya. Другое постоения алгоритма выбора из алгоритмов обхода давалось Attiya [Att87]. В этом построении обход одного маркера, скажем с идентификатором q, не прерывается до тех пор, пока маркер не достигнет процесса r уже посещенного другим маркером, скажем процесса p.Маркер annexing ждет в r, но посылает маркер "охотник", чтобы преследовать маркер p и затем ветнуться в r, если p может быть успешно побежден. Если охотник возвращается, не нужно начинать новый обход, а текущий обход маркера q продолжается, таким образом потенциально сокращается сложность по сообщениям. Чтобы позволять охотнику возвращаться, чтобы обработать r, сеть должна быть двунаправленая. Если используется f (x) - алгоритм обхода, результирующий алгоритм выбора имеет сложность по сообщениям приблизительно 3. S1j f(N/ i)
7.4.2 Применения Алгоритма KKM
Если f (x) - алгоритм обхода для класса сетей существует, этот класс как считают - f (x) -обходимый.
Выбор в кольцах. Кольца - x-обходимо, следовательно KKM алгоритм выбирает лидера в кольце используя 2N log N сообщений.
Выбор в кликах. Клики - 2x-обходимы, следовательно KKM алгоритм выбирает лидера в клике, использующей 3N log N сообщений согласно Теореме 7.24. Более осторожный анализ алгоритма показывает, что сложность - фактически 2N log N + 0 (N) в этом случае. Каждый маркер преследуется, используя не более трех сообщений chasing, так что общее количество сообщения chasing в вычислении, ограничено 3.S0logN+12- i N= 0(N). Никакой алгоритм выбора для клик со сложностью лучше чем 2NlogN + 0 (N) не известен до настоящего времени. Нижняя граница Ω (NlogN) была доказана Korach, Moran, и Zaks [KMZ84].
Нижняя граница не соблюдается, если сеть имеет направление глобального смысла [LMW86]. В сети, которая имеет направление глобального смысла, каналы процесса помечены целыми числами от 1 до N-1, и там существует направленный гамильтонов цикл такой, что канал pq помечен в процессе p расстоянием от p до q в цикле: см. Раздел B. 3. Loui, Matsushita. И West [LMW86] дал 0 (N) алгоритм выбора для клик с направление глобального смысла, но на вычисление направление глобального смысла затрачивается Ω (N2) сообщений, даже если лидер доступен [Tel94].
Выбор в торе. Торические сети - x-обходимы, следовательно KKM алгоритм выбирает лидера в торе используя 2N log N сообщений.
Тор должен быть помечен (то есть, каждый край помечен как Up, Left и т.д.) чтобы применить x-алгоритм обхода (Алгоритм 6.11). Peterson [Pet85] дал алгоритм выбора для решетки и тора, который использует 0 (N) сообщения и не требует, чтобы грани были помечены.
Выбор в гипекубах. Гиперкубы со смыслом направлений - x-обходимы (см. Алгоритм 6.12), следовательно KKM алгоритм выбирает лидера в гиперкубе, использование 2N log N сообщений. Tel [Tel93] предложил алгоритм выбора для гиперкубов со смыслом направлений, который использует только 0 (N) сообщений. Вычисление смысла направлений стоит 0 (1.51) сообщений [Tel94], это также и сложность GHS алгоритма когда он применяется к гиперкубу.
Tel [Tel93] дал алгоритм выбора для гиперкубов со смыслом направлений, который использует 0 (N) сообщений.
Упражнения к Главе 7
Раздел 7.1
Упражнение 7.1 Докажите, что сравнительный алгоритм выбора для произвольных сетей - алгоритм волны, если случай, в котором процесс становится лидером, расценен как случай решения.
Упражнение 7.2 Покажите, что сложность по времени Алгоритма 7.1 2D.
Раздел 7.2
Упражнение 7.3 Докажите, что идентификатор Σ1m H i = (m + 1) H i - m используемый в Подразделе 7.2.1.
Упражнение 7.4 Покажите, что ln (N + 1) < HN < ln (N) + 1. (ln означает натуральный логарифм.)
Упражнение 7.5 Рассмотрите алгоритм Chang-Роберта согласно предположению, что каждый процесс является инициатором. Для какого распределения идентификаторов по кольцу сложность по сообщениям минимальна и сколько сообщений обменены в этом случае?
Упражнение 7.6 Какова средняя сложностью алгоритма Chang-Роберта, если имеется точно S инициаторов, где каждый выбор процессов S, одинаково, вероятно будет набором инициаторов?
Упражнение 7.7 Дайте начальную конфигурацию для Алгоритма 7.7, для которого алгоритм фактически требует ëJog N + 1û раундов. Также дайте начальную конфигурацию, для которой алгоритм требует только двух раундов, независимо от числа инициаторов. Является ли это возможным для алгоритма, чтобы закончиться в одном круге?
Упражнение 7.8 Определите набор ecr (как определяет Lemma 7.10) для алгоритма Chang-Роберта.
Раздел 7.3
Упражнение 7.9 Примените вырождение к кольцевому алгоритму и сравните алгоритм с алгоритмом Chang-Роберта. Каково различие и каково влияние этого различия?
Упражнение 7.10 Определите для каждого из семи типов сообщения, используемых в Gallager/Humblet/Spira алгоритме, может ли сообщение этого типа быть послано узлу в состоянии sleep.
Упражнение 7.11 Предположим, что GHS алгоритм использует дополнительную процедуру пробуждения, которая гарантирует, что каждый узел начинает алгоритм в пределах единиц N время.
Докажите по индукции, что после не более чем 5N l — 3N единиц времени каждый узел - на 1 уровне. Докажите, что алгоритм заканчивает в пределах 5NlogN единиц время.
Раздел 7.4
Упражнение 7.12 Покажите, что O (NlogN) алгоритм для выбора в плоских сетях существует.
Упражнение 7.13 Покажите, что существует 0 (NlogN) алгоритм выбора для тора без смысла направлений.
Упражнение 7.14 Покажите, что существует 0 (NlogN) алгоритм выбора для гиперкубов без смысла направлений.
Упражнение 7.15 Покажите, что существует O (N (logN + k)) алгоритм выбора для сетей с ограниченной степенью k (то есть, сети, где каждый узел имеет не более k соседей).
8 Обнаружение завершения
Вычисление распределенного алгоритма заканчивается, когда алгоритм достигает конечной конфигурации; то есть конфигурация, в которой никакие дальнейшие шаги алгоритма невозможны. Не всегда в предельной конфигурации каждый процесс находится в конечном состоянии; то есть в таком состоянии,что нет ни одного события применимого к процессу. Рассмотрим конфигурацию, в которой каждый процесс находится в состоянии, которое позволяет получать сообщения, и все каналы пусты. Такая конфигурация является конечной, но состояния процессов могут быть промежуточными состояния в вычислении. В этом случае, процессы не знают, что вычисление закончилось; такое завершение вычисления называется неявным. Завершение называется явным в процессе, если состояние этого процесса в конечной конфигурации - конечное состояние. Неявное завершение вычисления также называется завершением сообщений, потому что после достижения конечной конфигурации сообщения больше не посылаются. Явное завершение также называется завершением процессов, потому что при явном завершении алгоритма процессы закончивают свое выполнение.
|
|
|
