Dijkstra–Scholten algorithm: Difference between revisions

Revision as of 06:45, 14 August 2009

Revision as of 01:17, 17 December 2009

Line 1:

{{Unreferenced|date=December 2009}}

The '''Dijkstra-Scholten algorithm''' is an [[algorithm]] for detecting [[Termination analysis|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:

Line 14:

* 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 directed acyclic 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.

Line 27 ⟶ 25:

* 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.

== Dijkstra-Scholten algorithm for cyclic directed graphs ==

* If cycles are allowed, the previous algorithm does not work. This is because, there may not be any node with zero outgoing edges. So, potentially there is no node which can terminate without consulting other nodes.

* The Dijkstra-Scholten algorithm solves this problem by implicitly creating a [[spanning tree (mathematics)|spanning tree]] of the graph. A spanning-tree is a tree which includes each node of the underlying graph once and the edge-set is a subset of the original set of edges.

Line 38 ⟶ 35:

*# Send signals on ''First_Edge''. (Once steps 1 and 2 are complete, a node informs its parent in the spanning tree about its intention of terminating.)

== See also ==

* [[ Huang's algorithm ]]

{{DEFAULTSORT:Dijkstra-Scholten Algorithm}}

[[Category:Graph algorithms]]

[[Category:Articles lacking sources (Erik9bot)]]

[[Category:Termination algorithms]]