Neither a reference work, a "recipe" book, a review of the field, or even a traditional textbook, Distributed Algorithms is that rare thing, a book that teaches a way of thinking. It does cover a wide range of different algorithms, but it focuses on the skills and techniques needed to understand, model, and prove statements about them, rather than on the properties of individual algorithms. I have avoided the field since I aborted my PhD thesis five years ago, but Distributed Algorithms reminded me why I was originally attracted to it. It is not a book for everyone, not even for all students of distributed algorithms, but for those seeking a deep understanding of formal methods it offers an uniquely rewarding experience.

Distributed Algorithms is divided into four parts, covering synchronous shared memory, asynchronous shared memory, asynchronous network, and partially synchronous algorithms. Each part begins with the presentation of a formal model for the class of algorithms, but this can be skipped and referred to as necessary. The meat of each part consists of an introduction to fundamental problems, along with algorithms for their solution and proofs of correctness (or impossibility results as appropriate). Consensus, atomic objects, mutual exclusion, leader election and minimum spanning trees, synchronizers, logical time and global snapshots, failure detection, and reliable FIFO communication channels are just some of the topics covered.

Integrated into this is the development of a sophisticated collection of tools and methods for proofs and modelling: simulation relations, invariants, automata and composition of automata, and transformations between the different formalisms and models. Lynch is particularly strong on the connections between different problems, models, and algorithms: ways of synchronizing asynchronous networks, for example, allowing synchronous algorithms to be "ported", or transformation results between asynchronous network and asynchronous shared memory systems. Finally, each of the twenty five chapters has an extensive set of exercises, which range from the completion of trivial steps omitted from proofs to serious research problems.

Apart from the occasional sub-section which uses algebraic topology, Markov-style probabilistic analysis, or other esoterica, the mathematics required by Distributed Algorithms is actually quite minimal. It does, however, assume a solid general competence with formal reasoning and a basic familiarity with analysis of algorithms. Connections to practical applications are mentioned only in passing, if at all — the asynchronous Bellman-Ford algorithm, for example, is presented without even a mention that it forms the basis for important real-life routing algorithms. But for those with a computer science background applications of this kind will be obvious, while for readers with a more narrowly mathematical background the elegance and beauty of the results should be motivation and reward enough.

January 1999

External links:

- buy from Amazon.com or Amazon.co.uk

Related reviews:

- books about computer science
- books about mathematics
- books published by Morgan Kaufmann