Путаница по поводу активного / пассивного состояния для алгоритма Дейкстры-Шолтена
Использование алгоритма Дейкстры-Шолтена, описанного в книге Джеральда Тела "Введение в распределенные алгоритмы":
var state_p. : (active, passive) init if p=p0 then active else passive ;
sc_p : integer init 0 ;
father_p : Set<P> init if p=p0 then p else udef ;
S_p: {state_p = active}
begin send (mes, p) ; sc_p := sc_p + 1 end
R_p: { A message (mes, q) has arrived at p }
begin receive (mes, q) ; state_p := active ;
if father_p = udef then father_p := q else send (sig, q) to q
end
I_p: { statep = active }
begin state_p := passive ;
if sc_p = 0 then (* Delete p from T *)
begin if father_p = p
then Announce
else send (sig, father_p) to father_p ;
father_p := udef
end
end
A_p: { A signal (sig,p) arrives at p }
begin receive (sig,p) ; sc_p := sc_p - 1 ;
if sc_p = 0 and state_p = passive then
begin if father_p = p
then Announce
else send (sig, father_p) to father_p ;
father_p := udef
end
end
А вот работающий пример из книги Массачусетского технологического института "Распределенные алгоритмы Вана Фоккинка".
Пример 6.1. Мы рассматриваем одно возможное вычисление базового алгоритма, поставляемого с алгоритмом Дейкстры-Шолтена, на неориентированном кольце трех процессов p, q, r.
(1) Вначале инициатор p отправляет базовые сообщения q и r и устанавливает ccp равным 2. После получения этих сообщений q и r оба становятся активными и присоединяются к T с родительским p.
(2) q отправляет базовое сообщение в r и устанавливает ccq равным 1. После получения этого сообщения r отправляет обратно подтверждение, что заставляет q уменьшить ccq до 0.
(3) p становится пассивным. (Поскольку ccp = 2, он остается в T.)
(4) r становится пассивным. Поскольку ccr = 0, он отправляет подтверждение своему родительскому p, что заставляет p уменьшить ccp до 1.
(5) q отправляет базовое сообщение в r и устанавливает ccq в 1.
(6) q становится пассивным. (Поскольку ccq = 1, он остается в T.)
(7) Обратите внимание, что все три процесса теперь пассивны, но все еще есть сообщение, перемещающееся от q к r. После получения этого сообщения r снова становится активным и присоединяется к T с родительским q.
(8) r становится пассивным. Поскольку ccr = 0, он отправляет подтверждение своему родительскому q, что заставляет q уменьшить ccq до 0.
(9) Так как q пассивен и ccq = 0, он отправляет подтверждение своему родительскому p, что заставляет p уменьшить ccp до 0.
(10) Поскольку p пассивен и ccp = 0, он вызывает Announce.
Вопрос
Почему в (2), когда q отправляет сообщение, оно не становится пассивным сразу, а в (5) оно становится пассивным еще до того, как сообщение получено? Что определяет, когда будет выполнен шаг I_p (в алгоритме), почему процессы становятся пассивными таким образом, это кажется недетерминированным!?