Communicating Sequential Processes

Communicating Sequential Processes (CSP) is theoretical one of the process calculations about the parallel nature [¹]. Affected programming language Occam [²]; [¹].

Anthony Hoar devised CSP first in 1978 [³] and was considerably improved afterwards. CSP was industrial, and it has been used as a form specifications description tool to describe parallel characteristics in various systems, and to inspect. For example, there are the examples such as T9000 transformer pewter [⁴] or the secure electronic commerce system [⁵]. Studies such as (^[6] that I am usable for the analysis of the large-scale system) which widens an applied range as a theory are conducted.

Table of contents

History

CSP shown in an article of 1978 of Hoar was a parallel programming language rather than a process calculation essentially. I was not able to express unlimited non-conclusiveness without a sentence structure being remarkably different from later CSP, and having semantics defined mathematically [⁷] [⁸]. The sequential process of the limited unit to work in parallel was synchronization-style message passing and, in original CSP, described a program in a form to communicate mutually. In contrast with later CSP, the name is added to each process, and the name of an origin of transmission and the transmission is appointed in a message. It is, for example, the next process

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

Oh, I receive a letter from a process named west repeatedly and send the letter to a process named east. Parallel composition

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

Then I assign the name called west to DISASSEMBLE process and assign the name called X to COPY process and assign the name called east to ASSEMBLE process and carry these out in parallel [³].

Hoar worked on the improvement of the theory side with Stephen Brookes and Bill Roscoe and others and performed a process of CSP algebraically afterwards. This directionality influences it with a study of Calculus of Communicating Systems (CCS) which Robin Milner went for the same period mutually. The theory side of CSP was announced in 1984 [⁹] and came to be known generally in book Communicating Sequential Processes^[7] of Hoar published in 1985. As of September, 2006, according to Citeseer, this book is considered to be the quotation number of times third place in the field of comp-sci (but the reliability is not high because it is a sampling method). After a book of this Hoar, some theories of CSP were only changed. The most of the change support the appearance of the automation tool for CSP process analysis and inspection. This new CSP is commented on in The Theory and Practice of Concurrency^[1] of Roscoe.

Summary

CSP describes a system as the thing which exchanges mutually because independent process group communicates by message passing as the name shows it. However, the part called "Sequential" (sequential) included in the name of CSP may produce misunderstanding. Because, in recent CSP, the process is because not only the simple sequential process but also the process generated by parallel composition of a more basic process group is included. The method that relations and the process between processes communicate with people is expressed using various process algebra operators. I can build an extremely complicated process from few primitive elements easily by using such an algebraic technique.

Primitive

CSP provides the class of two kinds of primitives in the process algebra.

Event

The event means communication or interaction. I am considered momentary by indivisibility. Indivisibility name (e.g.${\displaystyle {\mathit {on}}}$ ,${\displaystyle {\mathit {off}}}$ ), the compound name (e.g.${\displaystyle valve.open}$ ,${\displaystyle valve.close}$ ), input and output event (e.g.${\displaystyle mouse?xy}$ ,${\displaystyle screen!bitmap}$ There is).

Primitive process

The primitive process referred to basic behavior. For example,${\displaystyle {\mathit {STOP}}}$ (it is a process not to communicate at all and says the deadlock)${\displaystyle {\mathit {SKIP}}}$ There is (I express that it is finished successfully).

Algebra operator

Various algebra operators are in CSP. I nominate below a main thing.

Pre-fix

The pre-fix operator couples a process with an event and generates a new process. For example,

${\displaystyle a\rightarrow P}$ 

Oh,${\displaystyle {\mathit {a}}}$  It is にその environment and the process that is going to let you communicate,${\displaystyle {\mathit {a}}}$  In after の, it is a process ${\displaystyle {\mathit {P}}}$  I serve として.

Decisive choice

The decisive (or outside) choice operator assumes the future of the process definition possibility by the choice between two component processes, and enables what environment chooses by process group and the exchanges with the initial event. For example

${\displaystyle \left(a\rightarrow P\right)\Box \left(b\rightarrow Q\right)}$ 

