Dijkstra–Scholten algorithm

Dijkstra–Scholten algorithm

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

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.

Contents

Algorithm

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

Dijkstra–Scholten algorithm for a tree

  • 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 algorithm for directed acyclic graphs

  • The algorithm for a tree can be extended to acyclic directed graphs. We add an additional integer attribute Deficit to each edge.
  • On an incoming edge, Deficit will denote the difference between the number of messages received and the number of signals sent in reply.
  • When a node wishes to terminate, it waits until it has received signals from outgoing edges reducing their deficits to zero.
  • Then it sends enough signals to ensure that the deficit is zero on each incoming edge.
  • 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 algorithm for cyclic directed graphs

  • 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.
  • The Dijkstra–Scholten algorithm solves this problem by implicitly creating a spanning tree of the graph. A spanning-tree is a tree which includes each node of the underlying graph once and the edge-set is a subset of the original set of edges.
  • The tree will be directed (i.e., the channels will be directed) with the source node (which initiates the computation) as the root.
  • The spanning-tree is created in the following way. A variable First_Edge is added to each node. When a node receives a message for the first time, it initializes First_Edge with the edge through which it received the message. First_Edge is never changed afterwards. Note that, the spanning tree is not unique and it depends on the order of messages in the system.
  • Termination is handled by each node in three steps :
    1. Send signals on all incoming edges except the first edge. (Each node will send signals which reduces the deficit on each incoming edge to zero.)
    2. Wait for signals from all outgoing edges. (The number of signals received on each outgoing edge should reduce each of their deficits to zero.)
    3. Send signals on First_Edge. (Once steps 1 and 2 are complete, a node informs its parent in the spanning tree about its intention of terminating.)

See also


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Dijkstra-Scholten algorithm — The Dijkstra Scholten algorithm is an algorithm for detecting termination in a distributed system. The algorithm was proposed by Dijkstra and Scholten in 1980.First, let us consider the case of a simple process graph which is a tree. A… …   Wikipedia

  • Huang's algorithm — is an algorithm for detecting termination in a distributed system. The algorithm was proposed by Shing Tsaan Huang in 1989 in the Journal of Computers . Termination detection The basis of termination detection is in the concept of a distributed… …   Wikipedia

  • Edsger W. Dijkstra — Edsger Wybe Dijkstra Born May 11, 1930(1930 05 11) Rotterdam, Netherl …   Wikipedia

  • Diffusing update algorithm — DUAL, the Diffusing Update ALgorithm, is the algorithm used by Cisco s EIGRP routing protocol to ensure that a given route is recalculated globally whenever it might cause a routing loop. According to Cisco, the full name of the algorithm is DUAL …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

  • Reference counting — In computer science, reference counting is a technique of storing the number of references, pointers, or handles to a resource such as an object or block of memory. It is typically used as a means of deallocating objects which are no longer… …   Wikipedia

  • Garbage collection (computer science) — This article is about garbage collection in memory management. For garbage collection in an SSD, see garbage collection (SSD). For other uses, see garbage collection. In computer science, garbage collection (GC) is a form of automatic memory… …   Wikipedia

  • Intel iAPX 432 — Infobox Computer Hardware Cpu name = Intel iAPX 432 caption = produced start = 1981 produced end = slowest = 5 |slow unit = MHz fastest = 8 |fast unit = MHz fsb slowest = | fsb slow unit = fsb fastest = | fsb fast unit = manuf1 = Intel arch =… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”