The Dijkstra–Scholten algorithm (named after Edsger W. Dijkstra and Carel S. Scholten) is an algorithm for detecting termination in a distributed system. The algorithm was proposed by Dijkstra and Scholten in 1980.
Contents
- Algorithm
- DijkstraScholten algorithm for a tree
- DijkstraScholten algorithm for directed acyclic graphs
- DijkstraScholten algorithm for cyclic directed graphs
- References
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
- Send signals on all incoming edges except the first edge. (Each node will send signals which reduces the deficit on each incoming edge to zero.)
- Wait for signals from all outgoing edges. (The number of signals received on each outgoing edge should reduce each of their deficits to zero.)
- 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.)