SIAM Homepage | Search Catalog | New Books | Author Index | Series Index | Title Index | View My Shopping Cart

The catalog and shopping cart are hosted for SIAM by EasyCart. Your transaction is secure. If you have any questions about your order, contact

Purchase Now!

Distributed Computing: A Locality-Sensitive ApproachDistributed Computing: A Locality-Sensitive Approach

David Peleg

SIAM Monographs on Discrete Mathematics and Applications 5

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.


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.

2000 / xvi + 343 pages / Hardcover / ISBN-13: 978-0-898714-64-7 / ISBN-10: 0-89871-464-8 /
List Price $145.50 / SIAM Member Price $101.85 / Order Code DT05
Quantity desired

Search our catalog for:

Shopping cart provided by:
Select quantity and list or member price and then click the "Click to Order" button to add books to your shopping cart.
Banner art adapted from a figure by Hinke M. Osinga and Bernd Krauskopf (University of Auckland, NZ.)