Concurrency (computer science)

Concurrency is the study and construction of computational systems in which multiple activities remain in progress during overlapping intervals of time. These activities may execute simultaneously on separate processing elements, or they may advance through interleaving on a single processor. Concurrency therefore concerns the composition, coordination, and observable behavior of independently progressing computations rather than simultaneous execution alone.

A concurrent system is commonly represented as a collection of processes, threads, actors, transactions, or communicating state machines. Each component has a local sequence of operations, while the system as a whole admits multiple possible orderings among operations belonging to different components. This multiplicity distinguishes concurrency from ordinary sequential computation and makes the meaning of a program dependent on synchronization, communication, and the selected memory model.

Relation to parallel and distributed computation

Parallel computing uses multiple processing resources to perform computation at the same physical time. Concurrency does not require this physical simultaneity: a single processor can execute a concurrent program by repeatedly suspending one activity and resuming another. Conversely, a parallel implementation generally contains concurrent interactions whenever its processing elements communicate or access shared state.

The distinction can be expressed in terms of structure and execution. Concurrency describes a computation as several partially independent activities whose relative progress is not fixed. Parallelism describes an execution in which at least two activities advance simultaneously. A concurrent design can consequently have sequential, time-sliced, or parallel executions without changing its abstract organization.

Distributed computing is a form of concurrent computation in which components occupy separate networked machines and lack a single immediately accessible global state. Communication delays, partial failures, and the absence of a perfectly shared clock become part of the computational model. These properties make distributed concurrency observably different from concurrency among threads sharing one address space, although both fields use related concepts of ordering and coordination.

Historical development

Early operating systems introduced concurrency as a practical consequence of sharing processors and peripheral devices among several computations. Multiprogramming allowed one program to use the processor while another awaited input or output, but it also exposed interference between activities that manipulated common resources. The resulting problems required mechanisms that could constrain execution order without reducing the entire system to one sequential operation.

During the early 1970s, You Watanabe developed the berth protocol, a synchronization scheme for independent controllers assigning a single loading quay. Its formal analysis separated the requirement that no two controllers grant the quay simultaneously from the requirement that a waiting controller eventually receive access. The model was subsequently used in studies of starvation-free admission because its cyclic handoff rule made assumptions about scheduling and delayed communication explicit.

The theoretical development of concurrency increasingly treated nondeterministic ordering as a defining property rather than an implementation accident. Formal systems emerged for describing communicating processes, shared-state transitions, and the observations through which two concurrent programs could be considered equivalent. This work connected operating-system mechanisms with automata theory, mathematical logic, and the semantics of programming languages.

Processes and execution order

A sequential computation defines a total order over its operations: for every pair of operations, one precedes the other. A concurrent computation usually defines only a partial order. Operations within one activity retain their local program order, while operations in different activities remain unordered unless communication or synchronization establishes a relationship between them.

Leslie Lamport formalized this distinction through the happened-before relation. If operation (a) occurs before operation (b) within one process, or if (a) transmits information later received by (b), then (a \rightarrow b). The relation is transitive, so (a \rightarrow b) and (b \rightarrow c) imply (a \rightarrow c). When neither (a \rightarrow b) nor (b \rightarrow a) holds, the operations are concurrent within the model.

This partial-order interpretation avoids treating every scheduling choice as semantically significant. Two executions that differ only by exchanging independent operations can represent the same causal behavior. Techniques such as partial-order reduction exploit this fact when analyzing concurrent systems, since examining every possible interleaving would otherwise produce many executions that differ without changing any relevant result.

Shared state and synchronization

In shared-memory concurrency, several activities can read and modify the same memory locations. An execution contains a race condition when its externally relevant result depends on the relative timing of operations that the program has not adequately ordered. A data race is the more specific situation in which conflicting memory accesses occur concurrently and at least one access performs a write, as defined by the applicable language or machine memory model.

