Удаление узлов из T также необходимо по двум причинам. Во первых, основное сообщение удаляется после его получения. Во вторых, для того чтобы гарантировать продвижение алгоритма обнаружения дерево должно быть опустошено за конечное число шагов после завершения.
var statep : (active, passive) init if p = p0 then active else passive;
sсp : integer init 0;
fatherp : P init if p == p0 then p else udef;
Sp: { statep = active }
begin send (mes, p) ; scp := scp + 1 end
Rp: { сообщение (mes, q) прибывает в p }
begin receive (mes, q);, statep := active;,
if fatherp = udef then fatherp := q else send ( sig, q ) to q
end
Ip: { statep = active }
begin statep := passive ;
if scp = 0 then (* Удаляем p из T *)
begin if fatherp = p then Announce else send (sig , fatherp) to fatherp ;
fatherp := udef
end
end
Ap: { Сигнал (sig ,p) прибывает в p }
begin receive (sig,p) ; scp := scp -1 ;
if scp = 0 and statep = passive then
begin if fatherp = p then Announce else send ( sig, fatherp ) to fatherp ;
fatherp := udef
end
end
Алгоритм 8.3 dijkstra-scholten алгоритм.
Сообщения - листья T; процессы поддерживают переменную, которая считает число их сыновей в T. Удаление сына процесса p происходит в другом процессе q; это происходит при получении сообщения сына или удалении сына процесса q. Для того, чтобы предотвратить искажение данных счетчика сына p, процессу p посылается сигнальное сообщение (sig, p) об удалении его сына. Это сообщение заменяет удаленного сына p, и его удаление, т.е. получение, происходит в процессе p и p при получении сигнала уменьшает на единицу счетчик сыновей.
Алгоритм описан как Алгоритм 8.3. Каждый процесс p имеет переменную fatherp, которая не определена если pÏVT , равна p если p является корнем, и является отцом p, если p - не корень в T. Переменная scp содержит число сыновей p в T.
Доказательство правильности строго устанавливает, что граф T, как определено, является деревом и что он становится пустым только после завершения основного вычисления. Для любой конфигурации g Алгоритма 8.3, определено
VT = {p : fatherp¹ udef} È {передается (mes,p) } È {передается ( sig,p) }
И
ET = {(p, fatherp) : fatherp¹ udef Ù fatherp ¹ p}
È { ((mes, p), p) : (mes, p) передается }È{((sig,p), p) : (sig, p) передается }.
Безопасность алгоритма следует из утверждения P, определенного следующим образом
P º statep = active Þ p Î Vp (1)
Ù (u, v) Î ET Þ u ÎVT Ù v Î VT Ç P (2)
Ù scp = #{v : (v, p) ÎET } (3)
Ù VT ¹ Æ Þ T дерево с корнем p0 (4)
Ù (statep = passive Ù scp = 0) Þ p Ï VT (5)
Значение этого инварианта следующие. По определению, множество узлов T включает все сообщения (основные и управляющие), и согласно пункту (1) оно также включает все активные процессы. Пункт (2) скорее технический; он заявляет, что T - действительно граф, и все ребра направлены к процессам. Пункт (3) выражает правильность счетчика сыновей каждого процесса, и пункт (4) заявляет, что T - дерево, и p0 - корень. Пункт (5) используется, чтобы показать, что дерево действительно разрушается, если основное вычисление заканчивается. Для доказательства правильности, обратите внимание, что из P следует, что fatherp = p только для p = p0.
Lemma 8.4 P - инвариант Dijkstra-Scholten алгоритма.
Доказательство. Первоначально statep = passive для всех p ¹ p0 и fatherp0¹ udef, который доказывает пункт (1). Также, ET = Æ, что доказывает (2). Так как scp= 0 для каждого p, удовлетворяется (3). VT = {po} и ET = Æ, таким образом T - дерево с корнем p0, что доказывает (4). Единственный процесс в VT- p0, и p0 активен.
Sp: Никакой процесс не становится активным в Sp, и никакой процесс не удаляется из VT, так что (1) сохраняется.
Применимость действия означает, что p, отец нового узла (mes, p), находится в VT, что доказывает, что (2) сохраняется. В результате действия, VT дополняется узлом (mes, p) и ET дугой ((mes, p), p), что означает, что T остается деревом, и scpправильно увеличивается, чтобы представить нового сына p, следовательно (3) и (4) сохраняются.
Никакой процесс не становится пассивным листом, и никакой процесс не вставлен в VT , таким образом (5) сохраняется.
Rp: Или p уже был в VT (fatherp¹ udef) или p вставлен в VT после действия, таким образом (1) сохраняется.
Если значение fatherp определено, его новое значение - q, и если сигнал послан процессом p, его отец - также q, и q находится в VT, таким образом (2) сохраняется. Число сыновей q не изменяется, потому что сын (mes, q) процесса q заменяется сыном p или сыном (sig, q), так что scq остается правильным, который сохраняет (3).
Структура графа не изменяется, таким образом (4) сохраняется. Процесс p находится в VT после действия в любом случае, таким образом (5) сохраняется.
Ip: Переход p в пассивное состояние сохраняют (1), (2), (3) и (4). Из того, что p был прежде активен следует, что p был в VT. Если scp = 0, p удаляется из VT, таким образом (5) сохраняется.
Затем мы рассматриваем что случится при удалении p из T, то есть, если p окажется пассивным листом T.
Если сигнал посылается процессом p, отец сигнала - последний отец p, который находится в VT, следовательно (2) сохраняется. В этом случае, сигнал заменяет p как сын процесса fatherp, следовательно fatherfather p остается правильным, и (3) сохраняется. Структура графа не изменилась, следовательно (4) сохраняется.
Иначе, то есть, если fatherp= p, p = p0 и p, являющийся листом, означает, что p был единственным узелом T, так что удаление опустошает T , что сохраняет (4).
Ap: Получение сигнала уменьшает число сыновей p на единицу, и присваивание значения на scp гарантируетсохранение (3). То, что p был отецом сигнала, означает, что p был в VT. Если statep = passive и после получения scpприсваивается 0, p удаляется, таким образом сохраняется (5). Если p удаляется из VT, инвариант сохраняется по тем же причинам, что и для действия Ip. -
Теорема 8.5 Dijkstra-Scholten алгоритм (Алгоритм 8.3) - правильный алгоритм обнаружения завершения и использует М управляющих сообщений.
Доказательство. Пусть S сумма всех счетчиков сыновей, то есть, S = SpÎ P scp . Первоначально S = 0, S увеличивается на единицу при посылке основного сообщения (в Sp), S - уменьшается на единицу, когда получается управляющее сообщение (в Ap), и S никогда не становится отрицательным (из (3)). Это означает, что число управляющих сообщений никогда не превышает число основных сообщений в любом вычислении.
Чтобы доказать живость алгоритма, предположим, что основное вычисление закончилось. После завершения только действия Ap может иметь место и т.к. S уменьшается на единицу при каждом таком переходе, алгоритм достигает конечной конфигурации. Заметьте, что в этой конфигурации, VT не содержит никакие сообщения. Также, из (5), VT не содержит никаких пассивных листьев. Следовательно, T не имеет никаких листьев, что означает, что T пусто. Дерево стало пустым, когда p0 удалил себя, и программа такова, что p0 на этом шаге вызывает алгоритм объявления.
Чтобы доказать безопасность, обратите внимание, что только p0 вызывает алгоритм объявления, и делает это после того, как удаляет себя из VT. Из (4), T пусто, когда это случается,что заключает в себе term. -
Dijkstra-Scholten алгоритм достигает привлекательного баланса между передачей основных и управляющих сообщений; для каждого основного сообщения, посланного от p в q алгоритм посылает точно одно управляющее сообщение от q в p. Передача управляющих сообщений имеет нижнюю границу представленную в Теореме 8.2, так что алгоритм является оптимальным алгоритмом обнаружения завершения централизованных вычислений для худшего случая.
В описании этого подраздела, все сообщения содержат явное указание на их отца, но обычно это не является необходимым, потому что отец основных (управляющих) сообщений всегда их отправитель (адресат).
Dijkstra-Scholten алгоритм был обобщен для децентрализованных основных вычислений Shavit и Francez [SF86]. В их алгоритме, граф вычисления - лес, каждое дерево которого имеет в качестве корня инициатора основного вычисления. Дерево с корнем p обозначается Tp.
Алгоритм поддерживает граф F = (Vp , Ep), такой что (1) F является пустым или F - лес, каждое дерево которого имеет в качестве корня инициатора; (2) Vp включает все активные процессы и все основные сообщения. Как в алгоритме Dijkstra-Scholten завершении обнаруживается, когда граф становится пустым. К сожалению, в случае леса не так просто выяснить,является ли граф пустым. Действительно, свойство дерева вычислений иметь в качестве корня инициатора означает, что пустота дерева замечается корнем, который и вызывает алгоритм объявления. В случае леса, каждый инициатор замечает пустоту только собственного дерева, но это не означает, что весь леса пуст.