In distributed computing, the bully algorithm is a method for dynamically electing a coordinator or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator.

We assume that:

• the system is synchronous.
• processes may fail at any time, including during execution of the algorithm.
• a process fails by stopping and returns from failure by restarting.
• there is a failure detector which detects failed processes.
• message delivery between processes is reliable.
• each process knows its own process id and address, and that of every other process.

Properties and Performance

• E1: Safety

  • Satisfied if no process is replaced and the timeout T estimate is accurate
  • Not satisfied if crashed process is replaced while another process is announcing that it is the new coordinator

• E2: Liveness

  • Satisfied for a synchronous system and reliable transmission

• Bandwidth utilisation

  • Best case

    Process with the second highest identifier detects coordinators failure and elects itself coordinator and sends $N-2$ coordinator messages

  • Worst case

    Requires $O(N^2)$ messages when lowest ID detects failure $\rightarrow$ $N-1$processes with higher IDs start election, having $(N-1) + (N-2) + ... +1 = N(N-1)/2$ messages sen

• Turnaround - One process can send a message to other processes simultaneously.

  • Best case - Transmission time of 1 message ( the coordinator messages)
  • Worst case - Transmission time of 4 messages ( One for election message sent by lowest ID, one for lowest ID receiving responses by others, one for second highest ID confirming the failure of the highest ID and one for second highest ID sending coordinator message)