Raynal M. Distributed Algorithms for Message-Passing Systems

Springer, 2013. — 517 p.The aim of this book is to present in a comprehensive way basic notions, concepts and algorithms of distributed computing when the distributed entities cooperate by sending and receiving messages on top of an underlying network. In this case, the main difficulty comes from the physical distribution of the entities and the asynchrony of the environment in which they evolve.
This book covers algorithms, basic principles, and foundations of message-passing programming, i.e., programs where the entities communicate by sending and receiving messages through a network. The world is distributed, and the algorithmic thinking suited to distributed applications and systems is not reducible to sequential computing. Knowledge of the bases of distributed computing is becoming more important than ever as more and more computer applications are now distributed. The book is composed of six parts.Part I Distributed Graph Algorithms
Basic Definitions and Network Traversal Algorithms
Distributed Graph Algorithms
An Algorithmic Framework to Compute Global Functions on a Process Graph
Leader Election Algorithms
Mobile Objects Navigating a Network
Part II Logical Time and Global States in Distributed Systems
Nature of Distributed Computations and the Concept of a Global State
Logical Time in Asynchronous Distributed Systems
Asynchronous Distributed Checkpointing
Simulating Synchrony on Top of Asynchronous Systems
Part III Mutual Exclusion and Resource Allocation
Permission-Based Mutual Exclusion Algorithms
Distributed Resource Allocation
Part IV High-Level Communication Abstractions
Order Constraints on Message Delivery
Rendezvous (Synchronous) Communication
Part V Detection of Properties on Distributed Executions
Distributed Termination Detection
Distributed Deadlock Detection
Part VI Distributed Shared Memory
Atomic Consistency (Linearizability)
Sequential Consistency