Concurrent Programming: Algorithms, Principles, and Foundations

In this book the author explains synchronization and the implementation of concurrent objects, presenting in a uniform and comprehensive way the majortheoretical and practical results of the past 30 years. Among the key features of the book are a new look at lock-based synchronization (mutual exclusion, semaphores, monitors, path expressions); an introduction to the atomicity consistency criterion and its properties and a specific chapter on transactional memory; an introduction to mutex-freedom and associated progress conditions such as obstruction-freedom and wait-freedom; a presentation of Lamport's hierarchy of safe, regular and atomic registers and associated wait-free constructions; a description of numerous wait-free constructions of concurrent objects (queues, stacks, weak counters, snapshot objects, renaming objects, etc.); a presentation of the computability power of concurrent objects including the notions of universal construction, consensus number and the associated Herlihy's hierarchy; and a survey of failure detector-based constructions of consensus objects.

Part I - Lock-Based Synchronization.- Chap. 1 - The Mutual Exclusion Problem.- Chap. 2 - Solving Mutual Exclusion.- Chap. 3 - Lock-Based Concurrent Objects.- Part II - On the Foundations Side: The Atomicity Concept.- Chap. 4 - Atomicity: Formal Definition and Properties.- Part III - Mutex-Free Synchronization.- Chap. 5 - Mutex-Free Concurrent Objects.- Chap. 6 - Hybrid Concurrent Objects.- Chap. 7 - Wait-Free Objects from Read/Write Registers Only.- Chap. 8 - Snapshot Objects from Read/Write Registers Only.- Chap. 9 - Renaming Objects from Read/Write Registers Only.- Part IV - The Transactional Memory Approach.- Chap. 10 - Transactional Memory.- Part V - On the Foundations Side: From Safe Bits to Atomic Registers.- Chap. 11 - Safe, Regular and Atomic Read/Write Registers.- Chap. 12 - From Safe Bits to Atomic Bits: A Lower Bound and an Optimal Construction.- Chap. 13 - Bounded Constructions of Atomic b-Valued Registers.- Part VI - On the Foundations Side: The Computability Power of Concurrent Objects (Consensus).- Chap. 14 - Universality of Consensus.- Chap. 15 - The Case of Unreliable Base Objects.- Chap. 16 - Consensus Numbers and the Consensus Hierarchy.- Chap. 17 - The Alphas and Omega of Consensus: Failure Detector-Based Consensus.- Afterword.- Bibliography.- Index.