Distributed Termination Detection

RISC-Linz logo

Problem

Implement a distributed termination detection algorithm for a network of N nodes. Each node can be either in active or in passive state. Only an active node can send messages to other nodes; each message sent is received after some period of time later. After having received a message, a passive node becomes active; the receipt of a message is the only mechanism that triggers for a passive node its transition to activity. For each node, the transition from the active to the passive state may occur "spontaneously". The state in which all nodes are passive and no messages are on their way is stable: the distributed computation is said to have terminated. The purpose of the algorithm is to enable one of the nodes, say node 0, to detect that this stable state has been reached.

Algorithm

The algorithm (described by Dijkstra) works as follows:

For a detailed description of the algorithm, see this technical report.

Program

You should see a button labelled "Press Me" embedded below. If you do not see this button but the string "Please enable Java!" instead, you must enable Java on your Web browser and then reload the page.

Please enable Java!

Source Code (link termporarily disabled)


Maintained by: Wolfgang Schreiner
Last Modification: November 15, 1998

[DAJ ] [RISC-Linz] [University] [Search]