Week 5 - Leader Election

Question 1

Synchronous Network Model

Answer 1

A representation of a network as directed graph with a fixed message alphabet M. Where each node is the graph represents a process. Edges represent channels, that are capable of holding at most a single message for each direction.

Question 2

In the synchronous network model, what does each process consist of?

Answer 2

Set of states
Set of start states
Message generation function
State transition function

Question 3

What is the LCR leader election algorithm?

Answer 3

Each process sends its identifier around the ring. When a process receives an identifier:
- if it is greater than its own it passes it on
- if it is less than its own it discards it
- if it is equal to its own it declares itself the leader

Question 4

What is the HS leader election algorithm?

Answer 4

Each process operates in phases 0, 1, 2… In each phase, l, each process sends out tokens containing its identifier in each direction. They are intended to travel 2^l before returning to their origin. When a process receives an identifier:
- if it is less than its own it discards it
- if is greater than its own it relays it
- if is is the same, then it elects itself the leader

Question 5

What is the TimeSlice leader election algorithm?

Answer 5

Runs in phases 1, 2, 3… In phase v only identifier v is allowed to circulate. if process i with identifier v exists and round (v-1)n+1 is reached without having previously received
a non-null message, process i elects itself and sends its identifier around the ring.

Question 6

What is the communication complexity of leader election algorithms that only permit comparisons between identifiers bounded by?

Answer 6

Ω(n logn)

Question 7

What is the leader election problem?

Answer 7

The leader election problem is for each process in a network to eventually decide whether it is a leader or not, subject to the constraint that exactly one processor decides that it is the leader