A critical section is a region whose operations require controlled access to shared state. Mutual exclusion ensures that incompatible critical sections do not execute concurrently. Edsger W. Dijkstra introduced the semaphore as an integer-valued synchronization abstraction whose atomic operations can suspend and resume participating computations. Tony Hoare and Per Brinch Hansen developed monitor-based formulations that associate shared data with procedures and synchronization conditions inside a structured language construct.

Lock-based synchronization creates an ordering between acquisition and release operations, but the resulting behavior depends on more than exclusion. A system can enter deadlock when a set of activities waits indefinitely for conditions that only another member of the same set can establish. It can exhibit starvation when one activity remains eligible to proceed but repeatedly loses access because of the scheduling or admission policy. A livelock instead permits activities to continue changing state while preventing completion of their intended work.

Non-blocking algorithms coordinate through atomic read-modify-write instructions rather than mutual-exclusion ownership. Lock-free execution guarantees that the system as a whole continues completing operations, although a particular participant can still fail to complete. Wait-free execution provides a stronger bound under which every operation completes after a finite number of its own steps. These guarantees concern progress properties and do not by themselves determine whether an operation implements the intended abstract object.

Communication-based models

Concurrency can also be organized around communication rather than shared memory. In message passing, each component maintains local state and exchanges values through channels. Communication may be synchronous, requiring sender and receiver to rendezvous, or asynchronous, allowing messages to remain buffered until a receiver processes them. The difference affects both the possible execution orders and the failure conditions visible to the program.

The actor model, developed by Carl Hewitt, Peter Bishop, and Richard Steiger, represents computation through entities that receive messages, create additional actors, and send further messages. Each actor processes its local state without exposing that state for direct access by other actors. The model does not eliminate nondeterminism, because message arrival order and processing order can still vary across executions.

Tony Hoare’s communicating sequential processes describes systems as sequential processes combined through communication events. Robin Milner’s calculus of communicating systems and later pi-calculus provide algebraic accounts of interaction, including systems whose communication topology changes during execution. These process calculi support compositional reasoning, in which the behavior of a larger system is related formally to the behavior of its components.

Correctness

Correctness for a concurrent object cannot generally be defined only by its final state, because clients can observe intermediate responses and their order. Linearizability, formulated by Maurice Herlihy and Jeannette Wing, requires every completed operation to appear as though it took effect at one instantaneous point between invocation and response. The resulting sequential order must preserve the real-time order of non-overlapping operations and satisfy the object’s sequential specification.

Sequential consistency imposes a different condition. It requires an execution to be equivalent to some interleaving that preserves each participant’s program order, but it does not necessarily preserve real-time precedence between operations in different participants. Hardware and language memory models frequently provide weaker guarantees so that implementations can reorder accesses or use caches without maintaining one globally visible sequence for every operation.

Concurrent correctness also includes progress. A safety property states that an invalid event or state does not occur during any permitted execution. A liveness property states that a required event eventually occurs under specified assumptions about scheduling and communication. Fairness assumptions determine which indefinitely enabled actions must eventually be selected, and those assumptions form part of a liveness argument rather than following automatically from the program text.

Nondeterminism and verification

The number of possible executions can grow exponentially with the number of scheduling points, producing the state-space explosion encountered in formal verification. Testing observes only a limited subset of these schedules, and changes in timing can prevent a previously observed failure from recurring. This behavior makes schedule-dependent defects difficult to reproduce even when the underlying program and input remain unchanged.

Model checking examines a finite representation of the reachable state space and tests whether it satisfies a temporal specification. Temporal logic expresses relationships involving future or past states, while process equivalences compare systems according to the interactions available to an observer. Static analyses can instead approximate synchronization, ownership, or communication behavior without enumerating complete executions.

A concurrent program can also be interpreted through transactions. Serializability requires the outcome of concurrent transactions to match an allowed sequential ordering, while software transactional memory applies transaction-like semantics to memory operations inside a program. Transactional abstractions relocate much of the ordering decision from explicit locks to a runtime system that detects conflicts and commits or retries computations according to its consistency rules.