Topics in distributed algorithms. (English) Zbl 0755.68062

Cambridge International Series on Parallel Computation. 1. Cambridge, UK etc.: Cambridge University Press. X, 240 p. (1990).
The book presents a collection of recent computer algorithms and protocols used in distributed computing and distributed system implementation. It is about the structure, the design, and the verification of such algorithms.
An distributed algorithm executes as a collection of sequential processes, all executing their part of the algorithm independently, but coordinating their activity through communication. In the book the processes are communicating by message exchanges, bot through shared memory.
Chapter 1 contains a historical overview of the scientifical and technical developments which led to research in distributed algorithms. Also an overview is given of current research topics in this field. Chapter 2 deals with the problem of network synchronisation in synchronous bounded delay networks. Chapter 3 is a case study in program verification. Here a verification method described by invariants is considered. The method is applied to two distributed algorithms (communication protocol proposed by Fletcher and Watson and an algorithm by Mattern). Chapter 4 is devoted to modular design of distributed algorithms. A large class of algorithms for the distributed infimum approximation problem is described. Chapter 5 examines the structure of distributed algorithms for garbage collection. It is shown that such algorithms can be obtained by superimposing a termination detection algorithm on a collection of simple processes.
Because of the clear representation and the detailed register the book is a valuable introduction and reference for the topic of distributed algorithms.
Reviewer: B.Zaddach


68W15 Distributed algorithms
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science