分布式计算-Peterson/Dolev-Klawe-Rodeh算法

1、首先计算最小标识，并使它为每一进程所知。具有该标识那个进程变成领导人，其他进程都被击败。如果把算法的执行看作是标识的执行，而不是进程的执行，算法就会容易理解。初始时，每个标识是活动的，在每一轮以后，有一些标识变成被动的。在一轮中，一个活动标识和与它相邻的两个活动标识（一个顺时针，一个逆时针）进行比较，如果它是局部最小，则它在那一轮中生存下来。

2、如果在该轮的一开始，进程P持有活动标识CIp，则称进程P是活动的，否则它是被动的，简单地传递所有它所接收的消息。活动进程把它的当前标识发送到下一个活动进程，并利用消息<one,.>获得前一个活动进程中的当前标识，将接收的标识存储在变量acnp中。如果标识在这轮中幸存下来，它将是下一轮中p的当前标识。为决定是否标识acnp在这轮幸存下来，就要将它与cip和消息<two,.>中所得到的活动标识比较。进程P发送消息<two,acnp>,使得在下一个活动进程中作出决策成为可能。

3、算法

var CIp:P init p;(*P的当前活动标识*)

       acnp:P init udef;

       winp:P init udef;

      statep:(active,passive,leader,lost) init active;

 

begin if p is initiator then statep:=active else statep:=passive;

           while winp=udef do

                    begin if statep=active then

                             begin send <one,CIp>;receive <one,q>;acnp:=q;

                                        if acnp=CIp then (*acnp是最小的*)

                                           begin send <smal,acnp>;winp:=acnp;

                                                     receive <smal,q>

                                           end

                                        else

                                           begin send <two,acnp>;receive <two,q>;

                                                     if acnp<CIp and acnp<q

                                                        then CIp:=acnp

                                                        else statep:=passive

                                           end

                                  end

                              else (*statep=passive*)

                                       begin receive <one,q>;send <one,q>;

                                                 receive m,;send m;

                                                 if m is a <smal,q> message then winp:=q

                                        end

                           end;

                       if p=winp then state p:=leader else statep:=lost

end