<- People Behind Informatics


All 0-9 A B C D E F G H I J K L M N O P Q R S T U V W XY Z




 
Distributed Termination Detection
Distributed termination detection is a core problem of the theory of distributed computing which has gained considerable interest in recent years. Distributed termination detection algorithms solve the problem of how to detect that all nodes (machines) of a distributed system have finished their work. The problem (as given in EWD840) can be described in the following way: N nodes are considered, each of which is either in active or in passive state. Only an active node can send messages to other nodes; message transmission is considered instantaneous. After having received a message, a passive node becomes active; the receipt of a message is the only mechanism that triggers a passive node’s transition to activity. For each node, the transition from the active to the passive state may occur "spontaneously". The state in which all nodes are passive and no messages are on their way is stable and the distributed computation is said to have terminated. The purpose of the algorithm is to enable one of the nodes to detect that this stable state has been reached. The algorithm described by Dijkstra works on a ring and requires synchronous communication. It is entirely described by six rules (see further details in EWD840). This algorithm extended Dijkstra’s initial work on termination detection described in EWD684. Edsger W. Dijkstra, Termination detection for diffusing computations, EWD684 Edsger W. Dijkstra, Derivation of a termination detection algorithm for distributed computations, EWD840 [Source: Laszlo Böszörmenyi: Notes to the Virtual Exhibition "People behind Informatics"]
 

 

<- People Behind Informatics


Home  |  Top  |  Search  |  Gallery  | Glossary  | Sitemap  |  Making Of  |  Help