| |
| |
| Preface | |
| |
| |
| Key Features | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Concurrent and Distributed Computing | |
| |
| |
| |
| Data Communication and Synchronization | |
| |
| |
| |
| Contention, Cooperation, and Resource Allocation | |
| |
| |
| |
| Synchronization: Two Examples | |
| |
| |
| |
| Why is Synchronization Difficult? | |
| |
| |
| |
| Too Much Milk | |
| |
| |
| |
| The Coordinated Attack Problem | |
| |
| |
| |
| The Mutual Exclusion Problem | |
| |
| |
| |
| The Problem | |
| |
| |
| |
| Comments | |
| |
| |
| |
| Complexity Measures | |
| |
| |
| |
| Counting Steps | |
| |
| |
| |
| Counting Time Units | |
| |
| |
| |
| Counting Remote Memory Accesses | |
| |
| |
| |
| Space Complexity | |
| |
| |
| |
| Processes, Threads and Scheduling | |
| |
| |
| |
| Processes | |
| |
| |
| |
| Threads | |
| |
| |
| |
| Scheduling | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Mutual Exclusion Using Atomic Registers: Basic Topics | |
| |
| |
| |
| Algorithms for Two Processes | |
| |
| |
| |
| Peterson's Algorithm | |
| |
| |
| |
| Kessels' Single-writer Algorithm | |
| |
| |
| |
| Tournament Algorithms | |
| |
| |
| |
| A Solution Based on Peterson's Algorithm | |
| |
| |
| |
| A Solution Based on Kessels' Algorithm | |
| |
| |
| |
| A Fast Mutual Exclusion Algorithm | |
| |
| |
| |
| Lamport's Fast Algorithm | |
| |
| |
| |
| A Simple Observation | |
| |
| |
| |
| Starvation-free Algorithms | |
| |
| |
| |
| Basic Definitions | |
| |
| |
| |
| The Bakery Algorithm | |
| |
| |
| |
| The Black-White Bakery Algorithm | |
| |
| |
| |
| Tight Space Bounds | |
| |
| |
| |
| A Lower Bound | |
| |
| |
| |
| An Upper Bound: The One-bit Algorithm | |
| |
| |
| |
| Computing with Infinitely Many Processes | |
| |
| |
| |
| Automatic Discovery of Algorithms | |
| |
| |
| |
| Three Algorithms | |
| |
| |
| |
| More Results | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Mutual Exclusion Using Atomic Registers: Advanced Topics | |
| |
| |
| |
| Local Spinning Algorithms | |
| |
| |
| |
| Local Spinning | |
| |
| |
| |
| The Local Spinning Black-White Bakery Algorithm | |
| |
| |
| |
| A Local Spinning Tournament Algorithm | |
| |
| |
| |
| Adaptive Algorithms | |
| |
| |
| |
| Basic Definitions | |
| |
| |
| |
| A Simple Adaptive Algorithm | |
| |
| |
| |
| An Adaptive Tournament Algorithm | |
| |
| |
| |
| The Adaptive Black-White Bakery Algorithm | |
| |
| |
| |
| An Impossibility Result | |
| |
| |
| |
| Fault-tolerant Algorithms | |
| |
| |
| |
| Defining Fault-tolerance | |
| |
| |
| |
| A Fault-tolerant Algorithm | |
| |
| |
| |
| Self-stabilization | |
| |
| |
| |
| Symmetric Algorithms | |
| |
| |
| |
| Symmetric Deadlock-free Algorithms | |
| |
| |
| |
| Symmetric Starvation-free Algorithms | |
| |
| |
| |
| Observations about Concurrency | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Blocking and Non-blocking Synchronization | |
| |
| |
| |
| Synchronization Primitives | |
| |
| |
| |
| Atomic Operations | |
| |
| |
| |
| Objects | |
| |
| |
| |
| Non-atomic Registers | |
| |
| |
| |
| Collision Avoidance using Test-and-set Bits | |
| |
| |
| |
| A Trivial Deadlock-free Algorithm | |
| |
| |
| |
| Using a Test-and-test-and-set Bit | |
| |
| |
| |
| Collision Avoidance Locks | |
| |
| |
| |
| A Fast Starvation-free Algorithm | |
| |
| |
| |
| The Ticket Algorithm using RMW Objects | |
| |
| |
| |
| The Ticket Algorithm | |
| |
| |
| |
| A Simple Lower Bound | |
| |
| |
| |
| Local Spinning using Strong Primitives | |
| |
| |
| |
| Anderson's Queue-based Algorithm | |
| |
| |
| |
| Graunke and Thakkar Queue-based Algorithm | |
| |
| |
| |
| The MCS Queue-based Algorithm | |
| |
| |
| |
| Concurrent Data Structures | |
| |
| |
| |
| Non-blocking and Wait-free Synchronization | |
| |
| |
| |
| A Non-blocking Concurrent Queue Algorithm | |
| |
| |
| |
| Semaphores | |
| |
| |
| |
| Constant Space Starvation-free Algorithm | |
| |
| |
| |
| Correctness Proof | |
| |
| |
| |
| Monitors | |
| |
| |
| |
| Fairness of Shared Objects | |
| |
| |
| |
| Fairness Properties | |
| |
| |
| |
| Basic Results | |
| |
| |
| |
| Algorithms | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Barrier Synchronization | |
| |
| |
| |
| Barriers | |
| |
| |
| |
| Atomic Counter | |
| |
| |
| |
| A Simple Counter Barrier | |
| |
| |
| |
| A Local Spinning Counter Barrier | |
| |
| |
| |
| A Barrier without Shared Memory Initialization | |
| |
| |
| |
| Test-and-set Bits | |
| |
| |
| |
| A Constant Space Barrier | |
| |
| |
| |
| An Asymmetric Barrier without Memory Initialization | |
| |
| |
| |
| Combining Tree Barriers | |
| |
| |
| |
| A Tree-based Barrier | |
| |
| |
| |
| The Dissemination Barrier | |
| |
| |
| |
| The See-Saw Barrier | |
| |
| |
| |
| The Algorithm | |
| |
| |
| |
| Correctness Proof | |
| |
| |
| |
| Semaphores | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Problems | |
| |
| |
| |
| The l-exclusion Problem | |
| |
| |
| |
| The Problem | |
| |
| |
| |
| Algorithms Using Atomic Registers | |
| |
| |
| |
| An l-starvation-free Algorithm | |
| |
| |
| |
| An Unbounded FIFO-enabling Algorithm | |
| |
| |
| |
| Using a Single Read-modify-write Register | |
| |
| |
| |
| The Counter Algorithm | |
| |
| |
| |
| The Numbered Ticket Algorithm | |
| |
| |
| |
| The Unbounded Colored Ticket Algorithm | |
| |
| |
| |
| The Bounded Colored Ticket Algorithm | |
| |
| |
| |
| The l-assignment Problem | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Multiple Resources | |
| |
| |
| |
| Deadlocks | |
| |
| |
| |
| Deadlock Prevention | |
| |
| |
| |
| Two Phase Locking and Timestamping-ordering | |
| |
| |
| |
| The Total Order Theorem | |
| |
| |
| |
| Deadlock Avoidance: The Problem of Deadly Embrace | |
| |
| |
| |
| The Problem | |
| |
| |
| |
| The Banker's Algorithm | |
| |
| |
| |
| The Dining Philosophers Problem | |
| |
| |
| |
| The Problem | |
| |
| |
| |
| Preliminaries | |
| |
| |
| |
| Concurrency and Robustness | |
| |
| |
| |
| Hold and Wait Strategy | |
| |
| |
| |
| The LR Algorithm | |
| |
| |
| |
| The LLR Algorithm | |
| |
| |
| |
| A Lower Bound | |
| |
| |
| |
| Relating Concurrency and Robustness | |
| |
| |
| |
| Wait and Release Strategy | |
| |
| |
| |
| Randomized Algorithms | |
| |
| |
| |
| The Free Philosophers Algorithm | |
| |
| |
| |
| The Courteous Philosophers Algorithm | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Classical Synchronization Problems | |
| |
| |
| |
| The Producer-Consumer Problem | |
| |
| |
| |
| Atomic Registers | |
| |
| |
| |
| Atomic Counter | |
| |
| |
| |
| General Semaphores | |
| |
| |
| |
| Binary Semaphores | |
| |
| |
| |
| Monitors | |
| |
| |
| |
| Sleep and Wakeup | |
| |
| |
| |
| Readers and Writers | |
| |
| |
| |
| Semaphores | |
| |
| |
| |
| Monitors | |
| |
| |
| |
| The Sleeping Barber | |
| |
| |
| |
| The Cigarette Smoker's Problem | |
| |
| |
| |
| More Synchronization Problems | |
| |
| |
| |
| Group Mutual Exclusion and Room Synchronization | |
| |
| |
| |
| Concurrent Reading and Writing of Clocks | |
| |
| |
| |
| The Choice Coordination Problem | |
| |
| |
| |
| The H[subscript 2]O Problem | |
| |
| |
| |
| The Roller Coaster Problem | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Consensus | |
| |
| |
| |
| The Problem | |
| |
| |
| |
| Three Simple Consensus Algorithms | |
| |
| |
| |
| A Single 3-valued Read-modify-write Register | |
| |
| |
| |
| Two Processes, Two Read-modify-write Bits | |
| |
| |
| |
| Many Processes, Four Read-modify-write Bits | |
| |
| |
| |
| Consensus without Memory Initialization | |
| |
| |
| |
| The Algorithm | |
| |
| |
| |
| Correctness Proof | |
| |
| |
| |
| Reaching Consensus Using a Shared Queue | |
| |
| |
| |
| Impossibility of Consensus with One Faulty Process | |
| |
| |
| |
| A Formal Model | |
| |
| |
| |
| Basic Observations | |
| |
| |
| |
| The Impossibility Theorem | |
| |
| |
| |
| The Relative Power of Synchronization Primitives | |
| |
| |
| |
| The Universality of Consensus | |
| |
| |
| |
| Basic Definitions | |
| |
| |
| |
| A Universal Construction | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Timing-based Algorithms | |
| |
| |
| |
| Timing-based Systems | |
| |
| |
| |
| Mutual Exclusion with Known Delays | |
| |
| |
| |
| Fast Mutual Exclusion with Known Delays | |
| |
| |
| |
| The Algorithm | |
| |
| |
| |
| Correctness Proof | |
| |
| |
| |
| Consensus with Known Delays | |
| |
| |
| |
| Fast Consensus with Known Delays | |
| |
| |
| |
| The Algorithm | |
| |
| |
| |
| Correctness Proof | |
| |
| |
| |
| Fast Consensus with Unknown Delays | |
| |
| |
| |
| The Algorithm | |
| |
| |
| |
| Correctness Proof | |
| |
| |
| |
| Fast Mutual Exclusion with Unknown Delays | |
| |
| |
| |
| The Algorithm | |
| |
| |
| |
| Correctness Proof | |
| |
| |
| |
| Time Complexity | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Problems | |
| |
| |
| Bibliography | |
| |
| |
| Index | |