Bully Algorithm Assignment Help

• Each process includes a unique numerical ID
• Processes understand the Ids as well as address of each and every additional process
• Communication is actually thought reliable
• Key Concept: choose process along with highest ID
• Process initiates election if it just recovered from failure or even if coordinator failed
• 3 message kinds: election, OK, I won
• Several processes may start a good selection concurrently
  • Need consistent outcome
• O(n²) messages needed along with n processes
  
  

Bully Algorithm Details:

• Any process P may start initiate an election
• P sends Election messages to any or all process along with higher Ids as well as awaits OK messages
• If no OK messages, P becomes coordinator as well as sends I won messages to any or all process along with lower Ids
• If this receives an OK, it drops out as well as waits to have an I won
• If the process receives an Election msg, it returns an OK as well as begins an election
• If the process gets the receives a I won, it treats sender an coordinator
  
  

Bully Algorithm Example:

• The bully election algorithm
• Process 4 holds an election
• Process 5 and 6 respond, telling 4 to stop
• Now 5 and 6 each hold an election

• d) Process 6 tells 5 to stop
• e) Process 6 wins and tells everyone
  
  

Comparison Bully algorithm and Ring algorithm:

• Assume n processes and one election in progress
• Bully Algorithm
  • Worst Case: Initiator will be node together with least expensive ID
    • Triggers n-2 elections with higher ranked nodes: O( n² ) msgs
  • Best Case: Immediate election: n-2 messages
• Ring Algorithm
  • 2 ( n-1 ) messages always