BTech - CSE [ 2022 - 23 ]
Distributed Computing Lab
Assignment - 5
Title : Election Algorithms
Aim : To study and implement the following :-
1. Ring Algorithm
2. Bully AlgorithmElection Algorithms
1
7/18/2022
Election Algorithms
2
7/18/2022
Why elect a coordinator process ?
3
7/18/2022
Types of messages
There are basically 3 types of messages :
1. An election message to initiate the election
2. A reply/response message given in response to the
election message
3. A coordinator message sent to inform other processes,
the id of the coordinator process.
4
7/18/2022
Election Algorithm : Assumptions/Requirements
1. Any process can call for an election.
2. A process can call for at most one election at a time.
3. Multiple processes can call an election simultaneously.
4. The result of an election should not depend on which process calls for it.
5.Each process has
Variable called elected
An attribute value called attr, e.g., id, MAC address, CPU
6.The non-faulty process with the best (highest) election attribute value (e.g., highest id or address, or fastest cpu, etc.) is elected.
7. Requirement: A run (execution) of the election algorithm must always guarantee at the end: a) safety and b) liveliness [ non-faulty process]
5
7/18/2022
Ring algorithm
1.N Processes are organized in a logical ring.
pi has a communication channel to p(i+1) mod N.
All messages are sent clockwise around the ring.
2.Any process pi that discovers a coordinator has failed initiates an “election” message <i, pi.attr>
3.When a process pj receives an election message <i, pi.attr>, it compares the attr in the message with its own.
If the arrived pi.attr > pj.attr , then receiver pj forwards the message <i, pi.attr>.
If the arrived pi.attr < pj.attr and the receiver pj has not forwarded an election message earlier, it substitutes its own <j, pj.attr> in the message and forwards it.
If the arrived pi.attr = pj.attr , then this process’s pj .attr must be the greatest, and it becomes the new coordinator. This process then sends an “elected” message to its neighbor announcing the election result.
4.When a process pi receives an elected message, it
sets its variable electedi 🡨 id of the message.
forwards the message if it is not the new coordinator.
A participant participates in election and becomes non participant when election is over and elected message reaches it
6
7/18/2022
7
24
15
9
4
33
28
17
24
1
Note: The election was started by process 17.�The highest process identifier encountered so far is 24.
(final leader will be 33)�
Ring of N processes
Ring Algorithm : Progress
Lecture 7- 7
Ring Algorithm : Time Complexity
8
7/18/2022
(attr:=id)
1.The worst-case scenario occurs when the counter-clockwise neighbor has the highest attr/id
2. A total of N-1 messages is required to reach the new coordinator-to-be.
3.Another N messages are required until the new coordinator-to-be ensures it is the new coordinator.
4.Another N messages are required to circulate the elected messages.
worst case : 3N-1
best : 2N
assume : one process began election
ALTERNATIVELY :-
In ring algorithm, on the contrary, irrespective of which process detects the failure of coordinator and initiates an election, an election always requires 2(n-1) messages. (n-1) messages needed for one round rotation of the ELECTION message, and another (n-1) messages for the COORDINATOR message.
1.Processes are organized in a logical ring.
2.Any process that discovers the coordinator (leader) has failed initiates an “election” message. This is the initiator of the election.
3.The message is circulated around the ring, bypassing failed nodes.
4.Each node adds (appends) its id:attr to the message as it passes it to the next node.
5.Once the message gets to the initiator, it elects the node with the best election attribute value.
6.It then sends a “coordinator” message with the id of the newly-elected coordinator. Again, each node adds (appends) its id to the end of the message.
Once “coordinator” message gets back to initiator,
election is over if “coordinator” is in id-list.
else the algorithm is repeated (handles election failure).
Modified Ring Algorithm
Lecture 7- 9
1.A node initiates election by sending an “election” message to only nodes that have a higher id than itself.
If no answer, announce itself to lower nodes as coordinator.
if any answer, then there is some higher node active; wait for coordinator message. If none received after time out, start a new election.
2.A node that receives an “election” message replies with answer, & starts an election – unless it has already.
3. When a process finds the coordinator has failed, if it knows its id is the highest, it elects itself as coordinator, then sends a coordinator message to all processes with lower identifiers.
Bully Algorithm
Lecture 7- 10
Bully Algorithm : Progress
1.P sends an ELECTION message to all processes with higher numbers.
2.If no one responds, P wins the election and becomes coordinator.
3.If one of the higher-ups answers, it takes over. P’s job is done.
11
7/18/2022
The Bully Algorithm (1)
Figure 6-20. The bully election algorithm. (a) Process 4 holds an
election. (b) Processes 5 and 6 respond, telling 4 to stop.
(c) Now 5 and 6 each hold an election.
12
7/18/2022
The Bully Algorithm (2)
Figure 6-20. The bully election algorithm. (d) Process 6 tells 5 to stop. (e) Process 6 wins and tells everyone.
13
7/18/2022
Bully Algorithm : Time Complexity
14
7/18/2022