Distributed Termination Detection

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:

• Every node maintains a counter c. Sending a message increases c by one; the receipt of a message decreases c by one. The sum of all counters thus equals the number of messages pending in the network.
• When node 0 initiates a detection probe, it sends a token with a value 0 to node N-1. Every node i keeps the token until it becomes passive; it then forwards the token to node i-1 increasing the token value by c.
• Every node and also the token has a color (initially all white). When a node receives a message, the node turns black. When a node forwards the token, the node turns white. If a black machine forwards the token, the token turns black; otherwise the token keeps its color.
• When node 0 receives the token again, it can conclude termination, if
  • node 0 is passive and white,
  • the token is white, and
  • the sum of the token value and c is 0.
  Otherwise, node 0 may start a new probe.

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.

Source Code (link termporarily disabled)