Distributed Computing
A Locality-Sensitive Approach

Table of Contents

Preface
1. Introduction
Part I. Basics of Distributed Network Algorithms
2. The distributed network model
3. Broadcast and convergecast
4. Downcasts and upcasts
5. Tree constructions
6. Synchronizers
7. Vertex coloring
8. Maximal independent sets (MIS)
9. Message routing
10. Local queries and local resource finding
Part II. Locality-Preserving Representations
11. Clustered representations: Clusters, covers and partitions
12. Sparse covers
13. Sparse partitions
14. Related graph representations
15. Skeletal representations: spanning trees, tree covers and spanners
16. Sparse spanners for unweighted graphs
17. Light-weight spanners
18. Spanners with low average stretch
19. Proximity-preserving labeling systems
Part III. Distributed Constructions and Applications of LP-Representations
20. A basic algorithm for constructing network partitions
21. Efficient algorithms for constructing covers
22. Efficient algorithms for constructing network decompositions
23. Exploiting topological knowledge: broadcast revisited
24. How local are global tasks? MST revisited
25. Local coordination: Synchronizers and MIS revisited
26. Hierarchical cluster-based routing
27. Regional directories: resource finding revisited
28. Additional applications in other settings
Bibliography
Index.