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
6 - Wave and Traversal Algorithms
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
In the design of distributed algorithms for various applications several very general problems for process networks appear frequently as subtasks. These elementary tasks include the broadcasting of information (e.g., a start or terminate message), achieving a global synchronization between processes, triggering the execution of some event in each process, or computing a function of which each process holds part of the input. These tasks are always performed by passing messages according to some prescribed, topology-dependent scheme that ensures the participation of all processes. Indeed, as will become more evident to the reader in later chapters, these tasks are so fundamental that solutions to more complicated problems such as election (Chapter 7), termination detection (Chapter 8), or mutual exclusion can be given in which communication between processes occurs only via these message passing schemes.
The importance of message-passing schemes, called wave algorithms from now on, justifies a separate treatment of them in isolation from a particular application algorithm in which the schemes can be embedded. This chapter formally defines wave algorithms (Subsection 6.1.1) and proves some general results about them (Subsection 6.1.2). The observation that the same algorithms can be used for all of the fundamental tasks listed above, i.e., broadcasting, synchronization, and computing global functions, will be made rigorous (Subsections 6.1.3 through 6.1.5). Section 6.2 presents some widely used wave algorithms. Section 6.3 considers traversal algorithms, which are wave algorithms with the additional property that the events of a computation of the algorithm are totally ordered by causality.
- Type
- Chapter
- Information
- Introduction to Distributed Algorithms , pp. 181 - 226Publisher: Cambridge University PressPrint publication year: 2000