分布式计算-扩展Dijkstra-Feijen-Van Gasteren算法确认终止

当算法达到终止配置时,分布式算法的计算终止,即配置中不存在进一步可应用的算法步，每个进程处于允许接收的状态，且所有信道为空，即消息终止，则这个配置是终止的。

1、适于异步消息

规则A：当发送消息时，p使得unackp增加；当接收来自q的消息时，p向q发送确认消息；当接到确认消息时，p使得unackp减少。

规则B：当进程发送时，它变成黑色；仅当进程静止时，才变成白色。

2、算法

var statep:(active,passive);

      colorp:(white,black);

      unackp:integer init 0;

 

Sp:{statep=active}

        begin   send <mes>;unackp:=unackp+1;(*RULE A*)                      

                   colorp:=black;(*Rule B*)

         end

 Rp:{a message <mes> from q has arrived at p}

      begin receive <mes>;statep:=active;

               send <ack> to q (*Rule A*)

      end

Ip:{statep=active}

    begin statep:=passive end

 

Ap:{An ackonwledgement <ack> has arrived at p}

    begin receive <ack>;unackp:=unackp-1 end (*Rule A*)

 

start the detection,executed once by p0:

        begini send <tok,white> to pN-1 end

 

Tp:(*Process p handles the token <tok,c>*)

      {statep=passive∧unackp=0}

       begin if p=p0

                   then if (c=white∧colorp=white)

                               then Annouce

                               else send <tok,white> to pN-1

                    else if (colorp=white)  

                               then send <tok,c> to Nextp

                               else send <tok,black> to Nextp;

              colorp:=white (*Rule B*)

       end