What is a bully election algorithm?

Election algorithms are essential in distributed data systems to have a consensus between nodes, of which node is labeled as the master node. It is responsible for coordination between nodes or centralized lookups.

The imperative question boils down to defining the criteria for choosing the leading node when there are multiple candidates.

Note: It is the goal of leader election algorithm to choose an appropriate leader and let every other node in the system know about the elected leader.

It is the goal of an election algorithm to ensure the following:

• There should only be one leader among the nodes.

• All the nodes agree on who the leader is.

Bully algorithm mechanism

Any node can trigger a request for an election. However, one node can only issue a singular request at one point in time. The algorithm operates by identifying all the non-faulty nodes and electing the node with the largest identifier as the leader.

There can be three kinds of messages that nodes would exchange between each other during the bully algorithm:

1. Election message

2. OK message

3. Coordinator message

Example

Suppose there are n different nodes with unique identifiers ranging from $0$ to $n-1$.

Given that 5 is the highest ID amongst the nodes, it is the leader. Assuming that the leader crashes and node 2 are the first to notice the breakdown of the leader, the node with ID 2 initiates an election.

Accordingly, the node with ID 2 sends an election message to all nodes with an ID greater than its own ID.

Nodes 3 and 4 both receive the election message. However, since node 5 is crashed, it does not respond or receives the ping. Nodes 3 and 4 accordingly initiate election iteratively by broadcasting election messages to nodes with IDs greater than their own respective IDs.

Moreover, they respond with an OK message to the node that sent them a request for election since they are not the nodes with the highest IDs. This means that nodes 3 and 4 would confirm to node 2 that they are alive and non-crashed.

Node 4 receives the election message and accordingly responds with an OK message to node 3 to confirm its operating state. As of the previous case, node 5 does not respond as it is unavailable.

On the other hand, node 4 has already broadcasted an election message to node 5, and received no response. It simply figures out that node 5 has crashed, and the new node with the highest ID is node 4.

Node 4 figures out that it is the node with the highest ID, then sends a coordinator message to all of the alive nodes.

Consecutively, all nodes are updated with the new leader.

Pseudocode

Initiate node's perspective

1. The process $N_i$, with an ID equal to $i$, sends an election message to all nodes with an ID greater than $i$.

2. It awaits a response from the nodes:

   1. If there is no response, process $i$ wins the election.

   2. If it gets an OK message, it quits the election.

Receive node's perspective  

1. The process that receives an election message sends an OK message if a node ID is higher than its own. It then restarts and initiates an election message.

2. The process that receives an election message sends a coordinator message if it is the node with the highest ID.

Conclusion

On the whole, election algorithms are essential to ensure consensus and consistency between nodes in a distributed system. Essential systems that especially require a need for centralization or to assign a node with privilege use the election algorithms.