Dijkstra–Scholten algorithm: Difference between revisions

Revision as of 01:31, 27 February 2013

Revision as of 01:33, 27 February 2013

Line 4:

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.

The Dijkstra–Scholten algorithm <ref>{{cite web|last=Gaikwad|first=Rahul|url=http://www.cs.utexas.edu/~EWD/transcriptions/EWD06xx/EWD687a.html|work=Termination detection for diffusing computations|accessdate=27 February 2013}}</ref> is a tree-based algorithm which can be described by the following:

* The initiator of a computation is the root of the tree.