Oh, it is an initial event ${\displaystyle {\mathit {a}}}$  And ${\displaystyle {\mathit {b}}}$  It was the process that was going to perform とやり collecting, and did environment choose the thing that I exchanged with an event in the early days of which?${\displaystyle {\mathit {P}}}$  Or ${\displaystyle {\mathit {Q}}}$  I come to serve として.${\displaystyle {\mathit {a}}}$  And ${\displaystyle {\mathit {b}}}$  At the same time when I exchange it, the choice becomes non-decisive.

Non-decisive choice

The non-decisive (or internal) choice operator is a thing to be able to define the future of the process by the choice between two component processes, but cannot control it which component process environment chooses. For example

${\displaystyle \left(a\rightarrow P\right)\sqcap \left(b\rightarrow Q\right)}$ 

Oh,${\displaystyle \left(a\rightarrow P\right)}$  Or ${\displaystyle \left(b\rightarrow Q\right)}$  I serve のどちらかとして.${\displaystyle {\mathit {a}}}$  Or ${\displaystyle {\mathit {b}}}$  Can refuse to receive を; environment ${\displaystyle {\mathit {a}}}$  と ${\displaystyle {\mathit {b}}}$  When I donate both の, I only communicate with it. When two initial events that it is decisive choice, and are a choice are the same, non-conclusiveness produces it. Therefore, for example,

${\displaystyle \left(a\rightarrow a\rightarrow STOP\right)\Box \left(a\rightarrow b\rightarrow STOP\right)}$ 

It is equivalent with は next.

${\displaystyle a\rightarrow \left(\left(a\rightarrow STOP\right)\sqcap \left(b\rightarrow STOP\right)\right)}$ 

Interleave

The operator to interleave completely expresses independent parallel movement. The next process

${\displaystyle P\;\vert \vert \vert \;Q}$ 

Oh,${\displaystyle {\mathit {P}}}$  と ${\displaystyle {\mathit {Q}}}$  But, I mean that I work in parallel at the same time. The event that both processes produce is interleaved on chronological order.

An interface is parallel

The interface parallel operator expresses parallel movement to need synchronization between component processes. The event in the interface occurs only when all component processes can affect the event. For example, it is the next process

${\displaystyle P\left\vert \left[\left a\right \right]\right\vert Q}$ 

Oh, it is an event ${\displaystyle {\mathit {a}}}$  But, before occurring ${\displaystyle {\mathit {P}}}$  と ${\displaystyle {\mathit {Q}}}$  But, I mean that it is necessary to be in a condition to be able to handle the event together. Therefore, for example, it is the next process

${\displaystyle \left(a\rightarrow P\right)\left\vert \left[\left a\right \right]\right\vert \left(a\rightarrow Q\right)}$ 

Oh, it is an event ${\displaystyle {\mathit {a}}}$  I can treat を and can express it as follows.

${\displaystyle P\left\vert \left[\left a\right \right]\right\vert Q}$ 

One

${\displaystyle \left(a\rightarrow P\right)\left\vert \left[\left a,b\right \right]\right\vert \left(b\rightarrow Q\right)}$ 

Oh, I mean simple deadlock.

Concealment

The concealment operator provides the abstraction means of the process that I cannot observe some kind of events. As an example of the concealment of the next

${\displaystyle \left(a\rightarrow P\right)\setminus \left a\right}$ 

Oh, it is an event ${\displaystyle {\mathit {a}}}$  But ${\displaystyle {\mathit {P}}}$  It is omissible as follows when I shall not appear in の.

${\displaystyle {\mathit {P}}}$ 

Example

I consider the interaction with the person who is going to purchase the abstract expression and chocolate of the vending machine of the chocolate as an example of simple CSP. This vending machine handles two event "coin" and "choc". "coin" expresses injection of the price, and "choc" expresses delivery of the chocolate. The machine which requires payment of the price before handing chocolate is described as follows.

${\displaystyle VendingMachine=coin\rightarrow choc\rightarrow STOP}$ 

The person using a coin or the card is modelled as follows to pay.

${\displaystyle Person=(coin\rightarrow STOP)\Box (card\rightarrow STOP)}$ 

