9- termination detection Flashcards
Explain the problem set we’re trying to solve in termination detection.
Each of the processes is either active or passive. Only active processes can send messages related to the computation. An active process may become passive spontaneously. A passive process can only become active because of the reception of a
message of the computation.
Problem: Design a DA that determines that the computation has finished
Explain the naive solution for termination detection on a uniderictional ring topology
P0 sends a token to the next node, which only forwwards tokens when its passive. When the node is active, it waits with forwarding of the token until it is passive.
Explain how a problem can arise with using naive tokens for termination detection.
If an unrelated process starts sending a message, it could re-activate nodes that the token deemed ‘passive’. Invalidating the token’s awnser.
Explain the idea of the solution of naive tokens.
Tokens are initiated as white. Whenever a process is active/passive it turns white/black. So when a token meets a black process, it turns black itself. If P0 receives its token as black, then it will retry. Otherwise it concludes termination.
Explain the general termination-detection.
Initially, special process P0 has 1 weight and all other processes have none.
Then when P0 start a message, it gives all other processes (that want to start a computation) 1/k of its own weight (W(p0) = 0).
Whenever process Pi sends a computation message, it also sends half of its weight with that message. Once process Pi goes idle, it sends it remaining weights to P0 (who does acts as an observer).
Termination is detected when P0 receives its own weight back.
In general termination detection, what is the weight of Pi+1 and Pi after Pi+1 recieves a message from Pi?
Pi: Wi/2
Pi+1: Wi+1 + (Wi / 2)
In general termination detection: What happens if a process receives a message after it sent all its weights to P?
It first adds the weight of that message to its own (which is 0 + W(m)) and then continues as describes; half with the message it sends out, and half to p0 when it turns idle
