Tel G. Introduction to Distributed Algorithms

Tel G. Introduction to Distributed Algorithms
Cambridge University Press, 2000. — 610.Distributed systems and distributed information processing have received considerable attention in the past few years, and almost every university offers at least one course on the design of distributed algorithms. There exist a large number of books about principles of distributed systems; see for example Tanenbaum or Sloman and Kramer, but these concentrate on architectural aspects rather than on algorithms. Since the first edition of this book, other texts on distributed algorithms have been published by Barbosa, Lynch , and Attiya and Welch. It has been remarked that algorithms are the backbone of every computer application; therefore a text devoted solely to distributed algorithms seems to be justified. The aim of this book is to present a large body of theory about distributed algorithms, which has been developed over the past twenty years or so. This book can be used as a textbook for a one- or two-semester course on distributed algorithms; the teacher of a one-semester course may select topics to his own liking.
The book will also provide useful background and reference information for professional engineers and researchers working with distributed systems.Introduction: Distributed Systems
Part One: Protocols
The Model
Communication Protocols
Routing Algorithms
Deadlock-free Packet Switching
Part Two: Fundamental Algorithms
Wave and Traversal Algorithms
Election Algorithms
Termination Detection
Anonymous Networks
Snapshots
Sense of Direction and Orientation
Synchrony in Networks
Part Three: Fault Tolerance
Fault Tolerance in Distributed Systems
Fault Tolerance in Asynchronous Systems
Fault Tolerance in Synchronous Systems
Failure Detection
Stabilization
Part Four: Appendices
A: Pseudocode Conventions
B: Graphs and Networks