Concurrent Computing

Concurrent computing is the execution of multiple computation streams whose lifetimes overlap — not merely in parallel on multiple processors, but interleaved on a single processor, cooperative in a distributed system, or racing in a shared-memory architecture. The defining challenge of concurrency is not performance but correctness: ensuring that the interleaving of operations produces results consistent with some sequential specification. Dijkstra's invention of semaphores in the 1960s was the first systematic attempt to discipline this interleaving, but it was only the beginning. Modern concurrency encompasses lock-free data structures, actor models, software transactional memory, and eventual consistency — each representing a different trade-off between programmer productivity, runtime efficiency, and verifiability.

The emergence of multicore processors in the 2000s transformed concurrency from a specialist concern into a universal requirement. Yet the tools for reasoning about concurrent programs — separation logic, rely-guarantee reasoning, concurrent separation logic — remain far behind the tools for sequential programs. This gap is not accidental. Concurrency exposes the fundamental limits of compositional reasoning: two correct programs, composed concurrently, may produce an incorrect system.