Distributed Systems - Assignment 6 | Election Algorithms
DISTRIBUTED SYSTEMS
Practical Assignment No. 6
Election Algorithms — Bully & Ring
Name Apeksha Hatle
Roll No. 45017
Assignment No. 6
Subject Distributed Systems
1. Problem Statement
Design and implement simulation programs in Java for the two classic distributed election algorithms
used to select a coordinator (leader) process in a distributed system:
Part A — Bully Algorithm
• Accept n process IDs from the user.
• Accept the ID of the process that initiates the election.
• Simulate the Bully Algorithm: the initiator sends ELECTION messages to all processes with
higher IDs.
• The process with the highest ID among all processes becomes the COORDINATOR.
• Display each ELECTION message sent and announce the final coordinator.
Part B — Ring Algorithm
• Accept n process IDs from the user and arrange them in a logical ring (sorted order).
• Simulate the failure of the current coordinator (highest ID process becomes inactive).
• Accept the index of the process that initiates the election.
• Simulate the Ring Algorithm: election message passes around the ring through all active
processes.
• The process with the maximum ID among active participants becomes the new
COORDINATOR.
2. Theory & Key Concepts
What are Election Algorithms?
In a distributed system, processes may fail at any time — including the coordinator (leader) process.
Election algorithms are used to automatically select a new coordinator from the remaining active
Apeksha Hatle | Roll No. 45017 Page
Distributed Systems - Assignment 6 | Election Algorithms
processes when the current coordinator crashes. The goal is to ensure all active processes agree on a
single new coordinator without any centralized control.
Two fundamental election algorithms are the Bully Algorithm and the Ring Algorithm.
Bully Algorithm
Proposed by Garcia-Molina (1982). Assumes each process has a unique ID and knows all other
process IDs. The process with the highest ID always wins — hence the name 'Bully'.
How it works:
• When a process P notices the coordinator is down, it initiates an election by sending ELECTION
messages to all processes with higher IDs.
• If no higher-ID process responds, P declares itself the coordinator and broadcasts
COORDINATOR messages.
• If a higher-ID process Q receives an ELECTION message, Q takes over and sends ELECTION
messages to processes with IDs higher than Q.
• Eventually, the process with the highest ID wins and announces itself as coordinator.
Key characteristics:
• Simple and straightforward — the highest ID always wins.
• Works in point-to-point message-passing systems.
• Number of messages: O(n²) in the worst case.
• Fast when the highest-ID process is alive — it wins immediately.
Ring Algorithm
In the Ring Algorithm, all processes are logically arranged in a ring. Each process knows its successor
(the next process in the ring). Communication only happens between neighbours.
How it works:
• When a process detects coordinator failure, it sends an ELECTION message containing its own
ID to its successor.
• Each active process receiving the message appends/compares its own ID and forwards the
message to its successor.
• When the message travels the entire ring and returns to the initiator, the maximum ID in the
message is the new coordinator.
• The initiator broadcasts a COORDINATOR message with the winner's ID around the ring.
Key characteristics:
• Requires only 2n messages in the best case (n for election, n for coordinator announcement).
• More message-efficient than the Bully algorithm.
• Processes only communicate with their immediate successor — simpler communication pattern.
• Works well when process IDs are not globally known.
Apeksha Hatle | Roll No. 45017 Page
Distributed Systems - Assignment 6 | Election Algorithms
Comparison: Bully vs Ring
Feature Bully Algorithm Ring Algorithm
Message Pattern Broadcast to higher IDs Ring (neighbour-only)
Messages Required O(n²) worst case O(2n)
Knowledge Required All process IDs known Only successor known
Winner Always highest ID Highest ID among active
Speed Fast if highest alive Fixed — full ring traversal
Fault Tolerance Handles multiple failures Handles failures in ring
Communication Point-to-point Ring topology
3. Algorithm
Bully Algorithm
1. Input: number of processes n, their IDs, and the initiator process ID.
2. Set coordinator = initiator (initially assume the initiator wins).
3. For each process in the array: if process ID > coordinator, print ELECTION message from
initiator to that process, update coordinator = process ID.
4. After scanning all processes, print: 'Process [coordinator] becomes COORDINATOR'.
Ring Algorithm
5. Input: number of processes n and their IDs. Store in Process objects with id and active fields.
6. Sort processes by ID to form the logical ring.
7. Mark the last process (highest ID) as inactive to simulate coordinator failure.
8. Input: index of the initiator process.
9. Starting from the initiator, traverse the ring using (i + 1) % n.
10. If the current process is active, print election message and add its ID to the list.
11. Continue until the ring returns to the initiator (i == init).
12. Find the maximum ID in the list — that process is the new COORDINATOR.
13. Print the coordinator announcement.
4. Complete Source Code
[Link]
import [Link].*;
class Bully {
public static void main(String args[]) {
Apeksha Hatle | Roll No. 45017 Page
Distributed Systems - Assignment 6 | Election Algorithms
Scanner sc = new Scanner([Link]);
[Link]("Enter number of processes: ");
int n = [Link]();
int processes[] = new int[n];
for (int i = 0; i < n; i++) {
[Link]("Enter Process ID: ");
processes[i] = [Link]();
}
[Link]("Enter process initiating election: ");
int initiator = [Link]();
int coordinator = initiator;
[Link]("\nElection started...");
for (int i = 0; i < n; i++) {
if (processes[i] > coordinator) {
[Link](
"Process " + initiator +
" sends ELECTION message to process " +
processes[i]);
coordinator = processes[i];
}
}
[Link]("\nProcess " + coordinator + " becomes COORDINATOR");
}
}
[Link]
import [Link].*;
class Process {
int id;
boolean active;
Process(int id) {
[Link] = id;
active = true;
}
}
class Ring {
public static void main(String args[]) {
Scanner sc = new Scanner([Link]);
[Link]("Enter number of processes: ");
int n = [Link]();
Process p[] = new Process[n];
for (int i = 0; i < n; i++) {
[Link]("Enter Process ID: ");
int id = [Link]();
p[i] = new Process(id);
}
// Sort to form logical ring
[Link](p, [Link](a -> [Link]));
Apeksha Hatle | Roll No. 45017 Page
Distributed Systems - Assignment 6 | Election Algorithms
// Simulate coordinator failure (highest ID process goes down)
p[n - 1].active = false;
int ch;
do {
[Link]("\n1. Election");
[Link]("2. Exit");
[Link]("Enter choice: ");
ch = [Link]();
switch (ch) {
case 1:
[Link]("Enter initiator process index: ");
int init = [Link]();
List<Integer> list = new ArrayList<>();
int i = init;
do {
if (p[i].active) {
[Link]("Process " + p[i].id + " passes election
message");
[Link](p[i].id);
}
i = (i + 1) % n;
} while (i != init);
int leader = [Link](list);
[Link]("\nProcess " + leader + " becomes COORDINATOR");
break;
case 2:
[Link]("Exiting...");
break;
default:
[Link]("Invalid choice");
}
} while (ch != 2);
}
}
5. Steps to Compile and Run
Compile
javac [Link]
javac [Link]
Run Bully Algorithm
java Bully
Enter number of processes: 5
Enter Process ID: 1
Enter Process ID: 2
Enter Process ID: 3
Enter Process ID: 4
Enter Process ID: 5
Apeksha Hatle | Roll No. 45017 Page
Distributed Systems - Assignment 6 | Election Algorithms
Enter process initiating election: 2
Election started...
Process 2 sends ELECTION message to process 3
Process 2 sends ELECTION message to process 4
Process 2 sends ELECTION message to process 5
Process 5 becomes COORDINATOR
Run Ring Algorithm
java Ring
Enter number of processes: 5
Enter Process ID: 1
Enter Process ID: 2
Enter Process ID: 3
Enter Process ID: 4
Enter Process ID: 5
1. Election
2. Exit
Enter choice: 1
Enter initiator process index: 2
Process 3 passes election message
Process 4 passes election message
Process 1 passes election message
Process 2 passes election message
Process 4 becomes COORDINATOR
6. Writeup Points (For Practical Journal)
Write the following points in your practical journal:
• Election algorithms are used in distributed systems to select a new coordinator when the current
one fails, without any central authority.
• The Bully Algorithm selects the process with the highest process ID as the coordinator. It is
called 'Bully' because a higher-ID process always 'bullies' lower ones into submission.
• In the Bully Algorithm, the initiating process sends ELECTION messages to all processes with
higher IDs. The process with the highest ID wins and announces itself as COORDINATOR.
• The Ring Algorithm arranges processes in a logical ring. Election messages travel around the
ring, and the process with the highest ID among active participants becomes the coordinator.
• In the Ring Algorithm, only active processes forward the election message. Inactive (failed)
processes are skipped during ring traversal.
• In this simulation, the process with the highest ID is marked inactive to simulate a coordinator
failure, triggering the election.
• The Ring Algorithm uses approximately 2n messages (n for election round, n for coordinator
announcement), making it more message-efficient than the Bully Algorithm.
• The Bully Algorithm may require O(n²) messages in the worst case since every process may
need to send messages to all higher-ID processes.
Apeksha Hatle | Roll No. 45017 Page
Distributed Systems - Assignment 6 | Election Algorithms
• [Link]() with a custom comparator is used to sort Process objects by ID to form the logical
ring.
• [Link]() is used to find the maximum process ID among the active processes that
participated in the election ring.
• The modulo operator (i + 1) % n ensures circular traversal of the ring — after the last process, it
wraps back to index 0.
• Both algorithms guarantee that exactly one coordinator is elected, and all active processes
eventually know who the coordinator is.
7. Viva / Oral Explanation Points
Be ready to explain the following questions:
Q1. What is an election algorithm in distributed systems?
An election algorithm is a distributed algorithm used to select one process from a group of active
processes to act as the coordinator or leader. It is triggered when the current coordinator fails. The goal
is that all surviving processes agree on a single new coordinator without any central control.
Q2. Why do we need election algorithms?
In distributed systems, there is often one special process (coordinator) responsible for critical tasks like
managing shared resources, synchronizing clocks, or handling locks. When this coordinator crashes,
the system needs a reliable, automatic way to choose a new one — that's what election algorithms
provide.
Q3. Explain the Bully Algorithm step by step.
When process P detects coordinator failure: (1) P sends ELECTION messages to all processes with
higher IDs. (2) If no higher process responds, P declares itself coordinator and broadcasts
COORDINATOR messages. (3) If a higher-ID process Q receives the ELECTION message, Q takes
over and repeats the process. (4) The process with the highest ID always wins — it bullies everyone
else.
Q4. Why is it called the 'Bully' Algorithm?
It is called the Bully Algorithm because the process with the highest ID always wins the election
regardless of who initiates it. A higher-ID process always overrules (bullies) lower-ID processes, similar
to how a bully dominates others in a group.
Q5. Explain the Ring Algorithm step by step.
Processes are arranged in a logical ring. When P detects coordinator failure: (1) P sends an
ELECTION message with its own ID to its successor. (2) Each active process receiving the message
forwards it to its successor, and records the highest ID seen. (3) When the message completes the full
ring and returns to P, the maximum ID in the message is the new coordinator. (4) P broadcasts a
COORDINATOR message with the winner's ID.
Q6. What is the role of the 'active' flag in the Ring Algorithm?
Apeksha Hatle | Roll No. 45017 Page
Distributed Systems - Assignment 6 | Election Algorithms
The 'active' flag indicates whether a process is alive. In this simulation, the process with the highest ID
has active=false to simulate a coordinator crash. During ring traversal, inactive processes are skipped
— only active processes pass the election message. This ensures failed processes don't interfere with
the election.
Q7. How is the ring formed in the implementation?
The processes are sorted by their IDs using [Link]() with a Comparator. This sorted order
represents the logical ring. Traversal uses the modulo operation (i+1)%n to wrap around from the last
process back to the first, forming a circular ring.
Q8. What is the message complexity of both algorithms?
Bully Algorithm: O(n²) in the worst case — every process may send messages to all higher-ID
processes. Ring Algorithm: O(2n) — approximately n messages for the election round (around the ring)
and n more for the coordinator announcement, making it more efficient.
Q9. What happens if two processes start an election simultaneously in the Bully Algorithm?
Both processes send ELECTION messages to higher-ID processes. Since the highest-ID process
always wins, both initiations converge to the same winner. The process with the highest ID will
eventually announce itself as coordinator, so the two concurrent elections don't cause inconsistency.
Q10. What are the limitations of these election algorithms?
Bully Algorithm limitations: requires knowledge of all process IDs; high message overhead O(n²); if a
new high-ID process joins during election it restarts it. Ring Algorithm limitations: message must travel
the entire ring even if winner is adjacent; if multiple failures occur, ring may be broken and require
repair mechanisms.
8. Conclusion
In this assignment, we successfully implemented and simulated two classic election algorithms used in
distributed systems. The Bully Algorithm selects the coordinator by having the initiator send election
messages to all higher-ID processes; the highest-ID process always wins. The Ring Algorithm arranges
processes in a logical ring, passes the election message around, and elects the highest active process.
Both implementations correctly detect coordinator failure, simulate the election process, and announce
the new coordinator. This demonstrates how distributed systems can autonomously recover from
process failures through structured coordination protocols without requiring a central authority.
Apeksha Hatle | Roll No. 45017 Page