Dijkstra–Scholten algorithm

The Dijkstra-Scholten Algorithm is an algorithm for detecting termination in a distributed system. The algorithm was proposed by Dijkstra and Scholten in 1980.

First, let us consider the case of a simple process graph which is a tree. A distributed computation which is tree-structured is not uncommon. Such a process graph may arise when the computation is strictly divide-and-conquer type. A node starts the computation and divides the problem in two (or more, usually a multiple of 2) roughly equal parts and distribute those parts to other processors. This process continues recursively until the problems are of sufficiently small size to solve in a single processor.

Algorithm

Dijkstra-Scholten's algorithm is a tree-based algorithm which can be described by the following:

• The initiator of a computation is the root of the tree.
• Upon receiving a computational message:
  • If the receiving process is currently not in the computation: the process joins the tree by becoming a child of the sender of the message. (No acknowledgement message is sent at this point.)
  • If the receiving process is already in the computation: the process immediately sends an acknowledgement message to the sender of the message.
• When a process has no more children and has become idle, the process detaches itself from the tree by sending an acknowledgement message to its tree parent.
• Termination occurs when the initiator has no children and has become idle.

Dijkstra-Scholten Algorithm for a Tree

• For a tree, it is easy to detect termination. When a leaf process determines that it has terminated, it sends a signal to its parent. In general, a process waits for all its children to send signals and then it sends a signal to its parent.
• The program terminates when the root receives signals from all its children.

Dijkstra-Scholten Algorithm for Acyclic Directed Graphs

• The algorithm for a tree can be extended to acyclic directed graphs. We add an additional edge Deficit to each edge.
• On an incoming edge, Deficit will denote the difference between the number of messages received and the number of signals sent in reply.
• When a node wishes to terminate, it waits until it has received signals from outgoing edges reducing their deficits to zero.
• Then it sends enough signals to ensure that the deficit is zero on each incoming edge.
• Since the graph is acyclic, some nodes will have no outgoing edges and these nodes will be the first to terminate after sending enough signals to their incoming edges. After that the nodes at higher levels will terminate level by level.