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 synchronizations between a collection of independent agents or processes. They also provide algebraic laws that allow process descriptions to be manipulated and analyzed, and permit formal reasoning about equivalences between processes (e.g., using bisimulation). Leading examples of process calculi include CSP, CCS, ACP, and LOTOS. More recent additions to the family include the π-calculus, the ambient calculus, PEPA, the fusion calculus and the join-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 synchronizations between a collection of independent agents or processes. They also provide algebraic laws that allow process descriptions to be manipulated and analyzed, and permit formal reasoning about equivalences between processes (e.g., using bisimulation). Leading examples of process calculi include CSP, CCS, ACP, and LOTOS. More recent additions to the family include the π-calculus, the ambient calculus, PEPA, the fusion calculus and the join-calculus. While the variety of existing process calculi is very large (including variants that incorporate stochastic behaviour, timing information, and specializations for studying molecular interactions), there are several features that all process calculi have in common: To define a process calculus, one starts with a set of names (or channels) whose purpose is to provide means of communication. In many implementations, channels have rich internal structure to improve efficiency, but this is abstracted away in most theoretic models. In addition to names, one needs a means to form new processes from old ones. The basic operators, always present in some form or other, allow: Parallel composition of two processes P {displaystyle {mathit {P}}} and Q {displaystyle {mathit {Q}}} , usually written P | Q {displaystyle Pvert Q} , is the key primitive distinguishing the process calculi from sequential models of computation. Parallel composition allows computation in P {displaystyle {mathit {P}}} and Q {displaystyle {mathit {Q}}} to proceed simultaneously and independently. But it also allows interaction, that is synchronisation and flow of information from P {displaystyle {mathit {P}}} to Q {displaystyle {mathit {Q}}} (or vice versa) on a channel shared by both. Crucially, an agent or process can be connected to more than one channel at a time. Channels may be synchronous or asynchronous. In the case of a synchronous channel, the agent sending a message waits until another agent has received the message. Asynchronous channels do not require any such synchronization. In some process calculi (notably the π-calculus) channels themselves can be sent in messages through (other) channels, allowing the topology of process interconnections to change. Some process calculi also allow channels to be created during the execution of a computation. Interaction can be (but isn't always) a directed flow of information. That is, input and output can be distinguished as dual interaction primitives. Process calculi that make such distinctions typically define an input operator (e.g. x ( v ) {displaystyle x(v)} ) and an output operator (e.g. x ⟨ y ⟩ {displaystyle xlangle y angle } ), both of which name an interaction point (here x {displaystyle {mathit {x}}} ) that is used to synchronise with a dual interaction primitive. Should information be exchanged, it will flow from the outputting to the inputting process. The output primitive will specify the data to be sent. In x ⟨ y ⟩ {displaystyle xlangle y angle } , this data is y {displaystyle y} . Similarly, if an input expects to receive data, one or more bound variables will act as place-holders to be substituted by data, when it arrives. In x ( v ) {displaystyle x(v)} , v {displaystyle v} plays that role. The choice of the kind of data that can be exchanged in an interaction is one of the key features that distinguishes different process calculi. Sometimes interactions must be temporally ordered. For example, it might be desirable to specify algorithms such as: first receive some data on x {displaystyle {mathit {x}}} and then send that data on y {displaystyle {mathit {y}}} . Sequential composition can be used for such purposes. It is well known from other models of computation. In process calculi, the sequentialisation operator is usually integrated with input or output, or both. For example, the process x ( v ) ⋅ P {displaystyle x(v)cdot P} will wait for an input on x {displaystyle {mathit {x}}} . Only when this input has occurred will the process P {displaystyle {mathit {P}}} be activated, with the received data through x {displaystyle {mathit {x}}} substituted for identifier v {displaystyle {mathit {v}}} .