CLICK HERE TO DOWNLOAD PPT ON ELECTION ALGORITHMS
ELECTION ALGORITHMS Presentation Transcript
1.ELECTION ALGORITHMS
2.ELECTIONS
There are at least two basic strategies by which a distributed system can adapt to failures.
operate continuously as failures occur and are repaired
The second alternative is to temporarily halt normal operation and to take some time out to reorganize the system.
The reorganization of the system is managed by a single node called the coordinator.
So as a first step in any reorganization, the operating or active nodes must elect a coordinator.
3.ELECTION AND SYNCHRONIZATION
Similar
Like Synchronization, all processors must come to an agreement about who enters the critical region (i.e. who is the leader)
Different
The election protocol must properly deal with the case of a coordinator failing. On the other hand, mutual exclusion algorithms assume that the process in the critical region (i.e., the coordinator) will not fail.
A new coordinator must inform all active nodes that it is the coordinator. In a mutual exclusion algorithm, the nodes not in the critical region have no need to know what node is in the region.
There are at least two basic strategies by which a distributed system can adapt to failures.
operate continuously as failures occur and are repaired
The second alternative is to temporarily halt normal operation and to take some time out to reorganize the system.
The reorganization of the system is managed by a single node called the coordinator.
So as a first step in any reorganization, the operating or active nodes must elect a coordinator.
3.ELECTION AND SYNCHRONIZATION
Similar
Like Synchronization, all processors must come to an agreement about who enters the critical region (i.e. who is the leader)
Different
The election protocol must properly deal with the case of a coordinator failing. On the other hand, mutual exclusion algorithms assume that the process in the critical region (i.e., the coordinator) will not fail.
A new coordinator must inform all active nodes that it is the coordinator. In a mutual exclusion algorithm, the nodes not in the critical region have no need to know what node is in the region.
4.ELECTION ALGORITHMS
The two classical election algorithms by Garcia-Molina
Bully Algorithm
Invitation Algorithm
Ring Algorithm
The two classical election algorithms by Garcia-Molina
Bully Algorithm
Invitation Algorithm
Ring Algorithm
5.The Bully Algorithm
Assumptions
Each node has access to some permanent storage that survives node failures.
There are no transmission errors.
The communication subsystem does not fail
Assumptions
Each node has access to some permanent storage that survives node failures.
There are no transmission errors.
The communication subsystem does not fail
6.The Bully Algorithm
State Information For Election
Status
Down,Election,Reorganization,Normal
Co-ordinator
The Current co-ordinator of the node
Definition
The State Information of the task being performed - the application algorithms, list of the participating nodes
State Information For Election
Status
Down,Election,Reorganization,Normal
Co-ordinator
The Current co-ordinator of the node
Definition
The State Information of the task being performed - the application algorithms, list of the participating nodes
7.The Bully Algorithm
Each process has an associated priority (weight). The process with the highest priority should always be elected as the coordinator.
How do we find the heaviest process?
Any process can just start an election by sending an election message to all other processes
If a process Pheavy receives an election message from a lighter process Plight, it sends a take-over message to Plight. Plight is out of the race.
If a process doesn’t get a take-over message back, it wins, and sends a victory message to all other processes.
8.The Bully Algorithm
Each process has an associated priority (weight). The process with the highest priority should always be elected as the coordinator.
How do we find the heaviest process?
Any process can just start an election by sending an election message to all other processes
If a process Pheavy receives an election message from a lighter process Plight, it sends a take-over message to Plight. Plight is out of the race.
If a process doesn’t get a take-over message back, it wins, and sends a victory message to all other processes.
8.The Bully Algorithm
9.Process 6 tells 5 to stop
Process 6 wins and tells everyone
Process 6 wins and tells everyone
10.Bully Algorithm: Properties
Assume n processes initially
Worst Case:
Smallest process initiates election
Requires O(n2) messages
Best Case:
Eventual leader initiates election
Requires (n-1) messages
Assume n processes initially
Worst Case:
Smallest process initiates election
Requires O(n2) messages
Best Case:
Eventual leader initiates election
Requires (n-1) messages
11.The Invitation Algorithm
Bullying algorithm fails for asynchronous systems
The invitation algorithm classifies nodes into ‘groups’ and elects a co-ordinator for every group
An additional state variable is indroduced for this asynchronous election
Group Number
Identifier of the group the processor belongs to
Bullying algorithm fails for asynchronous systems
The invitation algorithm classifies nodes into ‘groups’ and elects a co-ordinator for every group
An additional state variable is indroduced for this asynchronous election
Group Number
Identifier of the group the processor belongs to
12.The Invitation Algorithm
When Processor p wishes to establish itself as the new co-ordinator , it sends out invitations to the potential participants
Groups that can communicate try to coalesce into larger groups
Periodically the group co-ordinator searches for other groups
When Processor p wishes to establish itself as the new co-ordinator , it sends out invitations to the potential participants
Groups that can communicate try to coalesce into larger groups
Periodically the group co-ordinator searches for other groups
13.Starting a new Group
If a node does not hear from its co-ordinator for a long time, the node declares its own group
It could start sending invitations to all the other participants of the old group
If a node does not hear from its co-ordinator for a long time, the node declares its own group
It could start sending invitations to all the other participants of the old group
14.A Comparison of the two Algorithms
Logical Structure
Bully –
Simple and Efficient because it imposes a logical structure on processors
Invitation –
Might take a long time for groups to merge because of no strongly defined structure
Logical Structure
Bully –
Simple and Efficient because it imposes a logical structure on processors
Invitation –
Might take a long time for groups to merge because of no strongly defined structure
15.A Comparison of the two Algorithms
Synchronous Vs Asynchronous
Bully
Makes very strong use of bounded response time which are mostly unrealistic
Invitation
Works correctly in the presence of timing failures
16.Election in a Ring
Process priority is obtained by organizing processes into a (logical) ring. Process with the highest priority should be elected as coordinator.
Each process has a successor
Initiation:
A process sends an ELECTION message to its successor (or next alive process) with its ID
Each process adds its own ID and forwards the ELECTION message
Leader Election:
Message comes back to initiator
Initiator announces the winner by sending another message around the ring
Synchronous Vs Asynchronous
Bully
Makes very strong use of bounded response time which are mostly unrealistic
Invitation
Works correctly in the presence of timing failures
16.Election in a Ring
Process priority is obtained by organizing processes into a (logical) ring. Process with the highest priority should be elected as coordinator.
Each process has a successor
Initiation:
A process sends an ELECTION message to its successor (or next alive process) with its ID
Each process adds its own ID and forwards the ELECTION message
Leader Election:
Message comes back to initiator
Initiator announces the winner by sending another message around the ring
17.Ring Algorithm: Initiation
18.Ring Algorithm - Election
19.Ring Algorithm: Properties
If only 1 process initiates election:
Requires 2n messages
Two or more processes might simultaneously initiate elections
Still ensures election of the same leader
Results in extra messages
If only 1 process initiates election:
Requires 2n messages
Two or more processes might simultaneously initiate elections
Still ensures election of the same leader
Results in extra messages
20.REFERENCES
Posts
0 comments