Dijkstra-Scholten algorithm

The Dijkstra-Scholten algorithm, named after Edsger W. Dijkstra and Carel S. Scholten and proposed by them in 1980, detects termination in a distributed system. It is a tree-based algorithm. The initiator of a computation is the root of the tree. A process that receives a computational message while not yet in the computation joins the tree as a child of the sender, with no acknowledgment at that point, while a process already in the computation immediately acknowledges the sender. When a process has no more children and has become idle it detaches itself by acknowledging its parent, and termination occurs when the initiator has no children and is idle. The scheme extends from simple trees to directed acyclic graphs, using a deficit count on each edge, and to cyclic graphs, by implicitly building a spanning tree through the first edge on which each node received a message.