Browse Books

Reviewer: Zhihui Xue

Distributed computing: a locality-sensitive approach is a new book mainly about the algorithm and theory in the distributed systems. The particular of the book is a thorough demonstration of the distributed computing from the locality aspect. In the beginning chapter, the book first gives an introduction of distributed systems, then discusses some important issues in the distributed computing, finally briefly describes the locality-sensitive distributed algorithms. After the introduction, the general distributed network algorithms are discussed in the part I of the book. It begins with the definition of distributed network model and complexity measures. Then the book gives a detail exposition of algorithms and protocols in distributed network. The topics include broadcast and convergecast, downcasts and upcasts, tree constructions, synchronizers, vertex coloring, maximal independent sets, message routing, local queries and local resource finding. The main features of this book are presented in the part II and III. Part II deals entirely with the locality-preserving representations. The author discusses three types of representations, which are cluster-based representation, skeletal representation, and network representation. The topics in this part are clusters, covers, partitions, and related graph representation, spanning trees, tree covers, spanners, and proximity preserving labeling systems. In the part III, the author integrates the distributed network algorithms and locality-preserving representations together and demonstrated the mutual applicability. In doing so, the author provides efficient distributed construction methods for partitions, covers and decompositions. Then the author illustrates the applicability of locality-preserving representations in distributed network algorithms by reexamining some topics in part I. The revisited topics are exploiting topological knowledge, constructing the minimum spanning trees, locality-based synchronizers and decomposition-based maximal independent set, hierarchical cluster-based routing, and regional directories for resource finding. Overall, the length of the book is just right. The presentation of the book and ideas presented are fine. The physical form of the book is good. There are good index and reference in the book. The materials covered in this book can be used for one-term graduate courses about the algorithms and theory in the distributed systems and computing, especially for the study of the locality sensitive approach. The book provides some exercises for study. Some knowledge of algorithm design and analysis and graph theory is required for readers. This book includes some up-to-date research results in the distributing computing. It can be a useful reference book for researcher in network architecture, discrete mathematics, and graph theory, and also for those who are interested in network architecture and design.