Election algorithms

Question 1

Define Election algorithms and give an example

Answer 1

Algorithms for choosing a unique process to play a particular role

E.g. choose mutual exclusion central server from among the processes that need to use the critical section

Question 2

State a key property of an elected process

Answer 2

Choice of elected process must be unique, even if several processes call elections concurrently

Question 3

The performance of an election algorithm is measured by?

Answer 3

♦ Total network bandwidth utilisation (total messages sent)

♦ Turnaround time – number of serialised message transmission times between initiation and termination of a single run

Question 4

What type is Chang and Roberts algorithm?

Answer 4

ring-based election

Question 5

In Chang and Roberts algorithm how are processes arranged?

Answer 5

Processes are arranged in a logical ring

Question 6

Explain how in Chang and Roberts algorithm processes send messages

Answer 6

Each process p(i) has a communication channel to the next process in the ring, p(i+1)modN.

All messages sent clockwise around the ring.

Question 7

What is the goal of Chang and Roberts algorithm?

Answer 7

to elect the coordinator, the process with the largest identifier

Question 8

In Chang and Roberts algorithm how are elections initiated?

Answer 8

Any process can initiate an election
♦ Marks itself as a participant
♦ Places its identifier in an election message
♦ Sends the message to its clockwise neighbour

Question 9

What happens in Chang and Roberts algorithm when a process p[k] receives an election message with enclosed ID p[i]?

Answer 9

♦ If p[k] non-participant, forward max(p[i], p[k]); mark itself as participant
♦ If p[k] participant, forward p[i]only if p[i]> p[k] otherwise do nothing

Question 10

What happens in Chang and Roberts algorithm when a process p[k] receives an election message and (p[i]== p[k])?

Answer 10

♦ p[k] becomes coordinator

♦ Mark itself non-participant; send elected message with its ID to neighbour

Question 11

What happens in Chang and Roberts algorithm when a process p[k] receives an elected message with enclosed ID p[i]?

Answer 11

♦ Mark itself as non-participant
♦ Set elected[k] = p[i]
♦ If (p[k] != coordinator)
{Forward message to neighbour}

Question 12

Performance of ring-based election algorithm - state how E1 is met (2 points)

Answer 12

♦ All identifiers are compared; a process must receive its own identifier back before sending an elected message
♦ For any two processes, the one with the larger
identifier will not pass on the other’s identifier =>
impossible that both should receive their own identifiers back

Question 13

Performance of ring-based election algorithm - state how E2 is met (

Answer 13

E2 follows immediately from the guaranteed traversals of the ring (no failures)
♦ non-participant and participant states used so that messages arising when another process starts a
concurrent election are extinguished as soon as
possible, before the winning election result has been
announced

Question 14

Give the worst case performance of ring-based election algorithm If only a single process starts an election.

Answer 14

Worst case is when anti-clockwise neighbour has the highest identifier

Question 15

In the worst case performance of ring-based election algorithm how many messages are required to reach the winner?

Answer 15

N-1 messages are needed to reach this neighbour

Question 16

In the worst case performance of ring-based election algorithm how many messages are required for the winner to receive it’s own identifier?

Answer 16

N messages required for this winner to receive its own identifier

Question 17

In the worst case performance of ring-based election algorithm how many elected messages are sent?

Answer 17

The elected message is sent N times

Question 18

In the worst case performance of ring-based election algorithm how many messages are sent in total?

Answer 18

3N-1 messages

Question 19

State the worst case performance of ring-based election algorithm in terms of:

• bandwidth utilisation
• turnaround time

Answer 19

Worst case bandwidth utilisation – 3N-1 messages

Worst case turnaround time – O(3N-1)