Communicating sequential processes

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 process calculi. CSP was influential in the development of the occam programming language.

CSP was first described in a 1978 paper by C. A. R. Hoare, but has since evolved substantially. CSP has been practically applied in industry as a tool for specifying and verifying the concurrent aspects of a variety of different systems — such as the T9000 Transputer, and a secure ecommerce system. The theory of CSP itself is also still the subject of active research, including work to increase its range of practical applicability (e.g. increasing the scale of the systems that can be tractably analyzed).

History

The version of CSP presented in Hoare's original 1978 paper was essentially a concurrent programming language rather than a process calculus. It had a substantially different syntax than later version of CSP, did not possess mathematically defined semantics, and was unable to represent unbounded nondeterminism. Programs in the original CSP were written as a parallel composition of a fixed number of sequential processes communicating with each other strictly through synchronous message-passing. In contrast to later versions of CSP, each process was assigned an explicit name, and the source or destination of a message was defined by specifying the name of the intended sending or receiving process. For example the process

COPY = *[c:character; west?c → east!c]

repeatedly receives a character from the process named west, and then sends that character to process named east. The parallel composition

[west::DISASSEMBLE || X::COPY || east::ASSEMBLE]

assigns the names west to the DISASSEMBLE process, X to the COPY process, and east to the ASSEMBLE process, and executes these three processes concurrently.

Following the publication of the original version of CSP, Hoare, Stephen Brookes, and A. W. Roscoe developed and refined the theory of CSP into its modern, process algebraic form. The approach taken in developing CSP into a process algebra was influenced by Robin Milner's work on the Calculus of Communicating Systems (CCS), and vice versa. The theoretical version of CSP was initially presented in a 1984 article by Brookes, Hoare, and Roscoe, and later in Hoare's book Communicating Sequential Processes, which was published in 1985. In September 2006, that book was still the third-most cited computer science reference of all time according to Citeseer (albeit an unreliable source due to the nature of its sampling). The theory of CSP has undergone a few minor changes since the publication of Hoare's book. Most of these changes were motivated by the advent of automated tools for CSP process analysis and verification. Roscoe's The Theory and Practice of Concurrency describes this newer version of CSP.

Informal description

As its name suggests, CSP allows the description of systems in terms of component processes that operate independently, and interact with each other solely through message-passing communication. However, the "Sequential" part of the CSP name is now something of a misnomer, since modern CSP allows component processes to be defined both as sequential processes, and as the parallel composition of more primitive processes. The relationships between different processes, and the way each process communicates with its environment, are described using various process algebraic operators. Using this algebraic approach, quite complex process descriptions can be easily constructed from a few primitive elements.

Primitives

CSP provides two classes of primitives in its process algebra:Events
Events represent communications or interactions. They are assumed to be indivisible and instantaneous. They may be atomic names (e.g. mathit{on}, mathit{off}), compound names (e.g. valve.open, valve.close), or input/output events (e.g. mouse?xy, screen!bitmap).Primitive processes:
Primitive processes represent fundamental behaviors: examples include mathit{STOP} (the process that communicates nothing, also called deadlock), and mathit{SKIP} (which represents successful termination)

Algebraic operators

CSP has a wide range of algebraic operators. The principal ones are:Prefix
The prefix operator combines an event and a process to produce a new process. For example,

a rightarrow P

is the process which is willing to communicate mathit{a} with its environment, and, after mathit{a}, behaves like the process mathit{P}.Deterministic Choice
The deterministic (or external) choice operator allows the future evolution of a process to be defined as a choice between two component processes, and allows the environment to resolve the choice by communicating an initial event for one of the processes. For example,

left(a rightarrow Pright) Box left(b rightarrow Qright)

is the process which is willing to communicate the initial events mathit{a} and mathit{b}, and subsequently behaves as either mathit{P} or mathit{Q} depending on which initial event the environment chooses to communicate. If both mathit{a} and mathit{b} were communicated simultaneously the choice would be resolved nondeterministically.Nondeterministic Choice
The nondeterministic (or internal) choice operator allows the future evolution of a process to be defined as a choice between two component processes, but does not allow the environment any control over which of the component processes will be selected. For example,

left(a rightarrow Pright) sqcap left(b rightarrow Qright)

can behave like either left(a rightarrow Pright) or left(b rightarrow Qright). It can refuse to accept mathit{a} or mathit{b}, and is only obliged to communicate if the environment offers both mathit{a} and mathit{b}. Nondeterminism can be inadvertently introduced into a nominally deterministic choice if the initial events of both sides of the choice are identical. So, for example,

