Dolev-Klawe-Rodeh

Can anybody do this;

The algorithm of Chang and Roberts achieve the 0(NlogN) (N the number of nodes) complexity of messages in the medium case, but at worst however it achieves 0(n^2). The algorithm of Peterson of/Dolev-Klawe-Rodeh achieves complexity of messages the O(NlogN) at worst situation improving the algorithm of Chang and Roberts for the leader election of head in rings of one way direction, where each node has his own unique identity.
The algorithm is based on the following idea.Firstly each identity is active, but in each round some identities becomes passive,as we will show then.In a round an active identity compares itself with the active identities of her two neighbouring nodes, that are found the one at the time and the other contrary to the time of indicators of clock. Supposing that is elected the smaller identity, if an active identity constitutes local minimal, then she remains active and goes to the next round, otherwise she becomes passive. So, after logN rounds will only have remained in the ring an active identity and this gains the election.
This idea can be applied directly in rings of that are double direction. In one way round of direction,the messages can move itself only at a time (eg that of indicators of clock), thing that makes difficult the acquisition of identity that is found at the direction of movement of messages.We suppose that we have a ring with three active in line identities r, q, p. Then q it can receive the message of r, but it cannot receive the message of p because the ring is one way of direction and should not waits for a entire circle to receive it.However in order to be the comparison,q sends her identity in the p and the r does not send simply her identity in q, but q promotes him in the p, in order that the p make the comparison. The activities that lose the election and become passive, simply promote the messages that they receive. If a activity receives a identity that is equal with hers then it is called leader, while if it receives a identity different from hers compares this identity with hers and with running minimal that it has kept from the previous comparisons. If the missed identity is smallest, then the activity becomes passive and it keeps new minimal.
For each activity it will be supposed you store her identity, running minimal, the identity of the leader and her situation.


It's new for me and i have no idea!!!

 

Ifound this but i don't think that it's c...

Code:

/* dolev-klawe-rodeh leader election */

#define N	5
#define I	3
#define L	10

chan ch[N] = [L] of {int};
int nr_of_leaders = 0;

proctype process(chan in, out; int id) {

int d, e, f;

printf("MSC: identitiy is %d\n", id);

act:
  d = id;
  do 
    :: true ->
      printf("MSC: value of d is %d\n", d);
      out!d; in?e;
      if 
        :: (e == d) ->
          printf("MSC: %d is the leader.\n", d);
          nr_of_leaders = nr_of_leaders+1;
          goto stop
        :: else ->
           skip
      fi;
      out!e; in?f;
      if 
        :: (e >= d) && (e >= f) ->
          d = e
        :: else ->
          printf("MSC: I become passive.\n");
          goto pas
      fi;
  od;

pas:
  do :: in?d -> out!d od;

stop:
  skip

}

init {
  byte i;
  atomic {
    i=1;
    do 
      :: i <= N -> 
        run process(ch[i-1], ch[i%N], (I+N-i)%(N+1));
        i = i+1
      :: i > N ->
        break
    od
  }
}

 

nobody know this;