Distributed computing : a locality-sensitive approach / David Peleg.

Format:

Book

Author/Creator:

Peleg, D. (David)

Contributor:

Society for Industrial and Applied Mathematics.

Series:

SIAM monographs on discrete mathematics and applications ; 5.

SIAM monographs on discrete mathematics and applications ; 5

Language:

English

Subjects (All):

Electronic data processing--Distributed processing.

Electronic data processing.

Physical Description:

1 electronic text (xvi, 343 p.) : digital file.

Place of Publication:

Philadelphia, Pa. : Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104), 2000.

Language Note:

English

System Details:

Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Summary:

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. 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.

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.

Notes:

Bibliographic Level Mode of Issuance: Monograph

Includes bibliographical references (p. 319-337) and index.

Title from title screen, viewed 12/30/2010.

ISBN:

0-89871-977-1

Publisher Number:

DT05 SIAM