Book contents
- Frontmatter
- Contents
- Preface
- 1 Introduction: Distributed Systems
- Part One Protocols
- Part Two Fundamental Algorithms
- 6 Wave and Traversal Algorithms
- 7 Election Algorithms
- 8 Termination Detection
- 9 Anonymous Networks
- 10 Snapshots
- 11 Sense of Direction and Orientation
- 12 Synchrony in Networks
- Part Three Fault Tolerance
- Part Four Appendices
- References
- Index
8 - Termination Detection
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface
- 1 Introduction: Distributed Systems
- Part One Protocols
- Part Two Fundamental Algorithms
- 6 Wave and Traversal Algorithms
- 7 Election Algorithms
- 8 Termination Detection
- 9 Anonymous Networks
- 10 Snapshots
- 11 Sense of Direction and Orientation
- 12 Synchrony in Networks
- Part Three Fault Tolerance
- Part Four Appendices
- References
- Index
Summary
A computation of a distributed algorithm terminates when the algorithm has reached a terminal configuration; that is, a configuration in which no further steps of the algorithm are applicable. It is not always the case that in a terminal configuration each process is in a terminal state; that is, a process state in which there is no event of the process applicable. Consider a configuration where each process is in a state that allows the receipt of messages, and all channels are empty. Such a configuration is terminal, but the processes' states could also occur as intermediate states in the computation. In this case, the processes are not aware that the computation has terminated; and the termination of the computation is said to be implicit. Termination is said to be explicit in a process if the state of that process in the terminal configuration is a terminal state of the process. Implicit termination of the computation is also called message termination because no more messages are exchanged when a terminal configuration has been reached. Explicit termination is also called process termination because the processes have terminated if an algorithm explicitly terminates.
It is usually easier to design an algorithm that terminates implicitly than one that terminates explicitly. Indeed, during the design of an algorithm all aspects regarding the proper termination of processes can be ignored; the design concentrates on bounding the overall number of events that can take place.
- Type
- Chapter
- Information
- Introduction to Distributed Algorithms , pp. 268 - 306Publisher: Cambridge University PressPrint publication year: 2000