Bully algorithm

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.

Assumptions

The algorithm assumes that:^[1]

• 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.

Algorithm

The algorithm uses the following message types:

• Election Message: Sent to announce election.
• Answer (Alive) Message: Responds to the Election message.
• Coordinator (Victory) Message: Sent by winner of the election to announce victory.

When a process P recovers from failure, or the failure detector indicates that the current coordinator has failed, P performs the following actions:

1. If P has the highest process id, it sends a Victory message to all other processes and becomes the new Coordinator. Otherwise, P broadcasts an Election message to all other processes with higher process IDs than itself.
2. If P receives no Answer after sending an Election message, then it broadcasts a Victory message to all other processes and becomes the Coordinator.
3. If P receives an Answer from a process with a higher ID, it sends no further messages for this election and waits for a Victory message. (If there is no Victory message after a period of time, it restarts the process at the beginning.)
4. If P receives an Election message from another process with a lower ID it sends an Answer message back and starts the election process at the beginning, by sending an Election message to higher-numbered processes.
5. If P receives a Coordinator message, it treats the sender as the coordinator.

See also

• Coordinator Election
• Chang and Roberts algorithm

References

• Witchel, Emmett (2005). "Distributed Coordination". Retrieved May 4, 2005.
• Hector Garcia-Molina, Elections in a Distributed Computing System, IEEE Transactions on Computers, Vol. C-31, No. 1, January (1982) 48–59
• L. Lamport, R. Shostak, and M. Pease, "The Byzantine Generals Problem" ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982.