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
9 - Anonymous Networks
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 earlier chapters the assumption was usually made that unique identities are available to distinguish the processes of a distributed system. This assumption is valid in most of the existing distributed systems; the identity of a process is often taken as the address used to send messages to the process. For the latter purpose, however, it is also possible for processes to be identified via indirect addressing (Subsection 2.4.4), where each process distinguishes between its neighbors by locally known channel names.
A different use of identities was made in Chapter 7, where the identities of processes were employed to break the symmetry between processes. A typical example of this phenomenon is already found in a simple algorithm like that of Chang and Roberts (Algorithm 7.3), when it is initiated by two processes, p and q. In this computation, p receives q's token and q receives p's token; the situation would be completely symmetric if no ordering on process identities were available. The symmetry is broken by this ordering; the smaller of the two processes survives, the larger becomes defeated. More complicated examples of symmetry breaking by means of identity comparisons are found in other algorithms in Chapter 7.
Globally unique identities have also been used to detect termination, e.g., in Finn's algorithm (Algorithm 6.9). A process detects that it has indirectly received information about all processes if two collections of names coincide, where collection Inc includes the names of all neighbors of processes in NInc (for details, see Subsection 6.2.6).
- Type
- Chapter
- Information
- Introduction to Distributed Algorithms , pp. 307 - 334Publisher: Cambridge University PressPrint publication year: 2000