What is ring election algorithm?

Need for election algorithms

Election algorithms are essential in distributed data systems so that there is consensus between nodes of which node is labelled as the master node responsible for coordination between nodes or centralized lookups.

The important question is defining the criteria for choosing the leading node when there are multiple candidates.

It's 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's 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.

Ring algorithm mechanism

On the overview, 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.

The algorithm is suitable for systems arranged in a unidirectional ring. The list of operational systems are circulated around until the list reaches the node that has initiated the election.

We only have one kind of message, the Election message.

• Let there be n different nodes with unique identifiers ranging from $0$ to $n−1$.

• Given that $5$ is the highest ID amongst the nodes, it would be the leader. Assuming that the leader crashes and node $2$ and node $0$ are to notice the breakdown of node with ID $5$, they would result in two different election messages each.

Each node appends its ID as it receives the election message.

• The election message will be forwarded to each of the node's next linked nodes.

For instance, node $0$ would propagate the message to node $1$ and node $2$ would propagate the message to node $3$.

• Proceeding further, the election message would be propagated to the neighbors until the respective election message reaches the node that initiated the election.

This would mean that the election message initiated by node 000This can be verified by checking the first element in the list. If the first element is 0, it would imply that node 0 has initated the election. would be circulated back to node $0$ and this represents the terminating condition.

Note: Node $5$, which has crashed, would simply forward the election message without appending its id.

• Nodes $0$ and $2$ would find the maximum of the IDs in the lists circulated and accordingly choose the node with maximum ID as the coordinator.

In this case, nodes $0$ and $2$ would identify that node $4$ is the new coordinator, and sends out coordinator messages to every other node in the system.

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 make use of election algorithms.