zbMATH — the first resource for mathematics

Distributed algorithms. (English) Zbl 0877.68061
Morgan Kaufmann Series in Data Management Systems. San Francisco, CA: Morgan Kaufmann. xxiii, 872 p. (1996).
Distributed information processing arises in a wide range of network applications and nowadays attracts much attention. The reviewed book is an up-to-date complete guide to the theory of distributed algorithms. There are three different network timing models for which distributed algorithms are designed, the synchronous, the asynchronous and the partially synchronous model. In each such model a number of important algorithms is thoroughly considered by the author. For the synchronous model they are: a leader election in a ring, breadth-first search, shortest paths, maximal independent set, reaching consensus with link and process failures. The second largest part of the book is devoted to the asynchronous model. Distributed algorithms which are discussed for this model are the following: mutual exclusion, resource-allocation problem including generalizations of the dining philosophers problem, atomic objects, election of a leader, synchronizers, shared memory versus networks, logical time for asynchronous networks, stable properties, data links protocol. The third part of the book deals with partially synchronous algorithms.
All algorithms are mathematically verified and complexity valuations for them are given.
The book is well written and could be used as a textbook for students or a guide for researchers.

68W10 Parallel algorithms in computer science
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science