Content deleted Content added
No edit summary |
see Wikipedia:Manual of Style: too many capital letters |
||
Line 1:
The '''Dijkstra-Scholten
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 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.
Line 14:
* Termination occurs when the initiator has no children and has become idle.
== Dijkstra-Scholten
* For a tree, it is easy to detect termination. When a leaf process determines that it has terminated, it sends a signal to its parent. In general, a process waits for all its children to send signals and then it sends a signal to its parent.
* The program terminates when the root receives signals from all its children.
== Dijkstra-Scholten
* The algorithm for a tree can be extended to acyclic directed graphs. We add an additional edge [[Deficit]] to each edge.
Line 27:
* Since the graph is acyclic, some nodes will have no outgoing edges and these nodes will be the first to terminate after sending enough signals to their incoming edges. After that the nodes at higher levels will terminate level by level.
== Dijkstra-Scholten
* If cycles are allowed, the previous algorithm does not work. This is because, there may not be any node with zero outgoing edges. So, potentially there is no node which can terminate without consulting other nodes.
Line 39:
== See also ==
* [[ Huang's
[[Category:Graph algorithms]]
| |||