473,325 Members | 2,771 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,325 software developers and data experts.

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!!!
Nov 27 '07 #1
1 2010
oler1s
671 Expert 512MB
Sorry to hear about your ridiculously hard homework assignment. What I don’t get it is why the teacher would give you such an assignment without teaching you the prerequisite material.
Nov 27 '07 #2

Sign in to post your reply or Sign up for a free account.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.