The '''Dijkstra–Scholten algorithm''' (named after [[Edsger W. Dijkstra]] and [[Carel S. Scholten]]) is an [[algorithm]] for detecting [[Termination analysis|termination]] in a [[distributed system]].<ref>{{citation|title=Distributed Systems: An Algorithmic Approach|first=Sukumar|last=Ghosh|publisher=CRC Press|year=2010|contribution=9.3.1 The Dijkstra–Scholten Algorithm|pages=140–143|url=httphttps://books.google.com/books?id=aVjVzuav7cIC&pg=PA140|isbn=9781420010848}}.</ref><ref>{{citation|title=Distributed Algorithms: An Intuitive Approach|first=Wan|last=Fokkink|publisher=MIT Press|year=2013|isbn=9780262318952|pages=38–39|url=httphttps://books.google.com/books?id=QqNWAgAAQBAJ&pg=PA38|contribution=6.1 Dijkstra–Scholten algorithm}}.</ref> The algorithm was proposed by Dijkstra and Scholten in 1980.<ref>{{citation
| last1 = Dijkstra | first1 = Edsger W.
| last2 = Scholten | first2 = C. S.
Line 12:
| year = 1980}}.</ref>
First, let us consider the case of a simple [[process graph]] which is a [[tree (data structure)|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 algorithm|divide-and-conquer]] type. A [[node (networking)|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.
