Dolev-Klawe-Rodeh

This is a discussion on Dolev-Klawe-Rodeh within the C Programming forums, part of the General Programming Boards category; Can anybody do this; The algorithm of Chang and Roberts achieve the 0(NlogN) (N the number of nodes) complexity of ...

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    7

    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!!!

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Lemme guess. Homework?

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Yes of course someone can "do" that - I'm sure the author can at least.
    Do you have any code to post, or did you get as far as "The algorithm" and give up?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Nov 2007
    Posts
    7
    I don't give up but i can't do that.I don't know how...i just need help!!!

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    The idea about homework is described here. In short, you either ask a very specific question, or you post some code that you have a problem with and ask a question on that code. You don't just post your entire homework description and hope that someone produces it for you, complete and ready to hand in.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User
    Join Date
    Nov 2007
    Posts
    7
    Ok i found this but i can't understand it.I don't think that the following is c...

  7. #7
    Registered User
    Join Date
    Nov 2007
    Posts
    7

    dolev

    I can't understand the following...Is it c;
    Attached Files Attached Files

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    No, that is not C (or C++). I'm not quote sure what it is..

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Rather than trying to steal someone else's code (whatever that is), why don't you tackle the problem yourself?

    Try not to spam your question on every forum on the internet. I hope no-one is stupid enough to do your homework, ask MacGyver -- he might do it

    Go and ask your teacher, or whoever gave you the assignment and say you have no idea -- they might be able to help you!
    Last edited by zacs7; 11-27-2007 at 03:35 PM.

  10. #10
    Registered User
    Join Date
    Oct 2007
    Posts
    62
    it is SPIN language
    http://en.wikipedia.org/wiki/Spin_(programming_language)

    Your best bet it do do it in C and work on it. Post code (yours) that you don't get and the programmers here will provide resources and hints to get you there. Trust me I know!!
    Last edited by tikelele; 11-27-2007 at 03:53 PM.

  11. #11
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,540
    > I can't understand the following...Is it c;
    Nope, though it looks like it might use the C pre-processor.

    With all those 'do od' constructs, it reminds me of some of the old ALGOL languages, though which one I'm not sure.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    For a moment, I thought it was Verilog.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21