Electing master node in a cluster using Bully Algorithm

This blog post explains the end to end implementation of the Bully Algorithm which is a leader election algorithm in Distributed Systems.

What is a Distributed System

A distributed system is a collection of independent computers that appears to its users as a single coherent system.

These multiple nodes are physically separate but linked with each other. They communicate with each other to complete each others’ and one end goal.

Distributed Algorithms

Distributed Algorithms run in a Distributed System. We have two types of Distributed algorithms which are Leader Election Algorithms and Consensus Algorithms.

In a clustered system, Leader Election Algorithms helps nodes to decide who the leader of the system is.

In order to distribute workload among worker nodes, it needs a leader/ Coordinator in a distributed system.

In this post, we are going to discuss Bully Algorithm which is a leader election algorithm.

Bully Algorithm

• Each node has a unique ID.
• Each node communicates with each other and broadcasts their IDs.
• The node which has the highest ID becomes the Leader.

Let’s move to the implementation of the algorithm. This is implemented using Python 3.8, Flask Framework. The communication between nodes is done using Rest API calls.

In this implementation, it has been implemented how initially the master node is going to be selected in a clustered system.

1. When a node is started, each node is assigned a node ID. Node ID is a random number generated according to the time that the node is started.
2. Node is registered at the startup in the Service Registry by providing its node name, node ID, port, and health check. We use a Service Registry to obtain the information and health of each node. In this implementation, Consul has been used as the Service Registry.
3. Once the nodes are registered, each node gets the other registered nodes’ details from the service registry.
4. Then each node starts to communicate with each other. How it does is each service has its own API to expose its details.

As an example, if my node is running in port 5001, I need to get the details of the service running in port 5002. Then I will call the API as below. This is a GET call.

http://localhost:5002/nodeDetails

Then the node 5001 will receive a response including node name, node id, coordinator, election, port.

Each node has its own bully class to update the details.

• coordinator: it says if that specific node is the coordinator of the cluster or not. Initially, this value is false.
• election: it says if any election is ongoing in the cluster at the moment.

5. Then each node has its own timeout value and tries to start the election.

6. Before that, each node checks if there is an election on going in the cluster. In other words, it checks if the cluster is electionReady. electionReady is the cluster should not have any coordinator node or there should not be any election on going.

7. If the cluster is electionReady, the node will start the election by making its own election flag ‘true’.

8. As mentioned earlier, the node which has the highest ID becomes the coordinator of the system. In order to satisfy that condition, the node first checks if there are any nodes that have a higher ID than itself using the collected information. If there are no nodes, that specific node wins the election, and it becomes the coordinator. Then it will announce that to the other nodes that it is the coordinator/leader in the system.

9. If there are higher nodes than itself, it will send a message to those nodes saying that there is an election. If the specific node gets a response from higher nodes, it gets to know that there are active higher nodes in the cluster and it stays back from the election and let the other nodes handle the election.

10. In this implementation, it has been used a proxy. A higher node can get many requests from lower ID nodes. Once a higher node gets a request, it starts executing the election method. If there are many requests come, this node tries to execute the election method several times. Therefore, to execute the election method exactly once, this proxy will route the first request only to the specific API. The requests from other nodes just let hit the proxy.

11. Once the responseAPI gets the request from a lower node, it actually checks if the coming node id is greater than the its node ID. If yes, it will start executing the election method.

12. Finally, it checks as described in step 9. This process goes recursively until they do not have any higher node ids than themselves. Once it reaches that level, itself becomes the coordinator of the system and let the other nodes know it and master starts its own work.

Please find the complete implementation of the Bully algorithm. All the instructions to run are in the README.md file.