What is 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. This algorithm applies to system where every process can send a message to every other process in the system.
Bully Algorithm assumptions
- 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
How does Bully Algorithm work
- 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:
- 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.
- If P receives no Answer after sending an Election message, then it broadcasts a Victory message to all other processes and becomes the Coordinator.
- 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.)
- 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.
- If P receives a Coordinator message, it treats the sender as the coordinator.
Network bandwidth utilization
Assuming that the bully algorithm messages are of a fixed (known, invariant) sizes, the most number of messages are exchanged in the group when the process with the lowest ID initiates an election. This process sends (N−1) Election messages, the next higher ID sends (N−2) messages, and so on resulting in N*N messages.
