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

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

0 голосов
/ 02 мая 2020

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

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

А вот пример работы из книги MIT «Распределенный Алгоритмы Вана Фоккинка '

Пример 6.1 Мы рассматриваем одно возможное вычисление алгоритма basi c, снабженного алгоритмом Дейкстры-Шолтена, для неориентированного кольца из трех процессов p, q, r.

(1) В начале инициатор p отправляет базовые c сообщения q и r и устанавливает ccp равным 2. После получения этих сообщений q и r оба становятся активными и присоединяются к T с родительским p.

(2) q отправляет базовое сообщение c в r и устанавливает ccq равным 1. После получения этого сообщения r отправляет обратно подтверждение, в результате чего q уменьшает ccq до 0.

(3) р становится пассивным. (Поскольку ccp = 2, он остается в T.)

(4) r становится пассивным. Поскольку ccr = 0, он отправляет подтверждение своему родительскому p, в результате чего p уменьшает ccp до 1.

(5) q отправляет базовое сообщение c в r и устанавливает ccq равным 1.

(6) q становится пассивным. (Поскольку ccq = 1, он остается в T).

(7) Обратите внимание, что все три процесса теперь пассивны, но все еще есть сообщение, перемещающееся из q в r. После получения этого сообщения r снова становится активным и присоединяется к T с родителем q.

(8) r становится пассивным. Поскольку ccr = 0, он отправляет подтверждение своему родителю q, что приводит к уменьшению ccq q до 0.

(9) Поскольку q пассивно и ccq = 0, он отправляет подтверждение своему родителю p, что заставляет p уменьшать ccp до 0.

(10) Так как p пассивно и ccp = 0, он вызывает Announce.

Вопрос

Почему в (2), когда q отправляет сообщение, оно не становится пассивным сразу, а в (5) оно становится пассивным даже до того, как сообщение пришло? Что определяет, когда выполняется шаг I_p (в алгоритме), почему процессы становятся пассивными таким образом, это кажется неопределенным c!?

...