Barbosa V.C. An Introduction to Distributed Algorithms

MIT Press, 1996. — 370.This book presents an introduction to some of the main problems, techniques, and algorithms underlying the programming of distributed-memory systems, such as computer networks, networks of workstations, and multiprocessors. It is intended mainly as a textbook for advanced undergraduates or first-year graduate students in computer science and requires no specific background beyond some familiarity with basic graph theory, although prior exposure to the main issues in concurrent programming and computer networks may also be helpful. In addition, researchers and practitioners working on distributed computing will also find it useful as a general reference on some of the most important issues in the field.
The material is organized into ten chapters covering a variety of topics, such as models of distributed computation, information propagation, leader election, distributed snapshots, network synchronization, self-stability, termination detection, deadlock detection, graph algorithms, mutual exclusion, program debugging, and simulation. Because I have chosen to write the book from the broader perspective of distributed-memory systems in general, the topics that I treat fail to coincide exactly with those normally taught in a more orthodox course on distributed algorithms. What this amounts to is that I have included topics that normally would not be touched (as algorithms for maximum flow, program debugging, and simulation) and, on the other hand, have left some topics out (as agreement in the presence of faults).
All the algorithms that I discuss in the book are given for a "target" system that is represented by a connected graph, whose nodes are message-driven entities and whose edges indicate the possibilities of point-to-point communication. This allows the algorithms to be presented in a very simple format by specifying, for each node, the actions to be taken to initiate participating in the algorithm and upon the receipt of a message from one of the nodes connected to it in the graph. In describing the main ideas and algorithms, I have sought a balance between intuition and formal rigor, so that most are preceded by a general intuitive discussion and followed by formal statements regarding correctness, complexity, or other properties.Part 1 Fundamentals
Message-Passing Systems
Intrinsic Constraints
Models of Computation
Basic Algorithms
Basic Techniques
Part 2 Advances and Applications
Stable Properties
Graph Algorithms
Resource Sharing
Program Debugging
Simulation