Weekly Paper Notes — the Seminal Paper of the Week for the 2026-08-08 CS paper digest. Area: Programming Languages / Concurrency (rotating away from a long run of distributed-systems picks).
Author: C. A. R. Hoare (Queen’s University, Belfast) Published: Communications of the ACM, Vol. 21, No. 8, August 1978, pp. 666–677 DOI: 10.1145/359576.359585
Why the paper still matters
If you have written ch <- v in Go, spawned an Erlang process and sent it a message, wired up an actor in Akka, or reasoned about a Rust mpsc channel, you have been programming in a dialect of a language sketched in eleven pages of CACM in 1978. Hoare’s Communicating Sequential Processes is one of the small number of papers whose ideas are now so thoroughly absorbed into practice that its originality is easy to miss.
The 1978 context matters. Concurrency at the time was overwhelmingly understood through shared memory plus a synchronisation discipline: semaphores (Dijkstra, 1965), conditional critical regions, and monitors — the last of which Hoare himself had formalised only four years earlier. In that world, processes communicate by mutating a shared store, and the language’s job is to supply enough locking machinery that the mutations don’t interleave catastrophically. Every mechanism in that lineage is fundamentally a restriction on an unrestricted, dangerous default.
Hoare’s move was to reject the default. CSP’s opening claim is that input and output are basic primitives of programming, on equal footing with assignment, and that parallel composition of communicating sequential processes is a fundamental structuring method rather than an implementation detail bolted onto a sequential language. There is no shared state in CSP. Processes have private variables. The only way for information to move is for one process to name another and communicate with it.
That single design decision — replacing shared mutable state with explicit message passing between named, isolated processes — is why the paper is still worth reading rather than merely citing.
The setup
CSP’s notation is spare to the point of austerity, built on Dijkstra’s guarded commands. It has essentially four ideas.
Commands and processes. A process is a sequential command list. Processes are composed in parallel with [X :: ... || Y :: ...], and the parallel command terminates only when all its constituent processes terminate.
Input and output commands. Y ! e means “output the value of expression e to process Y”. X ? v means “input from process X into variable v”. Communication is by direct naming: the sender names the receiver and the receiver names the sender. There is no channel object in the original paper, no anonymous port, no broker. This is the one aspect of CSP that later systems almost universally revised — Go’s channels, Erlang’s mailboxes, and CSP’s own later algebraic reformulation all introduced a level of indirection Hoare deliberately omitted.
The rendezvous. An input command and a matching output command correspond when the sender names the receiver, the receiver names the sender, and the types agree. Corresponding commands execute simultaneously, as a single atomic event, and their combined effect is the assignment of the sent value to the receiving variable. Whichever process arrives first waits.
Guarded commands and alternatives. From Dijkstra, CSP takes the guarded command guard → command and the alternative construct [ g₁ → c₁ ▯ g₂ → c₂ ]. Hoare’s crucial extension is that a guard may contain an input command. This is what makes CSP a concurrency language rather than a notation for pipelines: a process can offer to communicate with several partners at once and proceed with whichever becomes ready.
The invariants that make it work
Four properties of the design are worth naming explicitly, because they are exactly the properties that survived into every descendant.
1. No shared variables. A process’s variables are its own. This is not a discipline the programmer must maintain; it is a property of the language. Data races are not a bug you avoid — they are unrepresentable.
2. Communication is unbuffered and synchronous. There is no queue between sender and receiver. The rendezvous is the synchronisation event, so CSP needs no separate synchronisation construct at all. Hoare is explicit that buffering, where wanted, should be programmed as an intermediate process — a buffer is a first-class thing in the language, not a hidden property of the transport. This is a genuinely elegant unification: flow control, backpressure, and synchronisation all fall out of one mechanism.
3. Nondeterminism is explicit and bounded. When several guards of an alternative are ready, the choice is arbitrary. Hoare does not hide this, and does not pretend to a scheduling policy. Making nondeterminism a visible, first-class feature of the notation rather than an emergent property of the scheduler is what later made CSP tractable to formal reasoning.
4. Termination is compositional. A guard whose named partner has terminated simply fails, and the process continues with its other alternatives. When all a process’s guards fail, it terminates. This gives clean, structured shutdown of a process network without any out-of-band cancellation protocol — a problem that modern channel-based languages still handle awkwardly (Go’s context package exists largely to fill this gap).
The algorithm walk-through: a bounded buffer
The paper’s worked examples are its best argument, and the bounded buffer is the canonical one. In shared-memory concurrency, a bounded buffer requires a mutex, two condition variables, careful predicate re-checking on wakeup, and a decision about signalling discipline — Hoare vs. Mesa semantics, a distinction that exists only because monitors leak. It is a standard exercise precisely because it is a standard source of bugs.
In CSP it is a process holding a private array and a pair of counters, sitting in a loop over an alternative with two guarded input commands. One guard accepts a value from the producer, but is enabled only when the buffer is not full. The other accepts a request from the consumer, enabled only when the buffer is not empty, and replies with an output command. The bounds are ordinary boolean expressions in the guards.
The result contains no lock, no condition variable, no signalling discipline, and no wakeup race — because there is no shared state for a race to occur in, and the rendezvous provides the blocking. The buffer’s correctness argument is a sequential argument about one process’s local variables, plus the language’s guarantee about rendezvous. That reduction — from “reason about all interleavings of two threads over shared memory” to “reason about one process’s local state” — is the whole point of the paper.
The other examples in the paper are similarly instructive as a demonstration of range: the sieve of Eratosthenes as a pipeline of filter processes (later the canonical Go tutorial program), matrix multiplication on a mesh of processes, a factorial computation, an iterative array, and — most ambitiously — a sketch of how the subroutine, the coroutine, the class instance, and the monitor can all be expressed as CSP processes rather than needing separate language features. That last section is the paper’s boldest claim: not that CSP is a good concurrency notation, but that it subsumes several of the structuring mechanisms sequential languages had accumulated.
Why this design has outlasted everything around it
The direct lineage is easy to trace. Occam (INMOS, 1983) is CSP made executable, and shipped as the native language of the Transputer. Erlang (Armstrong et al., late 1980s) adopted isolated processes with no shared state and message passing as its foundation, though it chose asynchronous mailboxes over the synchronous rendezvous — a deliberate trade for distribution across unreliable networks. Go (2009) reintroduced the rendezvous almost verbatim: unbuffered channels are CSP channels, select is the alternative command, and Rob Pike’s “do not communicate by sharing memory; share memory by communicating” is Hoare’s thesis restated as a slogan. Rust’s channels, Clojure’s core.async, Kotlin’s coroutine channels, and Python’s trio all descend from the same idea.
But the paper’s second life is arguably more consequential than its first. The 1978 notation was informal, and Hoare spent the following decade turning it into a process algebra — a formal calculus with a denotational semantics based on traces, failures, and divergences, published as the 1985 book Communicating Sequential Processes. That formalisation, developed alongside Milner’s CCS and later the π-calculus, is the direct ancestor of the model checkers that verify real protocols today. FDR (Failures-Divergences Refinement) checks CSP specifications industrially. TLA+, though not CSP, inherits the ambition. When a modern paper announces that it model-checked a distributed protocol, it is standing on a formal edifice whose ground floor is this paper.
There is also a distributed-systems reading that has aged remarkably well. CSP processes share nothing and communicate only by message. That is precisely the model of a microservice fleet, of an actor system spread across machines, of any modern serverless architecture. Hoare’s argument that this model is easier to reason about, not merely easier to distribute, is the argument the industry rediscovered the hard way after two decades of distributed shared memory.
The honest caveats: direct naming does not compose, which is why nearly every descendant introduced channels as first-class values. The synchronous rendezvous is a poor fit for high-latency links, which is why Erlang went asynchronous. And CSP says nothing about failure — processes in the paper do not crash, which is exactly the gap Erlang’s supervision trees and later distributed-systems work were built to fill.
None of that diminishes the achievement. In 1978, with concurrency universally understood as “shared memory, carefully guarded,” Hoare wrote down a model in which the dangerous default simply does not exist, showed it was expressive enough to build everything people actually wanted to build, and did it in eleven pages. Nearly fifty years later the argument is still winning.
Read alongside
- Dijkstra, Guarded Commands, Nondeterminacy and Formal Derivation of Programs (CACM 1975) — the notational substrate CSP is built on.
- Hoare, Monitors: An Operating System Structuring Concept (CACM 1974) — the shared-memory approach Hoare himself formalised, then moved beyond.
- Milner, A Calculus of Communicating Systems (1980) — the contemporaneous process algebra, developed independently.
- Hoare, Communicating Sequential Processes (Prentice Hall, 1985) — the full formal treatment; freely available via usingcsp.com.
- Armstrong, Making Reliable Distributed Systems in the Presence of Software Errors (2003) — Erlang’s thesis, and the fault-tolerance story CSP omits.
- Pike, Concurrency Is Not Parallelism (2012) — the modern popularisation, and the clearest statement of why Go took this shape.
Links
📄 ACM Digital Library — doi:10.1145/359576.359585 · 📄 Author’s page and the 1985 book (free PDF)
Part of the Weekly CS Paper Digest series. Seminal picks are written from background knowledge and cited to the canonical publication; the diagram is original.