Dijkstra–Scholten algorithm: Difference between revisions

Revision as of 01:26, 27 February 2013

Latest revision as of 02:21, 15 December 2024

(17 intermediate revisions by 13 users not shown)

Line 1:

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=https://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=https://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

{{Unreferenced|date=December 2009}}

| last1 = Dijkstra | first1 = Edsger W.

The '''Dijkstra–Scholten algorithm''' (named after [[Edsger W. Dijkstra]] and C. S. Scholten) is an [[algorithm]] for detecting [[Termination analysis|termination]] in a [[distributed system]]. The algorithm was proposed by Dijkstra and Scholten in 1980.

| last2 = Scholten | first2 = C. S.

| doi = 10.1016/0020-0190(80)90021-6

| issue = 1

| journal = Information Processing Letters

| mr = 585394

| pages = 1–4

{{Reflist | title = Termination detection for diffusing computations}}

| url = http://www.cs.mcgill.ca/~lli22/575/termination3.pdf

| volume = 11

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

==Algorithm==

The Dijkstra–Scholten algorithm <ref>{{cite web|last=Gaikwad|first=Rahul|url=http://www.cs.utexas.edu/~EWD/transcriptions/EWD06xx/EWD687a.html|work=Termination detection for diffusing computations|accessdate=27 February 2013}}</ref> is a tree-based algorithm which can be described by the following:

The Dijkstra–Scholten 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 acknowledgementacknowledgment message is sent at this point.)

** If the receiving process is already in the computation: the process immediately sends an acknowledgementacknowledgment 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 acknowledgementacknowledgment message to its tree parent.

* Termination occurs when the initiator has no children and has become idle.

Line 35 ⟶ 46:

==See also==

* [[Huang's algorithm]]

==References==

{{reflist}}

{{Edsger Dijkstra}}

{{DEFAULTSORT:Dijkstra-Scholten Algorithm}}

[[Category:Graph algorithms]]

[[Category:Termination algorithms]]

[[Category:Edsger W. Dijkstra]]

{{Reflist Termination detection for diffusing computations}}