left(a rightarrow a rightarrow STOPright) Box left(a rightarrow b rightarrow STOPright)

is equivalent to

a rightarrow left(left(a rightarrow STOPright) sqcap left(b rightarrow STOPright)right)Interleaving
The interleaving operator represents completely independent concurrent activity. The process

P ;vertvertvert; Q

behaves as both mathit{P} and mathit{Q} simultaneously. The events from both processes are arbitrarily interleaved in time.Interface Parallel
The interface parallel operator represents concurrent activity that requires synchronization between the component processes – any event in the interface set can only occur when all component processes are able to engage in that event. For example, the process

P leftvertleft[left{ a right} right]rightvert Q

requires that mathit{P} and mathit{Q} must both be able to perform event mathit{a} before that event can occur. So, for example, the process

left(a rightarrow Pright) leftvertleft[left{ a right} right]rightvert left(a rightarrow Qright)

can engage in event mathit{a}, and become the process

P leftvertleft[left{ a right} right]rightvert Q

while

left (a rightarrow Pright ) leftvertleft[left{ a, b right} right]rightvert left(b rightarrow Qright)

will simply deadlock.Hiding
The hiding operator provides a way to abstract processes, by making some events unobservable. A trivial example of hiding is

left(a rightarrow Pright) setminus left{ a right}

which, assuming that the event mathit{a} doesn't appear in mathit{P}, simply reduces to

mathit{P}

Examples

One of the archetypal CSP examples is an abstract representation of a chocolate vending machine, and its interactions with a person wishing to buy some chocolate. This vending machine might be able to carry out two different events, “coin” and “choc” which represent the insertion of payment and the delivery of a chocolate respectively. A machine which demands payment before offering a chocolate can be written as:

VendingMachine = coin rightarrow choc rightarrow STOP

A person who might choose to use a coin or card to make payments could be modelled as:

Person = (coin rightarrow STOP) Box (card rightarrow STOP)

These two processes can be put in parallel, so that they can interact with each other. The behaviour of the composite process depends on the events that the two component processes must synchronise on. Thus,

VendingMachine leftvertleft[left{ coin, card right}right]rightvert Person equiv coin rightarrow choc rightarrow STOP

whereas if synchronization was only required on “coin”, we would obtain

VendingMachine leftvertleft[left{ coin right}right]rightvert Person equiv left (coin rightarrow choc rightarrow STOPright ) Box left (card rightarrow STOPright )

If we abstract this latter composite process by hiding the “coin” and “card” events, i.e.

left (left (coin rightarrow choc rightarrow STOPright ) Box left (card rightarrow STOPright )right ) setminus left{coin, cardright}

we get the nondeterministic process

left (choc rightarrow STOPright ) sqcap STOP

This is a process which either offers a “choc” event and then stops, or just stops. In other words, if we treat the abstraction as an external view of the system (e.g., someone who does not see the decision reached by the person), nondeterminism has been introduced.

Formal definition

Syntax

The syntax of CSP defines the “legal” ways in which processes and events may be combined. Let mathit{e} be an event, and mathit{X} be a set of events. Then the basic syntax of CSP can be defined as:

begin{matrix} Proc & ::= & STOP & ; &|& SKIP & ; &|& e rightarrow Proc & (prefixing) &|& Proc ;Box; Proc & (external ; choice) &|& Proc ;sqcap; Proc & (nondeterministic ; choice) &|& Proc ;vertvertvert; Proc & (interleaving) &|& Proc ;|[{ X } ]| ;Proc & (interface ; parallel) &|& Proc setminus X & (hiding) &|& Proc ; Proc & (sequential ; composition) &|& mathrm{if} ; b ; mathrm{then} ; Proc; mathrm{else}; Proc & (boolean ; conditional) &|& Proc ;triangleright; Proc & (timeout) &|& Proc ;triangle; Proc & (interrupt) end{matrix}

Note that, in the interests of brevity, the syntax presented above omits the mathbf{div} process, which represents divergence, as well as various operators such as alphabetized parallel, piping, and indexed choices.

Formal semantics

CSP has been imbued with several different formal semantics, which define the meaning of syntactically correct CSP expressions. The theory of CSP includes mutually consistent denotational semantics, algebraic semantics, and operational semantics.

Denotational semantics

The three major denotational models of CSP are the traces model, the stable failures model, and the failures/divergences model. Semantic mappings from process expressions to each of these three models provide the denotational semantics for CSP.

