Election Algorithm, a Case Study.
Intro
In distributed algorithms, a coordinator is often required, and the Election Algorithm serves this purpose by selecting a unique coordinator. This technique is crucial for designating a leader among a group of processors. In the event that the current leader process becomes unavailable, the algorithm is employed to identify a replacement leader from the remaining processors. The algorithm’s decision on where to initiate a new leader is based on the unique priority numbers assigned to each active process in the system. The process with the highest priority assumes the role of the new leader when necessary. Consequently, when the leader experiences a failure, the algorithm identifies the active process with the highest priority and shares this information with all active processes in the system.
It’s important to note that there are two distinct election algorithms — Bully and Ring Algorithm — designed for different distributed system configurations. Let’s take a look at both, starting with the Bully Algorithm.
Bully Algorithm
The Bully Algorithm is a distributed protocol designed for leader selection within a network of processes or nodes. Its primary objective is to select a coordinator or leader from a set of processes. The fundamental concept of the Bully Algorithm revolves around guaranteeing that the node with the highest priority assumes the leadership role.
Now, let’s delve deeper into its concepts.
1. Each process is assigned a unique numerical ID, ensuring that every network participant possesses a distinct identifier.
Each participating ID: 1, 2, 4, 3, 52. Processes maintain knowledge of the IDs and addresses of all other processes, ensuring that each process is aware of the address associated with every ID and its corresponding connection.
3. In the Bully Algorithm, reliable communication is presumed. Messages exchanged among processes are assumed to be accurately delivered and in the proper sequence. This presumption simplifies the algorithm’s implementation by excluding concerns about communication failures.
4. Select a process as a coordinator: Bully algorithm selects the process with the highest ID, making 5 (from Fig 2.1) the coordinator.
5. Election is triggered upon recovery from a failure or coordinator failure. Any process, especially the one detecting the failed node, can initiate the election when a coordinator fails.
6. Several processes can initiate an election simultaneously.
The following takes place when a process, say “P” sends a message to the coordinator:
- If the coordinator remains unresponsive for the specified time interval “t,” it is considered a coordinator failure.
- Process “P” broadcasts an election message to all processes with a higher-priority numerical value.
- It waits for a response. If there’s no response within time interval “t,” process “P” self-elects as coordinator.
- It transmits a notification to lower-priority numbers and the process “P,” becomes the new coordinator.
After assuming the role of coordinator, P0 establishes connections
with P0-2, P0-1, and P0-3. This process is taken due to the lack of
response from the higher nodes, namely P2, P3, and P6, within the
defined time interval "t."5. If a response is received within time “t” from another process, “Q”:
A. Process “P” waits for another “t” interval to receive a message from “Q” confirming its election as the coordinator.
Get Victor Ehikioya Raeva’s stories in your inbox
Join Medium for free to get updates from this writer.
B. If “Q” does not respond within “t,” it’s considered a failure, and the algorithm restarts.
Once P0 receives confirmation from Q, acknowledging its role as
the coordinator, it proceeds to distribute the message to other
processes while it discards from the election.P0 delegates its roles to subsequent processes, such as P1, P2, etc. Thus, P1 triggers the initiation of both P2 and P3.
If a node or process sends an "ok," the role is transferred to the
highest priority.Case study: Understanding the Bully Algorithm
We can examine a few case studies to better understand how the Bully Algorithm works.
- From the diagram below, process 4 sends an election message to nodes higher than itself — nodes 5, 6, and 7.
2. Since the highest node, 7 is inactive (failed to respond within the time interval, “t”); 5 and 6 send an ok message because they are active. The process 4’s job is complete. Processes 5 and 6 can initiate messages with each other.
3. Processes 5 and 6 initiates an election message to the node process higher than themselves. 5 initiates to 6 and 7, and 6 sends to 7. But since 7 is inactive, no response is sent back during the time interval.
4. The process 6 wins the election because it has the highest priority and sends an “Ok” message to 5.
5. Process 6 sends a coordinator message to all lower nodes as the new coordinator of the processes.
This outlines the standard procedure employed by the Bully Algorithm for coordinator selection, from initiating an election to determining the highest priority. We can replicate this process using a basic Python simulation.
class Node:
def __init__(self, node_id):
self.node_id = node_id
self.leader = None
def __str__(self):
return f"Node {self.node_id}"
def start_election(self, nodes):
"""Initiate an election process."""
print(f"{self} initiates an election.")
higher_nodes = [node for node in nodes if node.node_id > self.node_id]
# Send election messages to higher nodes
for higher_node in higher_nodes:
higher_node.receive_election(self)
def receive_election(self, initiating_node):
"""Receive an election message and respond accordingly."""
print(
f"{self} receives an election message from {initiating_node}.")
if self.leader is None or self.node_id > self.leader.node_id:
print(
f"{self} sends an OK message to {initiating_node}.")
initiating_node.receive_ok(self)
else:
print(
f"{self} ignores the election message from {initiating_node}.")
def receive_ok(self, responding_node):
"""Receive an OK message and acknowledge the leader."""
print(
f"{self} receives an OK message from {responding_node}.")
self.leader = responding_node
print(
f"{self} acknowledges {responding_node} as the leader.")
if __name__ == "__main__":
# Create nodes with unique IDs
nodes = [Node(1), Node(2), Node(3), Node(4), Node(5), Node(6), Node(7)]
# Simulate leader election
for node in nodes:
node.start_election(nodes)
# Find the elected leader
elected_leader = max(nodes, key=lambda node: node.node_id)
print(f"\n{elected_leader} is elected as the leader.")Now that you have been introduced to the Bully Algorithm, let’s delve deeper into the Ring Algorithm, which is the second Election Algorithm.
Ring Algorithm
The Ring Algorithm is suitable for systems structured in a ring topology, whether logically or physically. It operates under the assumption of unidirectional links between processes, allowing each process to communicate exclusively with the one to its right. This algorithm employs an active list, which contains the priority numbers of all active processes in the system, for example: [1, 5, 11, 0, 8, 6].
How the Ring Algorithm Works
- When process P1 identifies a coordinator failure, it creates a new empty active list. Afterward, it sends an election message to its right neighbor while appending the number 1 to the active list.
- If process P2 receives an election message from processes on the left, it can respond in 3 ways:
1. If the incoming message does not include "1" in the current active
list, P1 appends 2 and forwards the message.
2. Upon receiving or sending its first election message, P1 initiates
a new active list comprising 1 and 2. Subsequently, it transmits an
election message with a list of both 1 and 2.
3. Should process P1 receive its own election message, denoted as 1,
it updates its active list with the numbers of all active processes
within the system. P1 identifies the highest priority number in the
list and assigns it as the new coordinator.Ring Algorithm case study
- In the event that process “P” suspects a coordinator failure, it assembles an election message, including its ID, and transmits it to the first active successor. Subsequently, each process appends its ID and relays the message to the next node. It’s also possible to have multiple concurrent elections in progress.
2. When the message returns to P, and it sees its own process ID in the list, the circuit is complete. “P, ” here represents the process ID. You can see below that both initiators of the election, 2 and 5 elect 6 from the active list as the new coordinator. P transmits a coordinator message with the new priority number.
You can also see a simple simulation of how the Ring Algorithm works.
class Node:
def __init__(self, node_id):
self.node_id = node_id
self.election_in_progress = False
self.election_id = 0 # Unique ID for the current election
self.neighbors = [] # List of neighboring nodes
def add_neighbor(self, neighbor):
self.neighbors.append(neighbor)
def initiate_election(self, candidate_id):
if self.election_in_progress:
return
self.election_in_progress = True
self.election_id += 1
if self.node_id == candidate_id:
self.declare_victory()
else:
print(f"Node {self.node_id} initiates Election {self.election_id}.")
for neighbor in self.neighbors:
neighbor.initiate_election(candidate_id)
def declare_victory(self):
print(
f"Node {self.node_id} wins Election {self.election_id}
and is elected as the leader.")
self.election_in_progress = False
def simulate_ring_election(num_nodes, initial_candidate_id):
# Create a list of nodes with unique IDs.
nodes = [Node(i) for i in range(num_nodes)]
# Connect nodes in a directed graph.
for i in range(num_nodes):
nodes[i].add_neighbor(nodes[(i + 1) % num_nodes])
# Start the election by initiating it at the initial candidate node.
initial_candidate = nodes[initial_candidate_id]
print(f"Node {initial_candidate.node_id} initiates Election 1.")
initial_candidate.initiate_election(initial_candidate.node_id)
if __name__ == "__main__":
num_nodes = 7
initial_candidate_id = 2
simulate_ring_election(num_nodes, initial_candidate_id)In this code, the node with ID 2 initiates the election process, and it becomes the leader by design. This is because the Ring Election Algorithm is designed in such a way that the node that initiates the election also declares itself as the leader if no higher-priority node responds.
Conclusion
Summary:
Election algorithms are used to select a coordinator process from a group of processors. If the coordinator process fails, a new coordinator is elected. The algorithms rely on unique priority numbers assigned to active processes, with the highest-priority process becoming the new coordinator. Two common election algorithms are the Bully Algorithm, suitable for systems where processes can communicate with each other, and the Ring Algorithm, designed for systems organized as a ring with unidirectional communication.
Pros:
- Effective way to ensure continuous coordination in distributed systems.
- Provides a method for recovering from coordinator failures.
- Relatively simple to implement and understand.
Cons:
- May lead to network congestion in large-scale systems, as processes frequently exchange messages.
- Dependency on priority numbers can be problematic if not managed properly.
- The Ring Algorithm has limitations in terms of communication direction, which may not suit all system configurations.
