16-05-2012, 03:14 PM
Distributed Algorithms – 2g1513
leader election3.ppt (Size: 1.09 MB / Downloads: 63)
Election Algorithms
Gerard LeLann posed the Election problem in a famous paper 1977
Many distributed systems are client server based, with one server/coordinator (leader), and multiple clients
What happens if the leader fails?
Elect a new one
Who to choose
Basic idea:
If each process has a unique identity, and the identities are ordered
Elect the non-crashed node with minimum/maximum identity
Definition of en Election Algorithm
Formally, an algorithm is an election algorithm iff:
Each process has the same local algorithm
The algorithm is decentralized
It can be initiated by any number of processes in the system
It reaches a terminal configuration, and in each reachable terminal configuration one process is in state leader and the rest are in the state lost
Assumptions
Fully asynchronous system
No global clock, transmission times arbitrary
Every process has a unique identity
Identities are totally ordered
Because we have finite number of processes:
Max identity and Min identity available (extreme values)