Hirschberg-Sinclair Algorithm Assignment Help

• Operates within phases, requires bidirectional ring
• In kth stage, send own id in order to 2^k processes upon each attributes associated with yourself (directly send and then next processes along with id as well as k in it)
• If id received, forward if received id more than own id, otherwise ignore
• Last process within the chain sends a reply to originator that it's id less than received id
• Replies tend to be usually forwarded
• A process would go to (k+1)th phase only when this gets an answer through each sides in kth phase
• Process getting its own id – declare itself ‘leader’

Message Complexity:

• Message Complexity : O( nlgn )
• Lots associated with additional algorithms can be exist with regard to rings
• Lower Bound Result :
  • Any comparison-based leader election algorithm in a ring requires Ώ(nlgn) messages.