Concurrency & Parallelism¶
Tier: 1 (System Constraints)
Concepts: 14
Durability: Timeless (rooted in physical constraints of simultaneous execution and mathematical properties of ordering)
Fundamental Tensions¶
| Tension | Description |
|---|---|
| Safety vs. Liveness | Preventing races requires synchronization, but synchronization can cause deadlock. You cannot maximize both - stronger safety guarantees often reduce liveness. This tension is fundamental because any shared resource creates potential for both corruption (lack of safety) and starvation (lack of liveness). |
| Isolation vs. Performance | Complete isolation (copies, message passing) eliminates races but incurs overhead; sharing enables speed but requires coordination. The tension exists because copying data takes time, but so does synchronizing access. |
| Simplicity vs. Scalability | Coarse-grained locks are easy to reason about but limit parallelism; fine-grained or lock-free approaches scale better but are harder to prove correct. This is inherent because reasoning about interleaving grows combinatorially with concurrent entities. |
| Explicit vs. Implicit Coordination | Explicit synchronization (locks, channels) gives control but adds complexity; implicit approaches (immutability, confinement) are simpler but constrain design. Neither subsumes the other because some problems require mutation, others require flexibility. |
Concepts¶
- Concurrency vs. Parallelism Distinction
- Shared Mutable State as Root Hazard
- Race Condition
- Deadlock and the Coffman Conditions
- Mutual Exclusion and Critical Sections
- Synchronization Primitive Semantics
- Memory Visibility and Ordering
- Atomic Operations
- Lock-Free and Wait-Free Progress Guarantees
- Message Passing and Channel-Based Coordination
- Thread Confinement and Ownership
- Immutability as Concurrency Strategy
- Asynchronous Execution Pattern
- Granularity of Parallelism
Cross-Domain Transfer Summary¶
| This Domain Concept | Transfers To |
|---|---|
| Race condition | Distributed systems (TOCTOU), databases (isolation anomalies), file systems |
| Deadlock (Coffman conditions) | Distributed deadlock, resource allocation, workflow dependencies |
| Memory visibility/ordering | Distributed consistency models, database replication, CPU architecture |
| Message passing | Distributed systems, microservices, event-driven architecture |
| Immutability as strategy | Functional programming, event sourcing, version control, MVCC |
| Atomic operations | Distributed consensus, optimistic concurrency, cache coherence |
| Lock-free guarantees | Real-time systems, high-performance computing, OS kernels |
| Thread confinement | UI programming, resource lifecycle, single-writer patterns |
| Asynchronous execution | I/O systems, network programming, distributed RPC |
| Granularity of parallelism | MapReduce, GPU computing, distributed task scheduling |
Canonical Sources¶
| Source | Coverage |
|---|---|
| Coffman, Elphick & Shoshani, "System Deadlocks" (1971) | Definitive formulation of deadlock conditions |
| Dijkstra, "Solution of a Problem in Concurrent Programming Control" (1965) | Mutual exclusion problem, early synchronization |
| Hoare, "Monitors: An Operating System Structuring Concept" (1974) | Monitor primitive |
| Hoare, "Communicating Sequential Processes" (1978, 1985 book) | CSP model, channel-based concurrency |
| Hewitt, Bishop & Steiger, "A Universal Modular ACTOR Formalism" (1973) | Actor model foundations |
| Lamport, "Time, Clocks, and the Ordering of Events" (1978) | Happens-before, logical clocks, ordering |
| Herlihy, "Wait-Free Synchronization" (1991) | Lock-free/wait-free theory, consensus numbers |
| Herlihy & Shavit, "The Art of Multiprocessor Programming" (2008) | Comprehensive multiprocessor algorithms and theory |
| Goetz, "Java Concurrency in Practice" (2006) | Practical patterns (concepts transfer beyond Java) |
| Amdahl, "Validity of the Single Processor Approach" (1967) | Amdahl's Law, parallelism limits |
| Adve & Gharachorloo, "Shared Memory Consistency Models" (1996) | Memory models tutorial |
| Okasaki, "Purely Functional Data Structures" (1998) | Persistent/immutable data structures |