CS PAPERS DEEP-READ · PAPER 66
C. A. R. Hoare · Communications of the ACM · 1978
In 1978 Tony Hoare proposed CSP: when a program has to do several things at once, don't let those things share one pot of memory and then fence each other off; let each run on its own and have them deal with each other only by handing over messages. This is not a paper with experimental numbers — what it offers is a way of writing programs. When you write Go channels today, or run telecom-grade systems on Erlang / Elixir, you are using this paper's worldview.
The standard answer back then: several simultaneous strands of work share one pot of memory, everyone can read it and everyone can change it; to keep them from colliding, you agree on a separate set of rules — raise your hand first, and only then may you touch it.
Picture a roomful of people sharing one whiteboard that says how much money is in the account. There are two kinds of trouble. First, break the rule once and the board gets scribbled over: one person works out "100 minus 30" and is about to write it down, but someone else has already changed the number to 80 — and what lands on the board is 70. Second, and far more maddening: the error does not reproduce. Run it a hundred times and only the third run is wrong, because whether it breaks depends on whether two people happened to reach out in the very same microsecond.
Hoare's move is: take the whiteboard away.
Give each person their own small room and their own sheet of paper, where nobody can see anyone else's sheet; to exchange anything, you may only pass a note through the window. That class of bug is then not policed more strictly — it becomes impossible to have: with nothing shared, there is nothing to fight over, and since only one person ever touches a given sheet, the arithmetic on that sheet is always consistent.
The key is that it is hand to hand: the person offering the note must hold their arm out and wait for someone to take it, and the person reaching for one must wait for someone to offer it; whoever arrives first waits for the other, and they let go at the same instant, then each goes back to their own work.
That removes the old world's second mechanism: you used to write the data on the board and then separately announce "hey, it's ready" — and the bugs lived precisely in the mismatch between the two. Hand to hand, the note arriving is the announcement.
The second point matters just as much: one person can watch several windows at once and serve whichever window a note comes through first — you don't name in advance who you are waiting for, only that you're waiting for whoever is first. That is what lets one person act as a service window, taking several people in turn; without it you can only write a rigid single-file pipeline.
Those two moves are enough to build everything a language used to have to provide built in. Want a buffer that can hold goods? Hire someone as a runner who takes deliveries from the front and hands them out at the back. Want "only three people in the kitchen at a time"? Hire a doorkeeper who counts heads. What used to be built-in features all become "hire one more person".
In the 1980s people really did build a language from it (occam), and even a chip (the Transputer) with "process" and "window" built straight into the hardware — a paper turning into a CPU is rare. Go's channels, Erlang's message passing, even the microservice instinct that everything should guard its own data and expose only an interface, all come from the same source.
One honest caveat: this trick abolishes "the board got scribbled over", but it does not abolish everyone waiting on everyone else — if two people both hold their arms out waiting for the other to hand over first, they seize up together. Hoare's own five-philosophers-at-dinner example needs that extra doorkeeper precisely so it doesn't jam.
Don't let parallel strands of work share one pot of memory and fence each other off with locks; give each its own and let them pass messages hand to hand — the instant the note lands, handing over the data and lining up the timing are both done, so data collisions cannot happen. Then let a process wait on "whichever of these windows comes first", and buffers, permits and pipelines can all be written out rather than built in. The cost: it cures data collisions, not mutual waiting.
Want the rendezvous timing diagram, the guarded-command notation, and how it grew into Go's channels and select? → switch to the deep read
CSP proposes writing a concurrent program as a set of sequential processes with no shared variables at all, whose only interaction is a pair of input / output commands executed simultaneously — a rendezvous — and then borrows Dijkstra's guarded commands so a process can wait on "whichever of several inputs is ready first". From those two primitives alone, the paper shows that buffers, semaphores, monitor-style modules, coroutines, subroutine calls and pipelines can all be written out instead of built into the language. It is the blueprint for the occam language and the Transputer chip, and the common ancestor of Go's channels and of the CSP process algebra.
condition → statement; several are listed side by side, and any one of those whose condition holds is executed — which one is deliberately left unspecified (this is nondeterminism).The author is C. A. R. (Tony) Hoare; the paper appeared in CACM in August 1978, around the years he was moving from Queen's University Belfast to Oxford. It builds on Dijkstra: guarded commands (1975) are borrowed wholesale as the skeleton, while the targets it means to replace — semaphores and monitors — are respectively Dijkstra's and, four years earlier, Hoare's own, which makes this in a sense his alternative route around shared memory. Milner's CCS (1980) is the other great source stream of the same era. Downstream: the occam language and the INMOS Transputer, Ada's task rendezvous, Hoare's own 1985 book of the same title (which turns CSP into a process algebra with a formal semantics), and today's Go.
In 1978 the standard answer for concurrency was "shared memory plus a set of synchronisation gadgets": put the data in variables everyone can read and write, then use semaphores or monitors to rule who may touch it when. It works, but it chafes in three places. First, it splits one act into two mechanisms: "hand the data to the other side" goes through a shared variable, "tell the other side it's ready" goes through a semaphore — and the vast majority of concurrency bugs live exactly in the seam (a forgotten lock, the wrong granularity, a notification ahead of the write). Second, errors don't reproduce: correctness depends on precisely how instructions interleave, so the same code may fail once in a thousand runs. Third, reasoning isn't separable: to understand one piece of code you cannot look at that code alone — another thread may change your variables in the gap between any two instructions, and the number of interleavings explodes with the number of threads.
Hence the motivation: not to police shared data more strictly, but to make sharing disappear, so that each process becomes a sequential program you can once again read, and prove, on its own.
Processes share no variables; their only interaction is a pair of input / output commands — bang to send, query to receive. east!x means "hand the value of expression x to the process named east", and west?c means "receive a value from the process named west into variable c". The paper's smallest example is a one-line forwarder, *[west?c → east!c]: repeatedly take a character from the west and pass it east.
The mechanism: the two commands only take effect as a matched pair. Whichever side reaches its half first stops there and blocks until the other side reaches the matching half; at that point both commands execute simultaneously, the value is copied from the sender's expression into the receiver's variable, and each side carries on. That is the rendezvous, and it is synchronous and unbuffered: there is no "fire and forget", and no mailbox in which the system hoards messages for you.
Why design it this way? Because it fuses the old world's two mechanisms into one act: at the instant the hand-over completes, the two timelines are exactly aligned, so no separate "it's ready" notification is needed and there is no room for the two to mismatch. The deeper payoff is that reasoning becomes separable again — a process's variables are touched only by itself, its invariant is maintained by itself alone, and reading it requires no assumption that "someone else may change my state at any moment". The race condition isn't policed; there is nothing to race over. As for buffering, Hoare deliberately doesn't provide it — if you want it, write a process that is a buffer.
Matched send/receive alone only builds rigid single-file pipelines. What makes CSP actually sufficient is the second idea: take Dijkstra's guarded commands, and add one crucial permission — a guard may contain an input command.
The notation is *[ left?x → handle □ ctl?stop → quit ]: the box □ separates several "guard → statement" arms, and the star means repeat. The process stops here watching all the guards at once, and whichever arm's partner first reaches the matching half, that is the arm taken; if several are ready at once, any one is chosen — the paper deliberately does not say which, and promises no fair rotation.
Why is that permission crucial? It turns a process from "sending and receiving in a hard-wired order" into "serving in the order partners arrive". A server process taking several clients at once, or a buffer improvising between "there's room, so accept from the producer" and "there's stock, so answer the consumer", rests entirely on it. Go's select is its direct descendant.
There is one honest asymmetry: this version allows only input guards, never an output command in a guard — you cannot write "either send to A or receive from B, whichever comes first". Hoare says plainly that this restriction is for ease of implementation.
The last piece is the parallel command [P1 || P2 || … ]: start these processes side by side; it finishes when all of them do. Note that in this version the set of processes is statically fixed — there is no "spawn one per incoming request".
The body of the paper is then a long run of numbered examples, and together they are the real argument:
What this distils to: semaphores, monitors, subroutines, coroutines — things previously treated as language primitives or built-in system features — all degenerate in CSP into ordinary programs, "just add another process". That is where its real force lies: not performance, but economy of concepts.
To be honest about it: this paper has no experiments, no benchmarks, not one performance number, and in 1978 there was no implementation either — Hoare says himself that what he offers is a set of primitives, not a complete language (no types, modules or exceptions, and no formal semantics). Its "results" are of two other kinds.
The first is a demonstration of expressive power: that run of examples covers the classic problems of concurrent programming of the day, each written with only the two primitives and each short enough to read on one page. For a language-design paper, that is the experimental section — not "how much faster", but "everything you used to need a language feature for, you no longer need one for". The second is the provability it promises, and that promissory note was later honoured: with no shared state between processes, each process's invariant is maintained by itself, and reasoning needn't enumerate "who might touch my variables between which two instructions of mine". Seven years later Brookes, Hoare, Roscoe and others turned it into a process algebra with a formal semantics (the traces and failures-divergences models); with a refinement checker like FDR, a concurrent design really can be handed to a machine to check exhaustively for deadlock — far harder to do in the shared-memory model.
It reached hardware, which is rare. In the 1980s INMOS turned CSP into the occam language (PAR / SEQ / ALT and channels are first-class constructs) and designed the Transputer — a chip treating processes and channels as hardware concepts. A language-design paper becoming the design principle of a CPU is unusual; Ada's task rendezvous was likewise directly influenced by it.
It entered one of today's most mainstream languages. From Bell Labs' Newsqueak and Alef to Plan 9's Limbo, that line finally converges on Go: goroutines + channels + select, and even the slogan is CSP's — "don't communicate by sharing memory; share memory by communicating". Go departs from the original in two stated ways: channels are first-class values (no need to hard-code the partner process's name, a step that arrives only with the 1985 version) and may be buffered; and select allows send arms.
It also opened a whole branch of concurrency verification: the 1985 book of the same title turns CSP into a process algebra, named alongside Milner's CCS / π-calculus as one of the two source streams, and it remains a mainstream tool for verifying concurrency and communication protocols.
At the level of ideas, "don't share, pass messages" became one of the default pieces of advice in concurrency and distributed systems — Erlang / Elixir's processes and messages, actor frameworks like Akka, even the microservice instinct that each service guards its own data and exposes only an interface, all share this ancestry. But one precision is owed: the actor branch uses an asynchronous mailbox (fire and forget, messages queue in the recipient's box), not CSP's synchronous rendezvous; the common inheritance is only "share no state".
west / east; change the topology and you must edit the code, and a process can't be reused as a component. Only the 1985 version and occam fix this, by promoting channels to first-class entities.1 · In one sentence: write a concurrent program as a set of sequential processes with no shared variables, interacting only through a pair of simultaneously executed input / output commands (a rendezvous).
2 · The old world's pain: shared memory splits "handing over data" and "lining up timing" into two mechanisms, bugs live in the seam and don't reproduce, and reasoning must enumerate every interleaving.
3 · Idea one: east!x / west?c must pair up; whoever arrives first blocks, and on pairing both execute at once — hand-over and synchronisation in one act, with nothing shared there is nothing to race over. Synchronous and unbuffered is a deliberate choice.
4 · Idea two: an input may sit in a guard, so a process can wait on "whichever of several is ready" and take any one (no fairness promised) — the basis of server processes and buffers, and the ancestor of Go's select. This version forbids output guards.
5 · Idea three: add the parallel command [P1 || P2] and semaphores, monitors, subroutines, coroutines and pipelines all become "just add another process" — the selling point is economy of concepts.
6 · Results: no experimental numbers; the evidence is a run of short examples covering the classic concurrency problems, plus the promissory note "no sharing ⇒ reasoning separately", honoured seven years later as a process algebra with machine-checkable verification.
7 · Influence: occam and the Transputer, Ada's task rendezvous, Newsqueak→Limbo→Go's channels and select (Erlang / actors share the ancestry but take asynchronous mailboxes).
8 · Limitations: hard-coded process names don't compose, input guards only, a static process set, it cures races but not deadlock, synchronous coupling, and performance often below a plain mutex.