NationMaster - Encyclopedia: Communicating sequential processes

In computer science, Communicating Sequential Processes (CSP) is a formal language for describing patterns of interaction in concurrent systems.^[1] 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.^[2]^[1] Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... A specification language is a formal language used in computer science. ... A pattern is a form, template, or model (or, more abstractly, a set of rules) which can be used to make or to generate things or parts of a thing, especially if the things that are generated have enough in common for the underlying pattern to be inferred or discerned... Interaction is a kind of action which occurs as two or more objects have an effect upon one another. ... Concurrent systems are an area of study in computer science, where concurrency or parallelism is important. ... In the first half of the 20th century, various formalisms were proposed to capture the informal concept of computable function, Î¼-recursive functions, Turing Machines and the lambda calculus possibly being the most well-known examples today. ... Occam (from William of Ockham of Occams Razor fame) is a parallel programming language that builds on Communicating Sequential Processes (CSP) and shares many of their features. ...

CSP was first described in a 1978 paper^[3] 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,^[4] and a secure ecommerce system. ^[5] Academic applications of CSP include using it as tool for research in concurrency theory^{[citation needed]}, much as abstract machines are used for studying sequential systems. 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^[6]). 1978 (MCMLXXVIII) was a common year starting on Sunday. ... 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, in 1960. ... A formal specification is a mathematical description of software or hardware that may be used to develop an implementation. ... The INMOS Transputer was a pioneering parallel computing microprocessor design of the 1980s from INMOS, a small English company. ... An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in Automata theory. ...

History

The version of CSP presented in Hoare's original 1978 paper was essentially a concurrent programming language rather than a process calculus, and did not possess a mathematically defined semantics^[7]. It also suffered from a number of limitations, including an inability to represent unbounded nondeterminism. Subsequently, Hoare, Stephen Brookes, and A. W. Roscoe developed and refined the theory of CSP into its modern form^[8]. The approach taken in developing the theoretical version of CSP was heavily influenced by Robin Milner's work on the Calculus of Communicating Systems (CCS), and vice versa. In computer science, unbounded nondeterminism (sometimes called unbounded indeterminacy) is a property of concurrency by which the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources while still guaranteeing that the request will eventually be serviced. ... A. William Roscoe (Bill Roscoe) is director of the Computing Laboratory at the University of Oxford and a Professor of Computing Science. ... 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. ...

The theoretical version of CSP was presented in Hoare's book Communicating Sequential Processes^[7], which was published in 1985. In May 2005, 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. The definitive text on modern CSP is Roscoe's The Theory and Practice of Concurrency^[1]. 1985 (MCMLXXXV) was a common year starting on Tuesday of the Gregorian calendar. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... CiteSeer is a public speciality scientific and academic search engine and digital library that was created by researchers Dr. Steve Lawrence, Kurt Bollacker and Dr. Lee Giles while they were at the NEC Research Institute (now NEC Labs), Princeton, New Jersey, USA. CiteSeer crawls and harvests academic and scientific documents...

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. In computer science, Message passing is used in concurrent programming, parallel programming, and object-oriented programming, to accomplish communication by sending messages to recipients. ... The process calculi (or process algebras) are a diverse family of related approaches to formally modelling concurrent systems. ...

Primitives

It has been suggested that Circular wait be merged into this article or section. ...

Algebraic operators

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: Group representation theory is the branch of mathematics that studies properties of abstract groups via their representations as linear transformations of vector spaces. ...

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

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,

whereas if synchronization was only required on “coin”, we would obtain Synchronization is a problem in timekeeping which requires the coordination of events to operate a system in unison. ...

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

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. Look up decision in Wiktionary, the free dictionary. ... A person is defined by philosophers as a being who is in possession of a range of psychological capacities that are regarded as both necessary and sufficient to fulfill the requirements of personhood. ... This article is about the general notion of determinism in philosophy. ...

Formal definition

Syntax

The syntax of CSP defines the “legal” ways in which processes and events may be combined. Let

e

be an event, and

X

be a set of events. Then the basic syntax of CSP can be defined as: For other uses, see Syntax (disambiguation). ...

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. Semantics (Greek semantikos, giving signs, significant, symptomatic, from sema, sign) refers to the aspects of meaning that are expressed in a language, code, or other form of representation. ... In computer science, denotational semantics is an approach to formalizing the semantics of computer systems by constructing mathematical objects (called denotations or meanings) which express the semantics of these systems. ... An algebraic semantics of a programming language is a form of axiomatic semantics based on algebraic laws for describing and reasoning about program semantics in a formal manner. ... In computer science, operational semantics is a way to give meaning to computer programs in a mathematically rigorous way (See formal semantics of programming languages). ...

Applications

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 CSP_M^[9]. The CSP_M dialect of CSP possesses a formally defined operational semantics, which includes an embedded functional programming language. In computer science, operational semantics is a way to give meaning to computer programs in a mathematically rigorous way (See formal semantics of programming languages). ... Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ...

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)^[10]. Model checking is a method to algorithmically verify formal systems. ...

