Distributed Computing
A Locality-Sensitive Approach
Will be published approx. on 30. September 2000
Book
Hardback
359 pages
978-0-89871-464-7 (ISBN)
Description
This volume presents the locality-sensitive approach to distributed network algorithms - the utilization of locality to simplify control structures and algorithms and reduce their costs. The author begins with an introductory exposition of distributed network algorithms focusing on topics that illustrate the role of locality in distributed algorithmic techniques. He then introduces locality-preserving network representations and describes sequential and distributed techniques for their construction. Finally, the applicability of the locality-sensitive approach is demonstrated through several applications.
Distributed Computing: A Locality-Sensitive Approach is the only book that gives a thorough exposition of network spanners and other locality-preserving network representations such as sparse covers and partitions. The book is useful for computer scientists interested in distributed computing, electrical engineers interested in network architectures and protocols, and for discrete mathematicians and graph theorists.
Distributed Computing: A Locality-Sensitive Approach is the only book that gives a thorough exposition of network spanners and other locality-preserving network representations such as sparse covers and partitions. The book is useful for computer scientists interested in distributed computing, electrical engineers interested in network architectures and protocols, and for discrete mathematicians and graph theorists.
More details
Series
Language
English
Place of publication
New York
United States
Target group
Professional and scholarly
Dimensions
Height: 228 mm
Width: 152 mm
Thickness: 24 mm
Weight
846 gr
ISBN-13
978-0-89871-464-7 (9780898714647)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Content
Preface
Chapter 1: Introduction
Part I: Basics of distributed network algorithms
Chapter 2: The distributed network model
Chapter 3: Broadcast and convergecast
Chapter 4: Downcasts and upcasts
Chapter 5: Tree constructions
Chapter 6: Synchronizers
Chapter 7: Vertex coloring
Chapter 8: Maximal independent sets (MIS)
Chapter 9: Message routing
Chapter 10: Local queries and local resource finding
Part II: Locality-preserving representations
Chapter 11: Clustered representations: Clusters, covers and partitions
Chapter 12: Sparse covers
Chapter 13: Sparse partitions
Chapter 14: Related graph representations
Chapter 15: Skeletal representations: Spanning trees, tree covers and spanners
Chapter 16: Sparse spanners for unweighted graphs
Chapter 17: Light-weight spanners
Chapter 18: Spanners with low average stretch
Chapter 19: Proximity-preserving labeling systems
Part III: Distributed constructions and applications of LP-representations
Chapter 20: A basic algorithm for constructing network partitions
Chapter 21: Efficient algorithms for constructing covers
Chapter 22: Efficient algorithms for constructing network decompositions
Chapter 23: Exploiting topological knowledge: Broadcast revisited
Chapter 24: How local are global tasks? MST revisited
Chapter 25: Local coordination: Synchronizers and MIS revisited
Chapter 26: Hierarchical cluster-based routing
Chapter 27: Regional directories: Resource finding revisited
Chapter 28: Additional applications in other settings
Bibliography
Index.
Chapter 1: Introduction
Part I: Basics of distributed network algorithms
Chapter 2: The distributed network model
Chapter 3: Broadcast and convergecast
Chapter 4: Downcasts and upcasts
Chapter 5: Tree constructions
Chapter 6: Synchronizers
Chapter 7: Vertex coloring
Chapter 8: Maximal independent sets (MIS)
Chapter 9: Message routing
Chapter 10: Local queries and local resource finding
Part II: Locality-preserving representations
Chapter 11: Clustered representations: Clusters, covers and partitions
Chapter 12: Sparse covers
Chapter 13: Sparse partitions
Chapter 14: Related graph representations
Chapter 15: Skeletal representations: Spanning trees, tree covers and spanners
Chapter 16: Sparse spanners for unweighted graphs
Chapter 17: Light-weight spanners
Chapter 18: Spanners with low average stretch
Chapter 19: Proximity-preserving labeling systems
Part III: Distributed constructions and applications of LP-representations
Chapter 20: A basic algorithm for constructing network partitions
Chapter 21: Efficient algorithms for constructing covers
Chapter 22: Efficient algorithms for constructing network decompositions
Chapter 23: Exploiting topological knowledge: Broadcast revisited
Chapter 24: How local are global tasks? MST revisited
Chapter 25: Local coordination: Synchronizers and MIS revisited
Chapter 26: Hierarchical cluster-based routing
Chapter 27: Regional directories: Resource finding revisited
Chapter 28: Additional applications in other settings
Bibliography
Index.