Book contents
- Frontmatter
- Contents
- Preface
- 1 Introduction
- 2 A model of distributed computations
- 3 Logical time
- 4 Global state and snapshot recording algorithms
- 5 Terminology and basic algorithms
- 6 Message ordering and group communication
- 7 Termination detection
- 8 Reasoning with knowledge
- 9 Distributed mutual exclusion algorithms
- 10 Deadlock detection in distributed systems
- 11 Global predicate detection
- 12 Distributed shared memory
- 13 Checkpointing and rollback recovery
- 14 Consensus and agreement algorithms
- 15 Failure detectors
- 16 Authentication in distributed systems
- 17 Self-stabilization
- 18 Peer-to-peer computing and overlay graphs
- Index
7 - Termination detection
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface
- 1 Introduction
- 2 A model of distributed computations
- 3 Logical time
- 4 Global state and snapshot recording algorithms
- 5 Terminology and basic algorithms
- 6 Message ordering and group communication
- 7 Termination detection
- 8 Reasoning with knowledge
- 9 Distributed mutual exclusion algorithms
- 10 Deadlock detection in distributed systems
- 11 Global predicate detection
- 12 Distributed shared memory
- 13 Checkpointing and rollback recovery
- 14 Consensus and agreement algorithms
- 15 Failure detectors
- 16 Authentication in distributed systems
- 17 Self-stabilization
- 18 Peer-to-peer computing and overlay graphs
- Index
Summary
Introduction
In distributed processing systems, a problem is typically solved in a distributed manner with the cooperation of a number of processes. In such an environment, inferring if a distributed computation has ended is essential so that the results produced by the computation can be used. Also, in some applications, the problem to be solved is divided into many subproblems, and the execution of a subproblem cannot begin until the execution of the previous subproblem is complete. Hence, it is necessary to determine when the execution of a particular subproblem has ended so that the execution of the next subproblem may begin. Therefore, a fundamental problem in distributed systems is to determine if a distributed computation has terminated.
The detection of the termination of a distributed computation is non-trivial since no process has complete knowledge of the global state, and global time does not exist. A distributed computation is considered to be globally terminated if every process is locally terminated and there is no message in transit between any processes. A “locally terminated” state is a state in which a process has finished its computation and will not restart any action unless it receives a message. In the termination detection problem, a particular process (or all of the processes) must infer when the underlying computation has terminated.
When we are interested in inferring when the underlying computation has ended, a termination detection algorithm is used for this purpose.
- Type
- Chapter
- Information
- Distributed ComputingPrinciples, Algorithms, and Systems, pp. 241 - 281Publisher: Cambridge University PressPrint publication year: 2008