Concurrent Programming: Algorithms, Principles, and Foundations: Algorithms, Principles, and Foundations

Description

The advent of new architectures and computing platforms means that synchronization and concurrent computing are among the most important topics in computing science. Concurrent programs are made up of cooperating entities -- processors, processes, agents, peers, sensors -- and synchronization is the set of concepts, rules and mechanisms that allow them to coordinate their local computations in order to realize a common task. This book is devoted to the most difficult part of concurrent programming, namely synchronization concepts, techniques and principles when the cooperating entities are asynchronous, communicate through a shared memory, and may experience failures. Synchronization is no longer a set of tricks but, due to research results in recent decades, it relies today on sane scientific foundations as explained in this book. In this book the author explains synchronization and the implementation of concurrent objects, presenting in a uniform and comprehensive way the major theoretical 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. The book is suitable for advanced undergraduate students and graduate students in computer science or computer engineering, graduate students in mathematics interested in the foundations of process synchronization, and practitioners and engineers who need to produce correct concurrent software. The reader should have a basic knowledge of algorithms and operating systems. Front Matter....Pages i-xxxii Front Matter....Pages 1-1 The Mutual Exclusion Problem....Pages 3-13 Solving Mutual Exclusion....Pages 15-60 Lock-Based Concurrent Objects....Pages 61-109 Front Matter....Pages 111-111 Atomicity: Formal Definition and Properties....Pages 113-132 Front Matter....Pages 133-133 Mutex-Free Concurrent Objects....Pages 135-164 Hybrid Concurrent Objects....Pages 165-187 Wait-Free Objects from Read/Write Registers Only....Pages 189-218 Snapshot Objects from Read/Write Registers Only....Pages 219-248 Renaming Objects from Read/Write Registers Only....Pages 249-273 Front Matter....Pages 275-275 Transactional Memory....Pages 277-301 Front Matter....Pages 303-303 Safe, Regular, and Atomic Read/Write Registers....Pages 305-328 From Safe Bits to Atomic Bits: Lower Bound and Optimal Construction....Pages 329-345 Bounded Constructions of Atomic b -Valued Registers....Pages 347-368 Front Matter....Pages 369-369 Universality of Consensus....Pages 371-397 The Case of Unreliable Base Objects....Pages 399-420 Consensus Numbers and the Consensus Hierarchy....Pages 421-447 The Alpha(s) and Omega of Consensus: Failure Detector-Based Consensus....Pages 449-488 Back Matter....Pages 489-515