Election Algos Flashcards
(9 cards)
1
Q
Describe a simple election algorithm
A
- P broadcasts its request to all processes
- Each process responds with id & current load
- P chooses least loaded process and announces to everyone
2
Q
What are the 5 states a process can be in?
A
- Sleep
- Cand/Active
- Passive
- Lost
- Leader
3
Q
An election algorithm must satisfy these 3 things:
A
- Terminal configuration in each computation
- Each configuration must have a leader and other active processes in state Lost
- An execution can be initialised by any process
4
Q
Is an election algorithm centralised or decentralised?
A
Decentralised
5
Q
What must precede an election?
A
A ‘wake-up’ call.
6
Q
Describe how ‘wake-up’ method works.
A
- Election initiator sends wake up message to all neighbours
- Any process that receives the message will:
1. Wake up
2. Send wake up message to its neighbours.
7
Q
Why does a woken up process only execute the wave algorithm after it knows all its neighbours have woken up?
A
No First-In First-Out communication assumed.
8
Q
What construction can be used to make an election algorithm centralised?
A
Extinction.
9
Q
Explain the principles of extinction.
A
- Each wave holds id of initiator
- Only one wave, the one with smallest id, survives.
- Initiator announces the process with smallest id as leader.
