The bully algorithm

Question 1

when can we let processes crash during the election?

Answer 1

We can if we assume that the system is synchronous, so we can use timeouts to detect process failure

Question 2

state the Bully algorithm assumptions

Answer 2

Bully algorithm assumes that each process knows which
processes have higher identifiers, and can communicate with
each such process

Question 3

Name the Three types of messages in this algorithm

Answer 3

♦ election – announces an election
♦ answer – sent in response to an election message
♦ coordinator – announces identity of the elected process

Question 4

how is an election initiated?

Answer 4

A process initiates an election when it notices, through timeouts,
that the current coordinator has failed – several processes may
discover this concurrently

Question 5

What does Synchronous system assumptions enable?

Answer 5

construction of a reliable failure detector

Question 6

Give the upper bound on the total elapsed time from sending a message to another process to receiving a response

Answer 6

T = 2 (T[trans] + T[process])

Question 7

What is T[trans]?

Answer 7

maximum transmission delay

Question 8

What is T[process]?

Answer 8

maximum processing delay in a process

Question 9

When and how can a process elect itself?

Answer 9

Process that knows it has the highest identifier can elect itself as the coordinator by sending a coordinator message to all processes with smaller identifiers

Question 10

What does a process with a lower identifier do? (3 things)

Answer 10

♦ Sends an election message to processes with higher identifiers and awaits an answer message in response
♦ if none arrives within time T, process considers itself the coordinator and sends a coordinator message to all processes with lower identifiers
♦ else waits T’ for a coordinator message to arrive from the new coordinator – if none arrives, it calls (begins) another election

Question 11

What happens when process p[i] receives a coordinator message?

Answer 11

If p[i] receives a coordinator message, sets elected[i]
to the identifier of the coordinator contained in the
message

Question 12

What happens when process p[i] receives a election message?

Answer 12

If a process receives an election message, it sends

back an answer message and begins another election, unless it has begun one already

Question 13

What happens when a process is started to replace a crashed process?

Answer 13

it begins an election

Question 14

What happens when a process is started to replace a crashed process and that process has the highest identifier?

Answer 14

♦ if it has the highest identifier, then it will
announce itself as the new coordinator, even though the
current coordinator is functioning
♦ i.e. it “bullies” its way into being the coordinator

Question 15

Performance of bully algorithm - how does it meet E2 (liveness) ?

Answer 15

E2 (liveness) is met by the assumption of reliable message delivery

Question 16

Performance of bully algorithm - how does it meet E1 (safety) ?

Answer 16

E1 (safety) is met under the assumption that no process is replaced

Question 17

Performance of bully algorithm - when does it not meet E1 (safety) ?

Answer 17

E1 (safety) is not met if processes that crash are replaced by processes with the same identifier

♦ Multiple processes may announce themselves coordinators concurrently

Question 18

If the assumed timeout values are inaccurate what does this imply?

Answer 18

The failure detector is unreliable and E1 may also be broken

Question 19

Performance of bully algorithm - Give the best case scenario in terms of:

• number of messages
• turnaround time

Answer 19

The second highest identifier notices coordinator’s failure, declares itself coordinator, sends N-2 messages to others;

turnaround time is 1
message transmission time

Question 20

Performance of bully algorithm - Give the worst case scenario in terms of:

• number of messages
• turnaround time

Answer 20

lowest identifier notices coordinator’s failure, since N-1 processes begin elections, O(N 2 ) messages; approx.

N+1 transmission times