The theory and practice of concurrency control is the subject of this lucid new textbook. The material covers the field through about 1991 at a level of detail suitable for a graduate course, but it is written clearly enough for possible use in a fourth-year undergraduate seminar.
A concept is generally introduced with a short description that explains its purpose and its relationship to other concepts. Most concepts are formalized mathematically or in a program fragment and then explained or demonstrated through an example. These examples use accepted notation and a variety of familiar programming languages, such as Ada, Mesa, and Modula-2, which makes them both realistic and credible.
The first three chapters introduce fundamental concepts of synchronous and asynchronous behavior; formal semantics of sequential programs; and formal semantics of procedures, abstract data types, and coroutines. These chapters are primarily tutorial, but they provide the foundation for the precise analysis of concurrent behavior in the remainder of the book.
Chapter 4 reintroduces concurrency with an axiomatic treatment of interference, atomicity, and mutual exclusion. Chapter 5 covers monitors from several perspectives, including scheduling and efficiency. Chapters 6 and 7 formalize synchronous and asynchronous message-passing systems. Topics include deadlock, nondeterminism, datagrams, and virtual circuits.
Chapter 8 introduces remote procedure calls and performs a detailed axiomatic analysis of the Ada rendezvous, with implications for client and server processes. Perhaps the most important, and usually overlooked, concern in distributed systems is failure. Chapter 9 surveys this topic in some detail, although the axiomatic discussions supplement the lengthier operational descriptions here. The chapter explains a variety of reliability mechanisms, such as careful and stable storage, write-ahead logs, and Byzantine agreement.
The remainder of the book covers databases, a topic that is not properly a component of concurrent systems. Instead, it is perhaps the most exacting example of a concurrent system that could be presented. Chapter 10 introduces serializability and pessimistic and optimistic concurrency controls. Chapter11 explores transactions and nested transactions, distributed commitment, and abortion. Chapter 12 includes techniques for handling failures in distributed database management systems. It covers several two- and three-phase commit protocols, replication, quorums, and elections.
The book probably contains more material than can be covered in a semester, so the instructor may have to skip a few sections. Sections that may be safely skipped are marked with an asterisk, but this can also imply that the material is somehow unimportant. The authors’ experience in the field shows in their 142-reference bibliography, which includes a large fraction of the seminal publications in this rapidly evolving field. Just before each chapter’s exercises is a paragraph of bibliographic notes covering appropriate citations. The index seems to have been prepared with care, as have the exercises, which generally require some effort to solve. The illustrations, although adequate, are the weakest element. They could be both more plentiful and more attractive.
The book is written in simple, clear language and is filled with explanations, practical hints, and examples. Make no mistake: it is still a challenging text, written for well-qualified students. This approach is entirely appropriate because concurrency mechanisms designed without the benefit of formal reasoning are prone to subtle yet devastating errors.
