Concurrency (Computer Science)

Reference entry · last updated September 7, 2026

Concurrency is the composition and management of independently executing computations whose execution lifetimes overlap in time. While parallelism concerns the simultaneous physical execution of tasks on distinct hardware units, concurrency is a structural property of software design that enables a system to make progress on multiple concerns through non-deterministic interleaving, cooperative yielding, or preemptive scheduling. Concurrency enables operating systems, database engines, event-driven web servers, and distributed multi-agent systems to handle asynchronous input/output (I/O), maintain interface responsiveness, and coordinate shared resources.

1. First Principles: The Structural Nature of Concurrency

A system is concurrent if two or more state sequences \(S_1 = (s_{1,1}, s_{1,2}, \dots)\) and \(S_2 = (s_{2,1}, s_{2,2}, \dots)\) make progress across a shared time interval \([t_{\text{start}}, t_{\text{end}}]\), such that the exact order of operation execution is non-deterministic. This non-determinism distinguishes concurrent programming from sequential programming: program correctness cannot assume an invariant total ordering of events.

Concurrency can execute on a single CPU core via an event loop or preemptive scheduler that interleaves process time slices. When multiple physical cores are available, a concurrent program may additionally execute in parallel, but concurrency itself remains an architectural separation of concerns rather than a hardware speedup mechanism [5].

2. Formal Models of Concurrency

Computer scientists have formulated algebraic and behavioral models to specify and verify concurrent interactions mathematically.

2.1 Communicating Sequential Processes (CSP)

Proposed by C. A. R. Hoare in 1978, CSP models concurrent systems as independent sequential processes that interact exclusively by exchanging messages over synchronous, unbuffered channels [2]. In CSP, communication is a rendezvous: the sender blocks until the receiver is ready, and the receiver blocks until the sender emits data. CSP forms the theoretical underpinning of the channel primitives in Occam, Limbo, and Go.

2.2 The Actor Model

Formulated by Carl Hewitt, Peter Bishop, and Richard Steiger in 1973, the Actor Model treats the "actor" as the universal primitive of concurrent computation [3]. An actor encapsulates private state, a mailbox queue, and a behavior function. In response to an incoming message, an actor can concurrently:

• Send a finite number of messages to other actors with known addresses.
• Create a finite number of new actors.
• Designate the behavior to be used for the next message it receives.

Unlike CSP's synchronous channels, actors communicate via asynchronous message passing with unbounded mailboxes, eliminating shared mutable memory and providing fault isolation (exemplified by Erlang, Elixir/OTP, and Akka).

3. Synchronization and Coordination Primitives

Concurrent execution requires coordination mechanisms to maintain data invariants across overlapping computations.

3.1 Shared Memory, Mutexes, and Semaphores

In shared-memory environments, multiple threads share a single address space. Edsger W. Dijkstra introduced the semaphore in 1965 as an integer variable \(S\) accessed only through two atomic operations: \(P(S)\) (wait / decrement) and \(V(S)\) (signal / increment) [1]:

• Binary Semaphore / Mutual Exclusion Lock (Mutex): Restricts access to a critical section of code to exactly one executing thread at a time.
• Counting Semaphore: Regulates access to a finite pool of identical resources.
• Condition Variables and Monitors: Pair a mutex with a wait queue, allowing threads to suspend execution until a specific predicate condition is signaled by another thread.

3.2 Message-Passing and Channels

Message-passing avoids shared state by transferring ownership of data across communication queues. Channels can be unbuffered (synchronous handoff) or buffered (asynchronous FIFO queue with capacity \(C\)). Message-passing aligns with the design principle: "Do not communicate by sharing memory; instead, share memory by communicating."

3.3 Lock-Free and Atomic Primitives

Locks introduce overhead, priority inversion, and potential deadlock. Lock-free data structures rely on hardware-supported atomic read-modify-write instructions, predominantly Compare-and-Swap (CAS) [6]:

A CAS operation atomically compares the contents of a memory location to an expected value; only if they are equal does it update the location to the new value. If another thread modified the location concurrently, the operation fails cleanly, allowing the calling algorithm to retry.

4. Classical Hazards and Failure Modes

The non-deterministic interleaving of concurrent tasks introduces several fundamental classes of runtime bugs:

4.1 Race Conditions and Data Races

A data race occurs when two concurrent threads access the same memory location simultaneously, at least one access is a write, and no synchronization (mutex or memory barrier) orders the accesses. A race condition is a higher-level algorithmic flaw where the correctness of a program depends on the relative timing or interleaving of external events.

4.2 Deadlock and the Coffman Conditions

A deadlock occurs when a set of concurrent processes are permanently blocked because each process holds a resource that another process needs, and neither can proceed. In 1971, Edward G. Coffman Jr., Michael J. Elphick, and Arie Shoshani proved that a deadlock can arise if and only if four necessary and sufficient conditions hold simultaneously [4]:

1. Mutual Exclusion: At least one resource must be held in a non-shareable mode (only one process can use it at a time).
2. Hold and Wait: A process must currently hold at least one resource while waiting to acquire additional resources held by other processes.
3. No Preemption: Resources cannot be forcibly confiscated from a process; they can only be released voluntarily after the holding process completes its task.
4. Circular Wait: A closed chain of processes \(\{P_0, P_1, \dots, P_n\}\) exists such that \(P_0\) is waiting for a resource held by \(P_1\), \(P_1\) is waiting for \(P_2\), and \(P_n\) is waiting for \(P_0\).

Preventing deadlock requires mathematically eliminating at least one of these four conditions (e.g. establishing a global lock acquisition hierarchy to prevent circular wait).

4.3 Livelock and Starvation

• Livelock: Processes continuously change their state in response to each other without making functional forward progress (analogous to two polite people attempting to step around each other in a hallway and continually mirroring each other's steps).
• Starvation: A runnable process is perpetually denied access to necessary resources because other higher-priority processes continually preempt it.

4.4 Time-of-Check to Time-of-Use (TOCTOU)

A TOCTOU flaw occurs when a system inspects a state condition (e.g. checking file access permissions or balance availability) and subsequently acts upon that state, but a concurrent operation modifies the underlying condition in the interval between the check and the use, invalidating the authorization or invariant.

5. Concurrency in Asynchronous Multi-Agent Systems

In modern artificial intelligence agent architectures, concurrency governs fleet coordination and tool dispatch:

• Tool Call Interleaving: An agent orchestrator launches multiple asynchronous tool requests (web scrapes, sandbox code executions, database queries) concurrently. Result streams must be safely aggregated and sequenced into the model's context window.
• State Contention across Subagents: When multiple autonomous subagents operate concurrently on a shared repository or knowledge graph, uncoordinated file edits produce race conditions and merge conflicts. Architectural patterns like dedicated worktree isolation, branching pipelines, and immutable append-only logs prevent destructive concurrency hazards.
• Deadlock in Agent Handoffs: Two autonomous agents waiting mutually for outputs or authorization handoffs can form a circular dependency, replicating classic distributed deadlocks at the cognitive orchestration level.