The traces model defines the meaning of a process expression as the set of sequences of events (traces) that the process can be observed to perform. For example,

* tracesleft(STOPright) = left{ langlerangle right} since STOP performs no events
* tracesleft(arightarrow b rightarrow STOPright) = left{langlerangle ,langle a rangle, langle a, b rangle right} since the process (arightarrow b rightarrow STOP) can be observed to have performed no events, the event a, or the sequence of events a followed by b

More formally, the meaning of a process P in the traces model is defined as tracesleft(Pright) subseteq Sigma^{ast} such that:

  1. langlerangle in tracesleft(Pright) (i.e. tracesleft(Pright) contains the empty sequence)
  2. s_1 smallfrown s_2 in tracesleft(Pright) implies s_1 in tracesleft(Pright) (i.e. tracesleft(Pright) is prefix-closed)

where Sigma^{ast} is the set of all possible finite sequences of events.

The stable failures model extends the traces model with refusal sets, which are sets of events X subseteq Sigma that a process can refuse to perform. A failure is a pair left(s,Xright), consisting of a trace s, and a refusal set X which identifies the events that a process may refuse once it has executed the trace s. The observed behavior of a process in the stable failures model is described by the pair left(tracesleft(Pright), failuresleft(Pright)right). For example,

* failuresleft(left(a rightarrow STOPright) Box left(b rightarrow STOPright)right) = left{left(langlerangle,emptysetright), left(langle a rangle, left{a,bright}right), left(langle b rangle,left{a,bright}right) right}
* failuresleft(left(a rightarrow STOPright) sqcap left(b rightarrow STOPright)right) = left{ left(langlerangle,left{aright}right), left(langlerangle,left{bright}right),
left(langle a rangle, left{a,bright}right), left(langle b rangle,left{a,bright}right) right}

The failures/divergence model further extends the failures model to handle divergence. A process in the failures/divergences model is a pair left(failures_perpleft(Pright), divergencesleft(Pright)right) where divergencesleft(Pright) is defined as the set of all traces that can lead to divergent behavior and failures_perpleft(Pright) = failuresleft(Pright) cup left{left(s,Xright) vert s in divergencesleft(Pright)right}.

Applications

An early and important application of CSP was its use for specification and verification of elements of the INMOS T9000 Transputer, a complex superscalar pipelined processor designed to support large-scale multiprocessing. CSP was employed in verifying the correctness of both the processor pipeline, and the Virtual Channel Processor which managed off-chip communications for the processor.

Industrial application of CSP to software design has usually focused on dependable and safety-critical systems. For example, the Bremen Institute for Safe Systems and Daimler-Benz Aerospace modeled a fault management system and avionics interface (consisting of some 23,000 lines of code) intended for use on the International Space Station in CSP, and analyzed the model to confirm that their design was free of deadlock and livelock. The modeling and analysis process was able to uncover a number of errors that would have been difficult to detect using testing alone. Similarly, Praxis High Integrity Systems applied CSP modeling and analysis during the development of software (approximately 100,000 lines of code) for a secure smart-card Certification Authority to verify that their design was secure and free of deadlock. Praxis claims that the system has a much lower defect rate than comparable systems.

Since CSP is well-suited to modeling and analyzing systems that incorporate complex message exchanges, it has also been applied to the verification of communications and security protocols. A prominent example of this sort of application is Lowe’s use of CSP and the FDR refinement-checker to discover a previously unknown attack on the Needham-Schroeder public-key authentication protocol, and then to develop a corrected protocol able to defeat the attack.

Tools

Over the years, a number of tools for analyzing and understanding systems described using CSP have been produced. Early tool implementations used a variety of machine-readable syntaxes for CSP, making input files written for different tools incompatible. However, most CSP tools have now standardized on the machine-readable dialect of CSP devised by Bryan Scattergood, sometimes referred to as CSPM. The CSPM dialect of CSP possesses a formally defined operational semantics, which includes an embedded functional programming language.

The most well-known CSP tool is probably Failures/Divergence Refinement 2 (FDR2), which is a commercial product developed by Formal Systems Europe Ltd. FDR2 is often described as a model checker, but is technically a refinement checker, in that it converts two CSP process expressions into labelled transition systems, and then determines whether one of the processes is a refinement of the other within some specified semantic model (traces, failures, or failures/divergence).

Other CSP tools include

  • ProBE
  • ARC
  • Casper

Related formalisms

Several other specification languages and formalisms have been derived from, or inspired by, the classic untimed CSP, including:

See also

References

External links

Search another word or see communicating sequential processeson Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;