Termination Detection

Question 1

DFG’s Token Algorithm

Answer 1

N processes
* ordered in logical ring and number from 0 to n-1.
* Token can only be sent clockwise in the ring.
* Work can be sent from any process to any process.
* each is white or black
* all processes may send/receive messages with work to another process
* only idle processes may send the token

One token
* white or black

Question 2

DFG Initially

Answer 2

• Token and processes set to white
• Token’s and processes message count 0
• Organise process in a logical run
• Token at process 0
• Process 0 is active and has the initial problem

Question 3

DFG All processes

Answer 3

Upon receiving a message
* Becomes active until work completed

Work completed; nothing to receive
* Becomes idle

When sending a message
* Changes own colour to black

When sending a token
* Changes own colour to white

Question 4

DFG Process 0

Answer 4

Idle and has token: start termination detection
* Changes own colour to white
* Changes token colour to white
* Sends token to process (N-1)

Receives token from process 1
* Process 0 white and token white
Safe to terminate
* Process 0 black or token black
Wait until idle and then start termination detection again

Question 5

DFG Worker Processes

Answer 5

1. Continues working until idle
2. Updates token
   
   • Adds its message count to token
   • If black
     
     • Changes own colour to white
     • Changes token colour to black
   • If white
     
     • Leaves token colour unchanged
3. Sends token to next process in ring

Question 6

Weight Throwing

Answer 6

• Proc 0 is the controlling process and gets the original job with a starting weight w0 = C
• Every other Proc i (0 < i < N) has a starting weight wi = 0
• Every message j (j > 0) includes a weight wj which is assigned by the sender
• Invariants: The sum of all the weights in the system (at processes and in
  messages) is always = C, i.e.,
• When any Proc i sends work msg j: It also sends some of its own weight, say wj, so wi = wi – wj
• When any Proc i receives work and weight wj: it adds it to its own weight: so wi = wi + wj
• When Proc i (i > 0) becomes idle: it sends its weight to Proc 0, so wi = 0 and w0 = w0 + wi
• When Proc 0 becomes idle
  
  • If w0 = C -> it concludes termination
  • If w0 < C -> it waits for more messages

Question 7

Spanning Tree

Answer 7

• Initially
  
  • each leaf process is given a white token
  • all processes are white
• When a process sends a message to another, it changes to black
• When a leaf process terminates
  
  • It sends a black token if it is black, otherwise it sends a white token
• When a non-leaf process terminates and it has received a token from every child then
  
  • if it is black or received a black token from one of its children, it sends a black token to its parent
  • if it is white and did not received a black token from any of its children, it sends a white token to its
    parent
• Root restarts termination if
  
  • it has receive a black token from any of its children
• Root concludes termination if
  
  • It is white
  • It is idle
  • It has received a white token from each of its children