The calculus of communicating systems (CCS) is a

process calculus In computer science, the process calculi (or process algebras) are a diverse family of related approaches for formally modelling concurrent systems. Process calculi provide a tool for the high-level description of interactions, communications, and ...

introduced by

Robin Milner Arthur John Robin Gorell Milner (13 January 1934 – 20 March 2010) was a British computer scientist, and a Turing Award winner.deadlock or

livelock In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lock. ...

. According to Milner, "There is nothing canonical about the choice of the basic combinators, even though they were chosen with great attention to economy. What characterises our calculus is not the exact choice of combinators, but rather the choice of interpretation and of mathematical framework". The expressions of the language are interpreted as a

labelled transition system In theoretical computer science, a transition system is a concept used in the study of computation. It is used to describe the potential behavior of discrete systems. It consists of states and transitions between states, which may be labeled wi ...

. Between these models, bisimilarity is used as a semantic equivalence. __TOC__

Syntax

Given a set of action names, the set of CCS processes is defined by the following BNF grammar: :

,\,\, , \,\,\,P_1a\,\,\,

The parts of the syntax are, in the order given above ; inactive process : the inactive process

0

is a valid CCS process ; action : the process

a.P_1

can perform an action

a

and continue as the process

P_1

; process identifier : write

A \overset P_1

to use the identifier

A

to refer to the process

P_1

(which may contain the identifier

A

itself, i.e., recursive definitions are allowed) ; summation : the process

P_1+P_2

can proceed either as the process

P_1

or the process

P_2

; parallel composition :

P_1, P_2

tells that processes

P_1

and

P_2

exist simultaneously ; renaming :

P_1 /a /math> is the process P_1 with all actions named a renamed as b; restriction : P_1a is the process P_1 without action a

Related calculi, models, and languages

Communicating sequential processes In computer science, communicating sequential processes (CSP) is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or p ...

(CSP), developed by

Tony Hoare Sir Charles Antony Richard Hoare (; born 11 January 1934), also known as C. A. R. Hoare, is a British computer scientist who has made foundational contributions to programming languages, algorithms, operating systems, formal verification, and ...

, is a formal language that arose at a similar time to CCS. * The Algebra of Communicating Processes (ACP) was developed by Jan Bergstra and Jan Willem Klop in 1982, and uses an axiomatic approach (in the style of

Universal algebra Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures in general, not specific types of algebraic structures. For instance, rather than considering groups or rings as the object of stud ...

) to reason about a similar class of processes as CCS. * The pi-calculus, developed by

Robin Milner Arthur John Robin Gorell Milner (13 January 1934 – 20 March 2010) was a British computer scientist, and a Turing Award winner.PEPA, developed by Jane Hillston introduces activity timing in terms of exponentially distributed rates and probabilistic choice, allowing performance metrics to be evaluated. * Reversible Communicating Concurrent Systems (RCCS) introduced by Vincent Danos, Jean Krivine, and others, introduces (partial) reversibility in the execution of CCS processes. Some other languages based on CCS: * Calculus of broadcasting systems * Language Of Temporal Ordering Specification (LOTOS) * Process Calculus for Spatially-Explicit Ecological Models (PALPS) is an extension of CCS with probabilistic choice, locations and attributes for locations * Java Orchestration Language Interpreter Engine (Jolie) Models that have been used in the study of CCS-like systems: *

History monoid In mathematics and computer science, a history monoid is a way of representing the histories of concurrently running computer processes as a collection of strings, each string representing the individual history of a process. The history monoid pr ...

Actor model The actor model in computer science is a mathematical model of concurrent computation that treats an ''actor'' as the basic building block of concurrent computation. In response to a message it receives, an actor can: make local decisions, create ...

References

* Robin Milner: ''A Calculus of Communicating Systems'', Springer Verlag, . 1980. * Robin Milner, ''Communication and Concurrency'', Prentice Hall, International Series in Computer Science, . 1989 {{Concurrent computing 1980 in computing Process calculi