Compare bully election algorithm with Ring algorithm
1 Answer

Bully Algorithm:

  • When the process having the lowest priority number detects the coordinator’s failure and initiates an election, in a system of n processes, altogether (n-2) elections are performed.
  • All the processes except the active process with the highest priority number and the coordinator process that has just failed perform elections.
  • So in the worst case,the bully algorithm requires O(n2) messages. When the process having the priority number just below the failed coordinator detects failure of coordinator, it immediately elects itself as the coordinator and sends n-2 coordinator messages.
  • So in the best case, it has O(n) messages. During recovery, a failed process must initiate an election in recovery.
  • So once again, Bully algorithm requires O(n2) messages in the worst case, and (n-1) messages in the best case.

Ring algorithm:

  • In ring algorithm, on the contrary, irrespective of which process detects the failure of coordinator and initiates an election, an election always requires 2(n-1) messages. (n-1) messages needed for one round rotation of the ELECTION message, and another (n-1) messages for the COORDINATOR message.

  • During recovery, a failed process does not initiate an election on recovery, but just searches for the current coordinator. So ring algorithm only requires n/2 messages on average during recovery

Please log in to add an answer.