It allows you to exchange each other by putting these two processes in parallel. The behavior of the synthetic process depends for the event that two processes must synchronize. In other words,

${\displaystyle VendingMachine\left\vert \left[\left coin,card\right \right]\right\vert Person\equiv coin\rightarrow choc\rightarrow STOP}$ 

When synchronization is required only about "coin" here, the following is provided.

${\displaystyle VendingMachine\left\vert \left[\left coin\right \right]\right\vert Person\equiv \left(coin\rightarrow choc\rightarrow STOP\right)\Box \left(card\rightarrow STOP\right)}$ 

I am as follows when I abstract this synthetic process by concealing an event called "coin" and "card".

${\displaystyle \left(\left(coin\rightarrow choc\rightarrow STOP\right)\Box \left(card\rightarrow STOP\right)\right)\setminus \left coin,card\right}$ 

Thus, the next non-conclusiveness process is provided.

${\displaystyle \left(choc\rightarrow STOP\right)\sqcap STOP}$ 

That this stops after "choc" event is merely a process to stop. In other words, non-conclusiveness occurs if I handle the abstraction mentioned above as the thing which looked at the system from the outside (if, i.e., I ignore the decision that a human being made).

Formal definition

Sentence structure

The sentence structure of CSP defines the method that "is justice" of the combination of the event as a process.${\displaystyle {\mathit {e}}}$  を event,${\displaystyle {\mathit {X}}}$  I assume it the set of the を event. Then the basic sentence structure of CSP is defined as follows.

${\displaystyle {\begin{matrix}Proc&::=&STOP&\;\\&|&SKIP&\;\\&|&e\rightarrow Proc&(prefixing)\\&|&Proc\;\Box \;Proc&(external\;choice)\\&|&Proc\;\sqcap \;Proc&(nondeterministic\;choice)\\&|&Proc\;\vert \vert \vert \;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}}}$ 

It is the sentence structure definition mentioned above to simplify it ${\displaystyle \mathbf {div}}$  I omit a parallel operator and piping operator of a process (I express the emission) and the alphabetical order or the choice operator with the index.

Formal semantics

The correction of this knob is expected.

There is several formal semantics to define the meaning of the expression of right CSP grammatically. A theory of CSP has semantics of was consistent mutually, displaying it, algebraic semantics, operational semantics.

Semantics of displaying it

A model of CSP is important, displaying it includes three of trace model, stable failure model, the failure / emission model. Process expression and the semantic mapping with these models become the semantics of displaying it of CSP [¹].

The trace model defines the meaning of the process expression by a series of events (trace) that the process handles. For example,

• ${\displaystyle traces\left(STOP\right)=\left \langle \rangle \right}$  Because ${\displaystyle STOP}$  Because I do not handle no は event
• ${\displaystyle traces\left(a\rightarrow b\rightarrow STOP\right)=\left \langle \rangle ,\langle a\rangle ,\langle a,b\rangle \right}$  It is a process ${\displaystyle (a\rightarrow b\rightarrow STOP)}$  Oh, when handle no event; an event ${\displaystyle a}$  When accept を; an event ${\displaystyle a}$  It is an event after a beam with を tray ${\displaystyle b}$  Because three cases when I accept を are possible

If express it formally; a process ${\displaystyle P}$  The meaning in the の trace model ${\displaystyle traces\left(P\right)\subseteq \Sigma ^{\ast}}$  It is defined として. In other words,

1. ${\displaystyle \langle \rangle \in traces\left(P\right)}$  (${\displaystyle traces\left(P\right)}$  Including the sequence of the は sky)
2. ${\displaystyle s_{1}\smallfrown s_{2}\in traces\left(P\right)\implies s_{1}\in traces\left(P\right)}$  (${\displaystyle traces\left(P\right)}$  Closed in は プレフィックス)

Here,${\displaystyle \Sigma ^{\ast}}$  は is the set of the limited row of all events thought about.

