Termination Detection

Question 1

What is the DGF algorithm and how does it work?

Answer 1

DGF is a token based algorithm in which tokens are sent clockwise around a ring of processes. Work can be sent among nay processes in the ring. The token can be be black or white and each process changes between being black or white.

Question 2

In DGF what colour does a process become when sending a message?

Answer 2

Black

Question 3

In DGF what colour does a process become when sending a token?

Answer 3

White

Question 4

In DGF what conditions must be met in order to know it is safe to terminate?

Answer 4

Process 0 must be white and receive a white token

Question 5

In DGF, what occurs if either process 0 is black or the token is black when the token reaches process 0?

Answer 5

If the process is black then wait until idle, if the token is black then don’t wait, then start termination detection again

Question 6

What happens if a process > 0 receives the token?

Answer 6

Adds it’s message count to the token
If it’s own colour is black, it changes its colour to white and changes the token to black.
If it’s own colour is white it leaves the token colour unchanged

Question 7

Describe the weight throwing termination detection algorithm

Answer 7

• process 0 is the controlling process and gets the original job and has starting weighting w_0 = C
• all other processes have a starting weight of w_i = 0
• every message includes a weight w_j
• the sum of all weights (w_i and w_j) is always = C
• when a process sends work message j it sends some of its own weight
• when a process receives work and weight, it adds the received work to its own weight
• when any process (not 0) becomes idle, it send its weight to process 0

Question 8

In the weight throwing algorithm what happens when process 0 becomes idle?

Answer 8

If w_0 = C it concludes termination detection
If w_0 < C it waits for more messages

Question 9

What is a difference with tokens between DGF and spanning tree?

Answer 9

DGF has one token which is white and is initially given to process 0 which is then sent in a logical ring to each process whereas in spanning tree it is arranged in a tree and every leaf node gets a white token initially.

Question 10

Describe what happens if a process terminates in spanning tree algorithm

Answer 10

If it is a leaf process: it sends a black token if it is black, otherwise it sends a white token
If it is a non-leaf process and has received a token from all children: if it is black or has received a black token from one of its children -> send black token, else if it is white AND did not receive a black token from anyone of its children -> send white token

Question 11

What happens when the root process receives a token from all its children in the spanning tree algorithm?

Answer 11

If one of the tokens is black: restart termination
If it’s is idle, white and all tokens are white: conclude termination