Путаница по поводу активного / пассивного состояния для алгоритма Дейкстры-Шолтена

Использование алгоритма Дейкстры-Шолтена, описанного в книге Джеральда Тела "Введение в распределенные алгоритмы":

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 (в алгоритме), почему процессы становятся пассивными таким образом, это кажется недетерминированным!?

0 ответов