The stable failure model expanded the trace model by a refusal meeting (refusal set). Set of the event that a process can refuse practice with the refusal meeting ${\displaystyle X\subseteq \Sigma}$  である. The failure (failure) ${\displaystyle \left(s,X\right)}$  I am expressed by という pair. Here ${\displaystyle s}$  は trace,${\displaystyle X}$  It is は refusal meeting and traces it ${\displaystyle s}$  But, I express the event group that the process refuses when it was carried out. The behavior that was observed of the process in the stable failure model,${\displaystyle \left(traces\left(P\right),failures\left(P\right)\right)}$  I am expressed by という pair. For example,

• ${\displaystyle failures\left(\left(a\rightarrow STOP\right)\Box \left(b\rightarrow STOP\right)\right)=\left \left(\langle \rangle ,\emptyset \right),\left(\langle a\rangle ,\left a,b\right \right),\left(\langle b\rangle ,\left a,b\right \right)\right}$ 
• ${\displaystyle failures\left(\left(a\rightarrow STOP\right)\sqcap \left(b\rightarrow STOP\right)\right)=\left \left(\langle \rangle ,\left a\right \right),\left(\langle \rangle ,\left b\right \right),\left(\langle a\rangle ,\left a,b\right \right),\left(\langle b\rangle ,\left a,b\right \right)\right}$ 

The failure / emission model expanded the failure model to be able to handle the emission (divergence). The process in the failure / emission model ${\displaystyle \left(failures_{\perp }\left(P\right),divergences\left(P\right)\right)}$  I am expressed by という pair,${\displaystyle divergences\left(P\right)}$  It is a set of all trace causing the は emission. In addition,${\displaystyle failures_{\perp }\left(P\right)=failures\left(P\right)\cup \left \left(s,X\right)\vert s\in divergences\left(P\right)\right}$  But, it is managed.

Applied

There is an example used for specifications description and the inspection of the INMOS T9000 transformer pewter as an applied example of early important CSP. It is a complicated super scaler model pipeline processor, and T9000 is designed so that large-scale multi-processing is possible. CSP was used for the legitimacy inspection of the pipeline and the inspection of the communication management capability between the tip called Virtual Channel Processor [⁴].

The application of CSP in the software design is accomplished by an important system affecting human life mainly. For example, Bremen Institute for Safe Systems and Daimler-Benz Aerospace modelled a use planned system (approximately 23,000 lines of cords) in CSP at the International Space Station, and inspected that deadlock and live Locke did not get up [¹⁰]; [¹¹]. By this modeling and analysis, I discovered some problems that had difficulty in detection on the normal software test. Similarly, I inspected that security and deadlock did not occur by development of the secure IC card authentication system (approximately 100,000 lines of cords) using CSP in Praxis High Integrity Systems. Praxis insists that a defect rate of the system lowered than other equal systems [⁵].

Because CSP was suitable for modeling and the analysis of the complicated system which performed message switching, it has been applied to inspection of communication protocol and the security protocol. With the example which developed the new protocol that inspected Needham-Schroeder public key certification protocol as a notable applied example using CSP, and discovered unknown weakness, and dealt with it [¹²].

Tool

The correction of this knob is expected.

Some tools to analyze by expressing a system using CSP have been produced for many years. Because the expression of CSP which a computer could understand was various as for the early tool, I was not able to share information between tools. However, scale CSP_M^[13] of Bryan Scattergood is used with much CSP tools recently. A form definition of the operational semantics is in CSP_M, and the functional language including the composing type is included.

There is Failures/Divergence Refinement 2 (FDR2) which is the commercial product which Formal Systems Europe Ltd. developed as the most famous CSP tool. Gee, in FDR2, a model is often considered to be a mosquito, but, gee, improvement is a mosquito technically. In other words, I convert two CSP process expression into transition system with the label and check whether one becomes other improvement in an appointed semantics model (trace, failure, the failure / emission) [¹⁴].

There are other the following CSP tools.

• ProBE
• ARC
• Casper

Associated form technique

Other form technique and specifications description languages affected by CSP include the following.

• CSP where I added information to for Timed CSP, real time systems in a timing
• CSP where I added Receptive Process Theory, async (I do not block it) transmission operation to
• Wright, architecture description language
• I integrated Object Z (the Z language that I introduced object oriented into) with TCOZ, Timed CSP
• I integrated CSP with Circus, Z language
• I integrated CSP with CspCASL, CASL

Allied item

