Scribd
Upload
10 views15 pages

Bully and Ring Election Algorithms

The document outlines election algorithms used to select a coordinator in distributed systems, specifically the Bully and Ring algorithms. The Bully algorithm involves processes with unique IDs where the highest ID process initiates an election if it detects a failure, while the Ring algorithm organizes processes in a logical ring and sequentially polls neighbors to find the highest ID. Both algorithms ensure a new coordinator is elected when the current one fails, with the Bully algorithm requiring O(n^2) messages in worst-case scenarios.

Uploaded by

sajibuddin163
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
10 views15 pages

Bully and Ring Election Algorithms

The document outlines election algorithms used to select a coordinator in distributed systems, specifically the Bully and Ring algorithms. The Bully algorithm involves processes with unique IDs where the highest ID process initiates an election if it detects a failure, while the Ring algorithm organizes processes in a logical ring and sequentially polls neighbors to find the highest ID. Both algorithms ensure a new coordinator is elected when the current one fails, with the Bully algorithm requiring O(n^2) messages in worst-case scenarios.

Uploaded by

sajibuddin163
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Election Algorithm

Election Algorithm
• Need one process to act as a coordinator.
• Technique to pick a unique coordinator (a leader node).
• Take over the role of a failed process.
• Pick a master in Berkely clock synchronization.
• Types of Election algorithm: I. Bully algorithm; II. Ring algorithm.
Bully algorithm
• Each process has a unique numerical ID.
• Process know the IDs and address of every other process.
• Communication is assumed reliable.
• Key idea: select process with the highest ID.
• Process initiate election if it just recover from failure or if coordinator
failed.
• Several process can initiate an election simultaneously.
• O(n^2) message required with n process.
Algorithm (suppose Process P send a message to
the coordinator)
• It will assume that the coordinator process is failed
when it doesn't receive any response from the
coordinator within the time interval T.
• An election message will be sent to all the active
processes by process P along with the highest priority
number.
• If it will not receive any response within the time
interval T, the current process P elects itself as a
coordinator.
• After selecting itself as a coordinator, it again sends a
message that process P is elected as their new
coordinator to all the processes having lower priority.
If process P will receive any response from another
process Q within time T:
[Link] again waits for time T to receive another response, i.e., it
has been elected as coordinator from process Q.
[Link] it doesn't receive any response within time T, it is assumed
to have failed, and the algorithm is restarted.
Bully Election Algorithm Example

We start with 6 processes,


all directly connected to each other.
Process 6 is the leader,
as it has the highest number.
Process 6 fails.
Process 3 notices that Process 6 does not respond
So it starts an election, notifying those processes
with ids greater than 3.
Both Process 4 and Process 5 respond,
telling Process 3 that they'll take over from here.
Process 4 sends election messages
to both Process 5 and Process 6.
Only Process 5 answers
and takes over the election.
Process 5 sends out only one election message
to Process 6.
When Process 6 does not respond
Process 5 declares itself the winner.
Ring algorithm
• Processes have unique Ids and arranged in a logical ring
• Each process knows its neighbors
• Select process with highest ID
• Begin election if just recovered or coordinator has failed
• Send Election to closest downstream node that is alive
• Sequentially poll each successor until a live node is found
• Each process tags its ID on the message
• Initiator picks node with highest ID and sends a coordinator message
• Multiple elections can be in progress
• Wastes network bandwidth but does no harm
Example

You might also like