Termination Detection

Question 1

General Characteristics of Termination Detection

Answer 1

1. A process can only be idle or active
   An idle process only activates on receipt of a message
2. Only active processes can send messages

Question 2

What must Termination Detection Ensure?

Answer 2

1. Execution of a TD algorithm cannot indefinitely delay any computation.
2. The TD algorithm must not require any additional communication channels.

Question 3

Explain the Distributed Snapshot TD

Answer 3

The main idea behind the algorithm is as follows: When a computation terminates, there must exist a unique process which became idle last. When a computation goes from active to idle, it tells all processes to take a snapshot of themselves. Processes will do this if they believe the requesting process became idle before it did.

Once each process has created a snapshot, a global snapshot is available and can be checked to see if all the processes are idle. If so, the work is done and they can terminate.

Question 4

Explain the Weight Throwing TD

Answer 4

We initialise our system with a total weight of 1. When the controlling process starts sending processes data to process, it also sends a fraction of its weight to them. When every process finishes its work, it sends the results of the computation back to the controller ​ or to another process, along with the weight it has left.

Thus, if the controller receives back all the data, it will once again have a weight of 1. If so, it knows that all the work has been completed.

Question 5

Explain the Spanning Tree TD

Answer 5

The algorithm assumes N processes with P0 as the root/start process.

The root node communicates with the processes down the tree. If a child process terminates, it informs the parent. If all the child processes are terminated, the parent itself terminates.

A child will hold a white token if it has not sent any work to any other processes and is idle, otherwise it’ll hold a black token if it has sent work somewhere. ​ If the root process receives a black token, it knows to restart the detection algorithm as another process might have been restarted.

Question 6

Explain Message Optimal TD

Answer 6

This is similar however it differs in that a token is only returned to a parent once all the work a process has distributed and itself is complete.

Question 7

Explain Token Passing (Dijkstra’s Algorithm)

Answer 7

A master process sends a white token on a round trip where it visits all the other processes
exactly once.

When a token visits a process, two things can happen:

● If the process is idle, the token remains unchanged.

● If the process is has sent work somewhere since the token visited last, the token is
turned black. The process holds the token until it becomes idle.

If the token is sent by the master process, and returns as the same white colour as when sent - the algorithm has proven that all processes are idle and no messages have been passed around has taken place since the last token round-trip. Thus, all work is done and the system can terminate. Otherwise it must start again