Jump to content

Dijkstra–Scholten algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Utopianheaven (talk | contribs) at 01:40, 11 February 2006 (sp). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The Dijkstra-Scholten Algorithm is an algorithm for detecting termination in a distributed system. The algorithm was proposed by Dijkstra and Scholten in 1980.

Algorithm

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

  • The initiator of a computation is the root of the tree.
  • Upon receiving a computational message:
    • If the receiving process is currently not in the computation: the process joins the tree by becoming a child of the sender of the message. (No acknowledgement message is sent at this point.)
    • If the receiving process is already in the computation: the process immediately sends an acknowledgement message to the sender of the message.
  • When a process has no more children and has become idle, the process detaches itself from the tree by sending an acknowledgement message to its tree parent.
  • Termination occurs when the initiator has no children and has become idle.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Dijkstra–Scholten_algorithm&oldid=39153818"