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
11 - Sense of Direction and Orientation
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
Networks of regular structure, such as the torus or the hypercube, usually have the links labeled with their direction. We now discuss some recent research evaluating the benefits of such a labeling, called Sense of Direction or SoD. The availability of sense of direction strengthens the model and allows processors to communicate more efficiently with each other, and to exploit topological properties of the network algorithmically.
Sense of direction has been shown to reduce the complexity of some problems, but the number of problems for which this applies is surprisingly small. Indeed, for many problems, more efficient or easier algorithms are known if the edge labeling can be exploited. However, in many non-trivial cases good lower bounds for the unlabeled case are not available, and moreover some surprisingly efficient algorithms exist in unlabeled graphs.
The chapter attempts to follow the scientific struggle, started by Santoro [San84], to establish cases in favor of sense of direction in two areas: broadcasting and election.
We shall define sense of direction for several specific classes of network, and show how the election problem on rings can be solved more efficiently if chords and a sense of direction are available. We shall show that elections can be performed with linear complexity in hypercubes and cliques if SoD is available, but also that a randomized algorithm can achieve the same complexity without using SoD. Algorithms to compute an SoD in networks where none is given will also be discussed.
- Type
- Chapter
- Information
- Introduction to Distributed Algorithms , pp. 356 - 395Publisher: Cambridge University PressPrint publication year: 2000