Four Combinators for Concurrency

Robin Milner

Research output: Chapter in Book/Report/Conference proceedingConference contribution


An algebraic calculus of asynchronous parallel computation, called CCS (Calculus of Communicating Systems), was developed in [HM,Mil 1]. CCS can express both the semantics of parallel programming languages and the behaviour of data structures (mailbox, random access memory, buffer) which serve as interfaces between independent agents. The primitive notion is 'handshake' communication. The emphasis is upon (i) synthesis from components and (ii) extensionality (meaning &equil; observable behaviour), in contrast with Petri's Net theory which emphasizes causal independence. Here CCS is broadened to embrace synchrony, or systems which depend critically upon the timing of their components. The extension is not adhoc; it is shown that with just four combinators one may both express synchrony and derive CCS in a precise sense. In fact more is gained; it is shown in [Mil 4] how the dynamic reconfiguration of agent linkage, which was outside the scope of the original calculus, may now be expressed. Moreover the four combinators seem, informally speaking, to represent notions which are fully orthogonal to each other, and so to provide a somewhat deeper and intellectually clearer foundation for distributed computation than CCS (which in turn, at its higher level, has some advantages in manipulation). This foundation does not presume a particular abstract notion of process, which in the author's view is still a contentious matter, but rather allows candidates for such a notion to be defined and compared; each such candidate will be a congruence class for some congruence relation in the calculus.
Original languageEnglish
Title of host publicationPODC '82
Subtitle of host publicationProceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing
Number of pages7
ISBN (Print)0-89791-081-8
Publication statusPublished - 1982


Dive into the research topics of 'Four Combinators for Concurrency'. Together they form a unique fingerprint.

Cite this