CLICK HERE TO DOWNLOAD PPT ON Election Algorithms and Distributed Processing
Election Algorithms and Distributed Processing Presentation Transcript
1.Election Algorithms and Distributed Processing
2.Outline
Election algorithms – introduction
Traditional election algorithms
Bully algorithm
Ring algorithm
Wireless election algorithms
3.Need for a Coordinator
Many algorithms used in distributed systems require a coordinator
For example, see the centralized mutual exclusion algorithm.
In general, all processes in the distributed system are equally suitable for the role
Election algorithms are designed to choose a coordinator.
Election algorithms – introduction
Traditional election algorithms
Bully algorithm
Ring algorithm
Wireless election algorithms
3.Need for a Coordinator
Many algorithms used in distributed systems require a coordinator
For example, see the centralized mutual exclusion algorithm.
In general, all processes in the distributed system are equally suitable for the role
Election algorithms are designed to choose a coordinator.
4.Election Algorithms
Any process can serve as coordinator
Any process can “call an election” (initiate the algorithm to choose a new coordinator).
There is no harm (other than extra message traffic) in having multiple concurrent elections.
Elections may be needed when the system is initialized, or if the coordinator crashes or retires.
Any process can serve as coordinator
Any process can “call an election” (initiate the algorithm to choose a new coordinator).
There is no harm (other than extra message traffic) in having multiple concurrent elections.
Elections may be needed when the system is initialized, or if the coordinator crashes or retires.
5.Assumptions
Every process/site has a unique ID; e.g.
the network address
a process number
Every process in the system should know the values in the set of ID numbers, although not which processors are up or down.
The process with the highest ID number will be the new coordinator.
Process groups (as with ISIS toolkit or MPI) satisfy these requirements.
Every process/site has a unique ID; e.g.
the network address
a process number
Every process in the system should know the values in the set of ID numbers, although not which processors are up or down.
The process with the highest ID number will be the new coordinator.
Process groups (as with ISIS toolkit or MPI) satisfy these requirements.
6. Requirements
When the election algorithm terminates a single process has been selected and every process knows its identity.
Formalize: every process pi has a variable ei to hold the coordinator’s process number.
When the election algorithm terminates a single process has been selected and every process knows its identity.
Formalize: every process pi has a variable ei to hold the coordinator’s process number.
7.The Bully Algorithm - Overview
Process p calls an election when it notices that the coordinator is no longer responding.
High-numbered processes “bully” low-numbered processes out of the election, until only one process remains.
When a crashed process reboots, it holds an election. If it is now the highest-numbered live process, it will win.
Process p calls an election when it notices that the coordinator is no longer responding.
High-numbered processes “bully” low-numbered processes out of the election, until only one process remains.
When a crashed process reboots, it holds an election. If it is now the highest-numbered live process, it will win.
8.Process p sends an election message to all higher-numbered processes in the system. If no process responds, then p becomes the coordinator. If a higher-level process (q) responds, it sends p a message that terminates p’s role in the algorithm
9.The process q now calls an election (if it has not already done so).
Repeat until no higher-level process responds. The last process to call an election “wins” the election.
The winner sends a message to other processes announcing itself as the new coordinator.
Repeat until no higher-level process responds. The last process to call an election “wins” the election.
The winner sends a message to other processes announcing itself as the new coordinator.
10.Analysis
Works best if communication in the system has bounded latency so processes can determine that a process has failed by knowing the upper bound (UB) on message transmission time (T) and message processing time (M).
Works best if communication in the system has bounded latency so processes can determine that a process has failed by knowing the upper bound (UB) on message transmission time (T) and message processing time (M).
11.A Ring Algorithm - Overview
The ring algorithm assumes that the processes are arranged in a logical ring and each process is knows the order of the ring of processes.
Processes are able to “skip” faulty systems: instead of sending to process j, send to j + 1.
Faulty systems are those that don’t respond in a fixed amount of time.
The ring algorithm assumes that the processes are arranged in a logical ring and each process is knows the order of the ring of processes.
Processes are able to “skip” faulty systems: instead of sending to process j, send to j + 1.
Faulty systems are those that don’t respond in a fixed amount of time.
12.A Ring Algorithm
P thinks the coordinator has crashed; builds an ELECTION message which contains its own ID number.
Sends to first live successor
Each process adds its own number and forwards to next.
OK to have two elections at once.
P thinks the coordinator has crashed; builds an ELECTION message which contains its own ID number.
Sends to first live successor
Each process adds its own number and forwards to next.
OK to have two elections at once.
13.Ring Algorithm - Details
14.Elections in Wireless Environments
Traditional algorithms aren’t appropriate.
Can’t assume reliable message passing or stable network configuration
This discussion focuses on ad hoc wireless networks but ignores node mobility.
Nodes connect directly, no common access point, connection is short term
Often used in multiplayer gaming, on-the-fly file transfers, etc.
Traditional algorithms aren’t appropriate.
Can’t assume reliable message passing or stable network configuration
This discussion focuses on ad hoc wireless networks but ignores node mobility.
Nodes connect directly, no common access point, connection is short term
Often used in multiplayer gaming, on-the-fly file transfers, etc.
15.Assumptions
Wireless algorithms try to find the best node to be coordinator; traditional algorithms are satisfied with any node.
Any node (the source) can initiate an election by sending an ELECTION message to its neighbors – nodes within range.
When a node receives its first ELECTION message the sender becomes its parent node.
Wireless algorithms try to find the best node to be coordinator; traditional algorithms are satisfied with any node.
Any node (the source) can initiate an election by sending an ELECTION message to its neighbors – nodes within range.
When a node receives its first ELECTION message the sender becomes its parent node.
16.Wireless Elections
At each stage the “most eligible” or “best” node will be passed along from child to parent.
Once the source node has received all the replies, it is in a position to choose the new coordinator.
When the selection is made, it is broadcast to all nodes in the network.
At each stage the “most eligible” or “best” node will be passed along from child to parent.
Once the source node has received all the replies, it is in a position to choose the new coordinator.
When the selection is made, it is broadcast to all nodes in the network.
17.Chapter 6 - Summary
“Synchronization is … doing the right thing at the right time.”
Synchronization in distributed systems is related to communication.
Complicated by lack of global clock, shared memory.
Logical clocks support global event order.
Distributed mutex: important class of synchronization algorithms.
Leader election algorithms are sometimes needed.
“Synchronization is … doing the right thing at the right time.”
Synchronization in distributed systems is related to communication.
Complicated by lack of global clock, shared memory.
Logical clocks support global event order.
Distributed mutex: important class of synchronization algorithms.
Leader election algorithms are sometimes needed.
Posts
0 comments