Related formalisms

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

In software architecture, Wright is an architecture description language developed at Carnegie Mellon University. ... Object-Z is an object-oriented extension to Z developed at the University of Queensland. ... The Z notation (universally pronounced zed) is a formal specification language used for describing and modelling computing systems. ... C. A. R. Hoare and He Jifeng, Unifying Theories of Programming. ... The Common Algebraic Specification Language (CASL) is a general-purpose specification language based on first-order logic with induction. ...

See also

It is an implementation for Communicating Sequential Processes for Java™. External links JCSP Communicating Threads for Java: Real-Time Extension for Java ... Java is an object-oriented programming language developed by Sun Microsystems in the early 1990s. ... Limbo is a programming language for writing distributed systems and is the language used to write applications for the Inferno operating system. ... Inferno is an operating system for creating and supporting distributed services. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... Plan 9 from User Space (aka plan9port) is a port of many Plan 9 libraries and applications to Unix-like operating systems. ... C is a general-purpose, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ... In integrated circuit design, VerilogCSP is a set of macros added to Verilog HDL to support Communicating Sequential Processes (CSP) channel communications. ... A macro in computer science is an abstraction, that defines how a certain input pattern is replaced by an output pattern according to a defined set of rules. ... Verilog is a hardware description language (HDL) used to model electronic systems. ...

References

^ ^a ^b ^c Roscoe, A. W. (1997). The Theory and Practice of Concurrency. Prentice Hall. ISBN 0-13-674409-5.
- Some links relating to this book are available here. The full text is available for download as a PS or PDF file from Bill Roscoe's list of academic publications.
^ INMOS (1995-05-12). occam 2.1 Reference Manual. SGS-THOMSON Microelectronics Ltd.. , INMOS document 72 occ 45 03
^ Hoare, C. A. R. (1978). "Communicating sequential processes". Communications of the ACM 21 (8): 666–677. DOI:10.1145/359576.359585.
^ Barrett, G. (1995). "Model checking in practice: The T9000 Virtual Channel Processor". IEEE Transactions on Software Engineering 21 (2): 69–78. DOI:10.1109/32.345823.
^ Hall, A; R. Chapman (2002). "Correctness by construction: Developing a commercial secure system". IEEE Software 19 (1): 18–25.
^ Creese, S. (2001). "Data Independent Induction: CSP Model Checking of Arbitrary Sized Networks". D. Phil.. Oxford University.
^ ^a ^b Hoare, C. A. R.. Communicating Sequential Processes. Prentice Hall. ISBN 0-13-153289-8.
- This book has been updated by Jim Davies at the Oxford University Computing Laboratory and the new edition is available for download as a PDF file at the Using CSP website.
^ Brookes, Stephen; C. A. R. Hoare and A. W. Roscoe (1984). "A Theory of Communicating Sequential Processes". Journal of the ACM 31 (3): 560–599. DOI:10.1145/828.833.
^ Scattergood, J.B. (1998). "The Semantics and Implementation of Machine-Readable CSP". D.Phil.. Oxford University Computing Laboratory.
^ A.W. Roscoe (1994). "Model-checking CSP". In A Classical Mind: essays in Honour of C.A.R. Hoare. Prentice Hall.

A. William Roscoe (Bill Roscoe) is director of the Computing Laboratory at the University of Oxford and a Professor of Computing Science. ... Pearson can mean Pearson PLC the media conglomerate. ... The INMOS Transputer was a pioneering parallel computing microprocessor design of the 1980s from INMOS, a small English company. ... 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, in 1960. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ... A digital object identifier (or DOI) is a standard for persistently identifying a piece of intellectual property on a digital network and associating it with related data, the metadata, in a structured extensible way. ... The Institute of Electrical and Electronics Engineers or IEEE (pronounced as eye-triple-ee) is an international non-profit, professional organization incorporated in the State of New York, United States. ... A digital object identifier (or DOI) is a standard for persistently identifying a piece of intellectual property on a digital network and associating it with related data, the metadata, in a structured extensible way. ... The Institute of Electrical and Electronics Engineers or IEEE (pronounced as eye-triple-ee) is an international non-profit, professional organization incorporated in the State of New York, United States. ... The University of Oxford, located in the city of Oxford in England, is the oldest university in the English-speaking world. ... 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, in 1960. ... The Oxford University Computing Laboratory (OUCL) is the computer science department at Oxford University in England. ... 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, in 1960. ... A. William Roscoe (Bill Roscoe) is director of the Computing Laboratory at the University of Oxford and a Professor of Computing Science. ... The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ... A digital object identifier (or DOI) is a standard for persistently identifying a piece of intellectual property on a digital network and associating it with related data, the metadata, in a structured extensible way. ... The Oxford University Computing Laboratory (OUCL) is the computer science department at Oxford University in England. ... A. William Roscoe (Bill Roscoe) is director of the Computing Laboratory at the University of Oxford and a Professor of Computing Science. ...

Contents