*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