next up previous
Next: Useful Book for researchers, Up: Book Review Previous: In General About the

Chapter Content

The book is organized into ten chapters, a Bibliography with 345 entries, and a comprehensive Index. The content of each chapter is as follows:

Chapter 1 (Introduction, pp.1-29) provides some important background for the rest of the chapters. It tries to define the set of topics that are at the center of concurrent and distributed programming. In the rest it explains the needs for involving synchronization, mutual exclusion, and complexity measures. At the end it briefly discusses a few basic technical issues regarding processes, threads, and scheduling.

Chapter 2 (Mutual Exclusion Using Atomic Registers: Basic Topics, pp.31-96) looks at mutual exclusion phenomenon as one of the best paradigms of the difficulties associated with concurrent and distributed programming. The discussion begins with description of two algorithms that are used to solve the mutual exclusion problem of two processes. Next, more details concerning constructions of tournament algorithms, fast mutual exclusion algorithm, starvation-free algorithm, tight space bounds, and automatic discovery of algorithms, are given.

Chapter 3 (Mutual Exclusion Using Atomic Registers: Advanced Topics, pp.97-146) concentrates on advanced concepts related to using mutual exclusion. The hottest topics considered here are with detailed explanations of local spinning algorithms, adaptive algorithms, fault-tolerant algorithms (algorithms that are immune to some type of process failures), and symmetric algorithms.

Chapter 4 (Blocking and Non-blocking Synchronization, 147-202) concentrates on crucial problems related to synchronization. The main themes considered here are with synchronization primitives, collision avoidance using test-and-set-bits, the ticket algorithm using read-modify-write objects, local spinning using strong primitives, concurrent data structures, semaphores, monitors, and fairness of shared data.

Chapter 5 (Barrier Synchronization, pp.203-225) studies barrier as a coordination mechanism that forces processes which participate in a concurrent algorithm to wait until each of them has reached a certain point in its program. Interesting details concerning implementations of barriers including atomic counter, a constant space barrier, combining tree barriers, a tree-based barrier, and a barrier for two processes using two binary semaphores, are given.

Chapter 6 (The $ \ell$ -exclusion Problem, pp.227-248) describes the $ \ell$ -exclusion problem as a natural generalization of the mutual exclusion problem, and shows how to design algorithm which generates up to $ \ell$ processes that may simultaneously access identical copies of the same non-sharable resource when there are several competing processes. The discussion includes details about algorithms using atomic registers, algorithms using a single read-modify-write register, and the $ \ell$ -assignment problem.

Chapter 7 (Multiple Resources, pp.249-280) begins the discussion with a deadlock as a state in which two or more processes are waiting for each other, in a so-called deadly embrace. The problems of deadlock prevention and deadlock avoidance are considered. Next, the dinning philosophers problem which models the allocation of multiple resources in a distributed system is presented. In the rest, interesting details related to realization of hold and wait strategy and release strategy, and randomized algorithms, are given.

Chapter 8 (Classical Synchronization Problems, pp.281-305) is devoted to the interaction between processes that control the order in which the processes execute. The main themes considered here are with the producer-consumer problem as a classical cooperation problem, reader and writer problem, the sleeping barber problem, the cigarette smoker's problem, and a group of additional synchronization problems.

Chapter 9 (Consensus, pp.397-341) describes how to design an algorithm in which all correct processes reach a common decision based on their initial opinions. At the start three simple consensus algorithms are presented. Next, convenient solutions related to solution of the consensus problem including consensus without memory initialization, reaching consensus using a shared queue, and impossibility of consensus with one faulty process are discussed. In the rest, more details concerning the relative power of synchronization primitives and the universality of consensus are given.

Chapter 10 (Timing-based Algorithms, pp.343-371) points to the fact that the complexity of synchronization in a concurrent environment depends on timing assumptions. It focuses on a timing-based system which provides an interesting abstraction of the timing details of concurrent systems. The main topics considered here are with mutual- and fast mutual-exclusion with known delays, consensus- and fast consensus-with known delays, fast consensus- and fast mutual exclusion-with unknown delays.


next up previous
Next: Useful Book for researchers, Up: Book Review Previous: In General About the
root 2007-05-01