Dijkstra–Scholten algorithm

The Dijkstra–Scholten algorithm (named after Edsger W. Dijkstra and Carel S. Scholten) is an algorithm for detecting termination in a distributed system.[1][2] The algorithm was proposed by Dijkstra and Scholten in 1980.[3]

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 a 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

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

Dijkstra–Scholten algorithm for a tree

Dijkstra–Scholten algorithm for directed acyclic graphs

Dijkstra–Scholten algorithm for cyclic directed graphs

See also


References

  1. Ghosh, Sukumar (2010), "9.3.1 The Dijkstra–Scholten Algorithm", Distributed Systems: An Algorithmic Approach, CRC Press, pp. 140–143, ISBN 9781420010848.
  2. Fokkink, Wan (2013), "6.1 Dijkstra–Scholten algorithm", Distributed Algorithms: An Intuitive Approach, MIT Press, pp. 38–39, ISBN 9780262318952.
  3. Dijkstra, Edsger W.; Scholten, C. S. (1980), "Termination detection for diffusing computations" (PDF), Information Processing Letters 11 (1): 1–4, doi:10.1016/0020-0190(80)90021-6, MR 585394.
This article is issued from Wikipedia - version of the Saturday, April 16, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.