Leader Election Algorithm

A Leader Election Algorithm is a distributed algorithm used in networked systems to select a single
process (leader) among multiple distributed processes. The leader is responsible for coordination,
decision-making, and resource allocation in a distributed system.

Need for Leader Election Algorithm: In distributed systems, there is no central authority, so
leader election ensures:

 Coordination among processes.

 Avoidance of conflicts (e.g., multiple processes trying to access the same resource).

 Efficient task distribution and fault tolerance.

How Does It Work?

1. Processes communicate to decide who should be the leader.

2. Election Criteria: The leader is chosen based on factors like process ID, computational
power, or priority.

3. Election Messages: Processes send election messages to claim leadership.

4. Winner Announcement: The selected leader informs others.

Types of Leader Election Algorithms:

1. Bully Algorithm:

o The highest-ID process becomes the leader.

o If the leader crashes, a new leader is elected.

2. Ring Algorithm:

o Processes are arranged in a logical ring.

o A token circulates, and the process with the highest ID wins.

3. Randomized Leader Election:

o Uses randomization to pick a leader fairly.

Real-World Applications:

 Cloud Computing: Ensuring fault-tolerant leader selection in distributed cloud systems.

 Blockchain Networks: Electing a leader for transaction validation.

 Sensor Networks: Selecting a master node for data collection.

Types:

1. Bully Algorithm : The Bully Algorithm is a leader election algorithm used in distributed
systems where the process with the highest ID becomes the leader. When a leader fails, a
new election is initiated by any process that detects the failure. It sends election messages
to all higher-ID processes, and if no higher process responds, it declares itself the new
leader.

Steps:

1. A process detects that the leader has failed.

2. It sends ELECTION messages to all higher-ID processes.

3. If no higher process responds, it becomes the leader.

4. If a higher process responds, that process starts its own election.

5. The highest remaining process broadcasts a COORDINATOR message to inform others.

Bully Algorithm Example with 6 Processes (Failure Scenario)

Let's assume six processes in a distributed system, each having a unique ID (1 to 6). The highest
ID process is always the leader.

Initial Setup

Process ID Status Notes

P1 Alive Lowest ID
Process ID Status Notes

P2 Alive -

P3 Alive -

P4 Alive -

P5 Alive -

P6 Leader (Fails) Highest ID (Crashes)

Step-by-Step Execution

1⃣ P6 (Leader) Fails:

 The remaining processes detect that P6 is unresponsive.

2⃣ P3 Starts an Election:

 P3 realizes P6 is down.

 P3 sends Election Messages to P4, P5, and P6.

3⃣ P4 and P5 Respond:

 P4 and P5 (higher ID than P3) respond, meaning they take over the election.

 P5 initiates another election (since P6 is down, P5 is the next highest).

4⃣ P5 Becomes the New Leader:

 P5 sends messages to P6 (no response).

 Since no higher process responds, P5 declares itself the leader.

 P5 broadcasts "I am the new leader" to all remaining processes.

Final State
Process ID Status Notes

P1 Alive -

P2 Alive -

P3 Alive Initiated Election

P4 Alive Participated in Election

P5 New Leader Highest Available ID

P6 Failed No Response

Important points:

 If a leader fails, the next highest ID process takes charge.

 If multiple processes detect failure, the lowest ID among them starts the election.
 Only the highest available process wins the election and becomes the new leader.

Real-Life Example of the Bully Algorithm

Imagine a group of employees in an office deciding on a team leader when their manager is
suddenly unavailable. The person with the highest experience (ID) should take over.

Scenario: Choosing a Temporary Team Leader in an Office

Participants:

 Alice (ID 1) – Junior employee

 Bob (ID 2) – Mid-level employee

 Charlie (ID 3) – Senior employee

 David (ID 4) – Team lead (Current leader)

 Emma (ID 5) – Manager (Fails/Leaves)

What Happens?

1. Manager Emma (ID 5) is absent (Failure detected).

2. Charlie (ID 3) notices and starts an election.

3. Charlie asks higher-ranked employees (David, Emma) if they want to lead.

4. David (ID 4) responds:

o David takes over the election since he's higher.

o He asks Emma (ID 5) if she wants to lead.

