|
The process calculi (or process algebras) are a diverse family of related approaches to 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, and ACP. More recent additions to the family include the π-calculus, the ambient calculus, PEPA and the fusion calculus. Concurrent systems are an area of study in computer science, where concurrency or parallelism is important. ...
Algebra is the current mathematics collaboration of the week! Please help improve it to featured article standard. ...
In theoretical computer science a bisimulation is an equivalence relation between state transition systems, associating systems which behave in the same way in the sense that one system simulates the other and vice-versa. ...
In computer science, Communicating Sequential Processes (CSP) is a language for describing patterns of interaction. ...
The Calculus of Communicating Systems (or CCS) (one of the first process calculi) was developed by Robin Milner. ...
The Algebra of Communicating Processes (ACP) is an algebraic approach to reasoning about concurrent systems. ...
In theoretical computer science, the π-calculus is a notation originally developed by Robin Milner, Joachim Parrow and David Walker to model concurrency (just as the λ-calculus is a simple model of sequential programming languages). ...
Ambient calculus is a form of notation devised by Luca Cardelli and Andrew D. Gordon in 1998 and used to describe and theorise about mobile systems. ...
Salt-N-Pepa is an American R&B and hip hop group, consisting of Cheryl James and Sandy Denton (Salt and Pepa, respectively), and Deidre Dee Dee Roper (DJ Spinderella). ...
Essential features
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 (Pierce 1995): Stochastic, from the Greek stochos or goal, means of, relating to, or characterized by conjecture; conjectural; random. ...
- Representing interactions between independent processes as communication (message-passing), rather than as the modification of shared variables
- Describing processes and systems using a small collection of primitives, and operators for combining those primitives
- Defining algebraic laws for the process operators, which allow process expressions to be manipulated using equational reasoning
Mathematics of processes 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: the crucial operators, always present in some form or other, allow: - parallel composition of processes
- specification which channels to use for sending and receiving data
- sequentialization of interactions
- hiding of interaction points
- recursion or process replication
Parallel composition Parallel composition of two processes P and Q, usually written , is the key primitive distinguishing the process calculi from sequential models of computation. Parallel composition allows computation in P and Q to proceed simultaneously and independently. But it also allows interaction, that is synchronisation and flow of information from P to Q on a channel shared by both (or vice versa). 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. In theoretical computer science, the π-calculus is a notation originally developed by Robin Milner, Joachim Parrow and David Walker to model concurrency (just as the λ-calculus is a simple model of sequential programming languages). ...
Communication 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)) and an output operator (e.g. ), both of which name an interaction point (here 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 , this data is 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), 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.
Sequential composition Sometimes interactions must be temporally ordered. For example, it might be desirable to specify algorithms such as: first receive some data on x and then send that data on 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 will wait for an input on x. Only when this input has occurred will the process P be activated, with the received data through x substituted for identifier v.
Reduction semantics The key operational reduction rule, containing the computational essence of process calculi, can be given solely in terms of parallel composition, sequentialization, input, and output. The details of this reduction vary among the calculi, but the essence remains roughly the same. The reduction rule is: The interpretation of this reduction rule is: - The process sends a message, here y, along the channel x. Dually, the process receives that message on channel x.
- Once the message has been sent, becomes the process P, while becomes the process , which is Q with the place-holder v substituted by y, the data received on x.
The class of processes that P is allowed to range over as the continuation of the output operation substantially influences the properties of the calculus.
Hiding Processes do not limit the number of connections that can be made at a given interaction point. But interaction points allow interference (i.e. interaction). For the synthesis of compact, minimal and compositional systems, the ability to restrict interference is crucial. Hiding operations allow control of the connections made between interaction points when composing agents in parallel. Hiding can be denoted in a variety of ways. For example, in the π-calculus the hiding of a name x in P can be expressed as , while in CSP it might be written as . In theoretical computer science, the π-calculus is a notation originally developed by Robin Milner, Joachim Parrow and David Walker to model concurrency (just as the λ-calculus is a simple model of sequential programming languages). ...
In computer science, Communicating Sequential Processes (CSP) is a language for describing patterns of interaction. ...
Recursion and replication The operations presented so far describe only finite interaction and are consequently insufficient for full computability, which includes non-terminating behaviour. Recursion and replication are operations that allow finite descriptions of infinite behaviour. Recursion is well known from the sequential world. Replication !P can be understood as abbreviating the parallel composition of a countably infinite number of P processes:
Null process Process calculi generally also include a null process (variously denoted as nil, 0, STOP, δ, or some other appropriate symbol) which has no interaction points. It is utterly inactive and its sole purpose is to act as the inductive anchor on top of which more interesting processes can be generated.
History In the first half of the 20th century, various formalisms were proposed to capture the informal concept of a computable function, with μ-recursive functions, Turing Machines and the lambda calculus possibly being the best-known examples today. The surprising fact that they are essentially equivalent, in the sense that they are all encodable into each other, is the content of the Church-Turing thesis. Another shared feature is more rarely commented on: they all are most readily understood as models of sequential computation. The subsequent consolidation of computer science required a more subtle formulation of the notion of computation, in particular explicit representations of concurrency and communication. Models of concurrency such as the process calculi, Petri-Nets, and the Actor model emerged from this line of enquiry. (19th century - 20th century - 21st century - more centuries) Decades: 1900s 1910s 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s As a means of recording the passage of time, the 20th century was that century which lasted from 1901–2000 in the sense of the Gregorian calendar (1900–1999 in the...
In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are computable in some intuitive sense. ...
An artistic representation of a Turing Machine . ...
The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
In computability theory the Church-Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. ...
A Petri net (also known as a place/transition net or P/T net) is one of several mathematical representations of discrete distributed systems. ...
In computer science, the Actor model, first published in 1973, is a mathematical model of concurrent computation. ...
Research on process calculi began in earnest with Robin Milner's seminal work on the Calculus of Communicating Systems (CCS) during the period from 1973 to 1980. C.A.R. Hoare's Communicating Sequential Processes (CSP) first appeared in 1978, and was subsequently developed into a fully-fledged process calculus during the early 1980's. There was much cross-fertilization of ideas between CCS and CSP as they developed. In 1982 Jan Bergstra and Jan Willem Klop began work on what came to be known as the Algebra of Communicating Processes (ACP), and introduced the term process algebra to describe their work (Baeten 2004). CCS, CSP, and ACP constitute the three major branches of the process calculi family: the majority of the other process calculi can trace their roots to one of these three calculi. Robin Milner is a prominent British computer scientist. ...
The Calculus of Communicating Systems (or CCS) (one of the first process calculi) was developed by Robin Milner. ...
1973 (MCMLXXIII) was a common year starting on Monday (the link is to a full 1973 calendar). ...
1980 (MCMLXXX in Roman) was a leap year starting on Tuesday. ...
Sir Charles Antony Richard Hoare (Tony Hoare or C.A.R. Hoare, born January 11, 1934) is a British computer scientist, probably best known for the development of Quicksort, the worlds most widely used sorting algorithm, and perhaps even the worlds most widely used algorithm of any kind...
In computer science, Communicating Sequential Processes (CSP) is a language for describing patterns of interaction. ...
1978 (MCMLXXVIII in Roman) was a common year starting on Sunday (the link is to a full 1978 calendar). ...
1980 (MCMLXXX in Roman) was a leap year starting on Tuesday. ...
The Algebra of Communicating Processes (ACP) is an algebraic approach to reasoning about concurrent systems. ...
Current research Many different variants of process calculi have been studied and not all of them fit the paradigm sketched here. The most prominent example may be the Ambient calculus. This is to be expected as process calculi are an active field of study. Currently research on process calculi focuses on the following problems. Ambient calculus is a form of notation devised by Luca Cardelli and Andrew D. Gordon in 1998 and used to describe and theorise about mobile systems. ...
- Development of new process calculi for better modelling of computational phenomena.
- Finding well-behaved subcalculi of a given process calculus. This is valuable because (1) most calculi are fairly wild in the sense that they are rather general and not much can be said about arbitrary processes; and (2) computational applications rarely exhaust the whole of a calculus. Rather they use only processes that are very constrained in form. Constraining the shape of processes is mostly studied by way of Datatype.
- Logics for processes that allow to reason about (essentially) arbitrary properties of processes, following the ideas of Hoare logic.
- Behavioural theory: what does it mean for two processes to be the same? How can we decide whether two processes are different or not? Can we find representatives for equivalence classes of processes. Generally, processes are considered to be the same if no context, that is other processes running in parallel, can detect a difference. Unfortunately, making this intuition precises is subtle and mostly yields unwieldy characterisations of equality (which must also be undecidable, as a consequence of the Halting Problem in most cases). Bisimulations are a technical tool that aids reasoning about process equivalences.
- Expressivity of calculi. Programming experience shows that certain problems are easier to solve in some languages than in others. This phenomenon calls for a more precise characterisation of the expressivity of calculi modelling computation than that afforded by the Church-Turing thesis. One way of doing this is to consider encodings between two formalisms and see what properties encodings can potentially preserve. The more properties can be preserved, the more expressive the target of the encoding is said to be. For process calculi, the celebrated results are that the synchronous π-calculus is more expressive than its asynchronous variant, has the same expressive power as the higher-order π-calculus, but less than the Ambient calculus.
- Using process calculus to model biological systems. It is thought by some that the compositionality offered by process-theoretic tools can help biologists to organise their knowledge more formally.
Type has historically had the following uses: In biology, a type is the specimen or specimens upon which an original species description is based. ...
Hoare logic (also known as Floyd–Hoare logic) is a formal system developed by the British computer scientist C. A. R. Hoare, and subsequently refined by Hoare and other researchers. ...
In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and its initial input, determine whether the program, when executed on this input, ever halts (completes). ...
In theoretical computer science a bisimulation is an equivalence relation between state transition systems, associating systems which behave in the same way in the sense that one system simulates the other and vice-versa. ...
In computability theory the Church-Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. ...
In theoretical computer science, the π-calculus is a notation originally developed by Robin Milner, Joachim Parrow and David Walker to model concurrency (just as the λ-calculus is a simple model of sequential programming languages). ...
In theoretical computer science, the π-calculus is a notation originally developed by Robin Milner, Joachim Parrow and David Walker to model concurrency (just as the λ-calculus is a simple model of sequential programming languages). ...
Ambient calculus is a form of notation devised by Luca Cardelli and Andrew D. Gordon in 1998 and used to describe and theorise about mobile systems. ...
The Principle of Compositionality in semantics is the principle that the meaning of a complex expression is determined by the meanings of its constituent expressions and the rules used to combine them. ...
Relationship to other models of concurrency The use of channels for communication is one of the features distinguishing the process calculi from other models of concurrency, such as Petri nets and the Actor model (see Actor model and process calculi). One of the fundamental motivations for including channels in the process calculi was to enable certain algebraic techniques, thereby making it easier to reason about processes algebraically. Concurrent computing is the overlapped coordinated execution of the multiple tasks (split up and specially adapted) on multiple processors in order to share common resources. ...
A Petri net is a mathematical representation of discrete distributed systems. ...
In computer science, the Actor model, first published in 1973, is a mathematical model of concurrent computation. ...
In computer science the Actor model is related to subsequent process calculi models of concurrent digital computation. ...
References - - J.C.M. Baeten: A brief history of process algebra, Rapport CSR 04-02, Vakgroep Informatica, Technische Universiteit Eindhoven, 2004
- Robin Milner: A Calculus of Communicating Systems, Springer Verlag, ISBN 0387102353.
- Robin Milner: Communicating and Mobile Systems: the Pi-Calculus, Springer Verlag, ISBN 0521658691.
- - Benjamin Pierce: “Foundational Calculi for Programming Languages”, The Computer Science and Engineering Handbook, pp. 2190-2207, CRC Press, ISBN 0-8493-2909-4.
|
Feeds |
Contact