• The language that implemented the parallel nature in the Limbo - Inferno operating system. I am affected by CSP.
• There is the thread library that Plan 9 - C language can describe the CSP-like parallel nature.

Footnote

1. ^ ^{a b c d} Roscoe, A. W. (1997). The Theory and Practice of Concurrency. Prentice Hall. ISBN 0-13-674409-5. 
   • The link in conjunction with this book is right here. I can download the whole sentence from this list of Bill Roscoe in PS form or Portable Document Format.
2. ^ INMOS (May 12, 1995). occam 2.1 Reference Manual. SGS-THOMSON Microelectronics Ltd.. http://www.wotug.org/occam/documentation/oc21refman.pdf. , INMOS document 72 occ 45 03
3. ^ ^{a b} Hoare, C. A. R. (1978). "Communicating sequential processes." Communications of the ACM 21 (8): 666–677. doi: 10.1145/359576.359585. 
4. ^ ^{a b} 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. 
5. ^ ^{a b} Hall, A; R. Chapman (2002). "Correctness by construction: Developing a commercial secure system". IEEE Software 19 (1): 18–25. http://www.anthonyhall.org/c_by_c_secure_system.pdf. 
6. ^ Creese, S. (2001). Data Independent Induction: CSP Model Checking of Arbitrary Sized Networks. D. Phil.. Oxford University. 
7. ^ ^{a b} Hoare, C. A. R.. Communicating Sequential Processes. Prentice Hall. ISBN 0-13-153289-8. 
   • As for this book, Jim Davis of the Oxford University computer research institute makes version up, and the new publication is downloadable in Portable Document Format in a site called Using CSP.
8. ^ William Clinger (June, 1981). Foundations of Actor Semantics. Mathematics Doctoral Dissertation. MIT. https://dspace.mit.edu/handle/1721.1/6935. 
9. ^ 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. 
10. ^ Buth, B.; M. Kouvaras, J. Peleska, and H. Shi (December, 1997). "Deadlock analysis for a fault-tolerant system." Proceedings of the 6th International Conference on Algebraic Methodology and Software Technology (AMAST '97). pp. pp. 60–75 
11. ^ Buth, B.; J. Peleska, and H. Shi (January, 1999). "Combining methods for the livelock analysis of a fault-tolerant system." Proceedings of the 7th International Conference on Algebraic Methodology and Software Technology (AMAST '98). pp. pp. 124–139 
12. ^ Lowe, G. (1996). "Breaking and fixing the Needham-Schroeder public-key protocol using FDR". Tools and Algorithms for the Construction and Analysis of Systems (TACAS). Springer-Verlag. pp. pp. 147–166.. http://citeseer.ist.psu.edu/lowe96breaking.html 
13. ^ Scattergood, J.B. (1998). The Semantics and Implementation of Machine-Readable CSP. D.Phil.. Oxford University Computing Laboratory. 
14. ^ A.W. Roscoe (1994). Model-checking CSP. In A Classical Mind: essays in Honour of C.A.R. Hoare. Prentice Hall. 

Outside link

• User group of WoTUG CSP and Occam
• I develop Formal Systems Europe, Ltd. CSP tool, and free can download a part
• The implementation that introduced a concept of JCSP CSP into thread API of the JAVA
• Implementation by the JAVA of CTJ CSP
• Implementation in the C++ of C++CSP CSP
• CSP implementation (business) in JIBU .NET and others
• The tool which generates a code of the C++ from specifications description by CSP++ CSP
• A library for Common Lisp which can describe csp CSP-like parallel-related model.
• Macro to add a CSP-like function to VerilogCSP Verilog

It is acquired by "https://ja.wikipedia.org/w/index.php?title=Communicating_Sequential_Processes&oldid=57049327"

This article is taken from the Japanese Wikipedia Communicating Sequential Processes

This article is distributed by cc-by-sa or GFDL license in accordance with the provisions of Wikipedia.

Wikipedia and Tranpedia does not guarantee the accuracy of this document. See our disclaimer for more information.

In addition, Tranpedia is simply not responsible for any show is only by translating the writings of foreign licenses that are compatible with CC-BY-SA license information.