Dijkstra–Scholten algorithm: Difference between revisions

Revision as of 01:34, 27 February 2013

Revision as of 00:34, 5 July 2013

Line 1:

{{Unreferenced|date=December 2009}}

The '''Dijkstra–Scholten algorithm''' (named after [[Edsger W. Dijkstra]] and C.[[Carel S. Scholten]]) 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.