Distributed Computing : A Locality-Sensitive Approach

ISBN-13: 9780898714647 / Angielski

David Peleg

Opis

Gives a thorough exposition of network spanners and other locality-preserving network representations such as sparse covers and partitions.

Spis treści

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.