Distributed computing. A locality-sensitive approach.

*(English)*Zbl 0959.68042
SIAM Monographs on Discrete Mathematics and Applications, 5. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. xvi, 343 p. (2000).

The book brings together all important knowledge on the locality-sensitive approach to distributed computing obtained during the last twenty years. The approach is provided iteratively in four steps corresponding to Introduction, Part I, Part II and Part III of the book, respectively. In the Introduction is a short review of issues and features that distinguish central computing from distributed one, and the first touch with locality-sensitive distributed algorithms is given.

Part I is the next step to develop a locality including methodology for distributed network algorithms. As such, Part I provides an introductory exposition of these topics: distributed network model, broadcast and convergecast, downcasts and upcasts, tree construction, synchronizers, vertex coloring, maximal independent sets, message routing, and local queries and local resource finding.

The next step in the development of the locality sensitive methodology is described in Part II and its essence is to define Locality-Preserving (LP) network representations and to develop techniques for their constructions. In this part three types of LP-representation (cluster based representations, skeletal representations, and vertex labeling representation) are discussed. As a theoretical tool supporting an effective solving of the representation problems is a chosen graph-theoretic scheme. The third step in the development of the above-mentioned methodology is to integrate the results of the two previous steps. The results are: distributed network algorithms, and LP-representations. Part III of the book describes the third step of the methodology development and its contents are distributed constructions and applications of LP-representations.

The book is a needed one. It is very well structured. It is a precise text that is very suggestive for undergraduates and graduates students. The book is very helpful for practitioners and researchers, too.

Part I is the next step to develop a locality including methodology for distributed network algorithms. As such, Part I provides an introductory exposition of these topics: distributed network model, broadcast and convergecast, downcasts and upcasts, tree construction, synchronizers, vertex coloring, maximal independent sets, message routing, and local queries and local resource finding.

The next step in the development of the locality sensitive methodology is described in Part II and its essence is to define Locality-Preserving (LP) network representations and to develop techniques for their constructions. In this part three types of LP-representation (cluster based representations, skeletal representations, and vertex labeling representation) are discussed. As a theoretical tool supporting an effective solving of the representation problems is a chosen graph-theoretic scheme. The third step in the development of the above-mentioned methodology is to integrate the results of the two previous steps. The results are: distributed network algorithms, and LP-representations. Part III of the book describes the third step of the methodology development and its contents are distributed constructions and applications of LP-representations.

The book is a needed one. It is very well structured. It is a precise text that is very suggestive for undergraduates and graduates students. The book is very helpful for practitioners and researchers, too.

Reviewer: E.Kostolansky (Bratislava)

##### MSC:

68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |

68-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science |

68M14 | Distributed systems |

68W15 | Distributed algorithms |