o Emma doesn’t respond (failed).

5. David becomes the new leader and informs everyone:

o Bob, Charlie, and Alice acknowledge him.

Important points:

 Higher-ranked individuals (higher IDs) always get leadership if available.

 Lower-ranked individuals initiate elections if a leader is missing.
 Only the highest available person takes charge.

This is exactly how the Bully Algorithm works in distributed systems but applied in a real-life
office scenario.

2. Ring Algorithm : The Ring Algorithm is a leader election algorithm where processes are
arranged in a logical ring ring (each process knows its next neighbor). When a leader fails, an
election message is circulated around the ring, collecting process IDs. The process with the
highest ID is elected as the new leader and announces itself to all nodes. A leader (coordinator)
is elected to manage shared resources or coordinate tasks.

Steps:

1. Process Initiation:

o Any process can initiate the election if it detects a failure of the current leader.

2. Message Passing (Election Phase):

o The initiator sends an ELECTION message to the next process in the ring.
 o Each process appends its own ID and forwards it.

3. Leader Selection:

o When the message returns to the initiator, the process with the highest ID is the
new leader.

4. Announcement (Coordinator Phase):

o The leader sends a COORDINATOR message around the ring to inform all
processes.

Example

Consider four processes: P1, P2, P3, P4 (P4 is the highest).

P1 → P2 → P3 → P4 → P1 (ring structure)

 If P1 initiates an election, it sends [1] → P2 → [1,2] → P3 → [1,2,3] → P4 → [1,2,3,4] →

P1.

 Since P4 is the highest, it sends COORDINATOR (P4) message around the ring.

Advantages & Disadvantages

Pros Cons

Simple to implement Message overhead increases with nodes

No central failure point If a process crashes, recovery is needed

2. Raft Algorithm: The Raft Algorithm is a consensus algorithm used in distributed systems to
elect a leader through majority voting. It works by dividing time into terms and using voting
mechanisms. If a follower does not receive heartbeats from the leader, it becomes a candidate
and requests votes. The process that receives a majority of votes becomes the new leader and
maintains control by periodically sending heartbeats. Used in distributed databases (e.g., etcd,
Consul).

Roles in Raft

1. Leader – Handles client requests, replicates logs.

2. Followers – Accepts log entries from the leader.

 3. Candidate – Tries to become a leader via election.

Election Process

1. Term-Based Election:

o A follower becomes a candidate if it doesn’t receive a heartbeat from the leader.

o It starts an election by sending RequestVote RPCs to other nodes.

2. Majority Voting:

o If the candidate gets a majority of votes, it becomes the leader.

3. Leader Announcing:

o The new leader sends heartbeats to confirm leadership.

Example

Consider 5 nodes (N1, N2, N3, N4, N5), and N3 crashes.

 N1 & N2 detect no heartbeats → They start an election.

 N1 gets votes from N2, N4, and N5 (majority).

 N1 becomes the new leader and starts sending heartbeats.

Advantages & Disadvantages

Pros Cons

Faster than Ring Algorithm Slightly complex implementation

Handles leader failures efficiently Requires majority availability

Comparison: Ring vs. Raft

Feature Ring Algorithm Raft Algorithm

Structure Logical ring Distributed cluster

Leader Selection Highest ID Majority voting

Failure Handling Message delay Automatic failover

 Use Cases Small-scale systems Large distributed systems

Comparison Table: Bully vs. Ring vs. Raft

Feature Bully Algorithm Ring Algorithm Raft Algorithm

Election Basis Highest ID Highest ID Majority Voting

Topology Fully connected Logical Ring Distributed Cluster

Message O(n²) (High) O(n) (Moderate) O(n) (Moderate)

Complexity

Failure Handling Needs re-election if highest Needs re-election if Automatic re-

process fails ring breaks election

Speed Fastest Slow Fast (but needs

votes)

Use Cases Centralized systems Token-based systems Distributed

systems, cloud

Important Points:

 Use Bully Algorithm if you need fast elections and have a fully connected network.
 Use Ring Algorithm if you have a ring topology and need simple election handling.
 Use Raft Algorithm in large-scale distributed systems where fault tolerance and
automatic failover are needed (e.g., databases like etcd, Consul).