Communicating Sequential Processes (CSP)

Question 1

Explain:

Decomposition as basic idea of CSP?

Answer 1

The basic idea of CSP is to provide means to design systems which by their nature comprise of concurrent tasks which interact between each other and with the common environment of all of them.

Question 2

Benefits of CSP decomposition?

Answer 2

Many traditional problems of concurrent programming can be avoided:

• interference
• mutual exclusion
• interrupts
• multithreading
• semaphores

These problems appear as properties of multithreaded, single process software and/or synchronization primitives needed for solving the same.

Question 3

CSP as mathematical tool?

Answer 3

As mathematical tool it provides good formal foundation for avoidance of errors such as divergence, deadlock and non-termination.

With the mathematical foundation it is easier to achieve provable correctness.

Question 4

Alphabet of events.

Answer 4

Alphabet of events is set of all possible events happening in relation to an object.

Examples:

• {choc, coin}
• {in1p, in2p, in5p, small, large, out1p}

Question 5

Define:

Process

Answer 5

Process is defined as behavior patter of an object manifested as the series of events from the available alphabet associated with the object.

Question 6

Notational conventions:

Answer 6

• lowercase words - events {a, b, choc}
• uppercase words - processes {X, Y, VMS}
• lowercase letters - event variables (x)
• uppercase letters - sets of events X, Y
• alphabet of process - αP
  
  • αVMS = {coin, choc}
• process that neve engages with events of its alphabet - STOP_A- STOP_αVMS

Question 7

Define:

Prefix

(x → P)

Answer 7

Pronounced **“x then P” **describes an object which first engages with event x and then behaves as described by P.

• alphabet of (x → P) and P is the same: α(x → P) = αP assuming x ∈ αP

Examples:

• (coin -> (choc -> (coin -> STOP_αVMS)))
• (right -> up -> right -> up -> STOP_αCTR)

Question 8

(x -> y) and (P -> Q)

Answer 8

These forms are syntactically incorrect ways to write the prefix based description of behavior of an object.

P -> Q is not correct

(x -> y -> STOP) is the correct way to write the event sequence.

Question 9

Recursive notation of processes (object behaviors).

Answer 9

Provides more compact notation for the processes which cycle through set of events.

Question 10

Explain:

Recursive definition of the process

CLOCK = (tick -> CLOCK)

Answer 10

• αCLOCK = {tick}

1. consider an object that does nothing but ticks.
2. Second, consider an object that behaves exactly the same but is prefixed by a tick event (tick -> CLOCK)

This one can not be differentiated from the first one so: CLOCK = (tick -> CLOCK)

It provides potential for unbounded unfolding: (tick -> (tick -> tick -> (tick -> ….)))

Question 11

Define:

guarded process description.

Answer 11

Process description that starts with a prefix is called guarded process description.

F(X) = (x -> X)

Question 12

Define:

Process equation and uniqueness of its solution

Answer 12

If F(X) is a guarded process description expression containing process name X, and A is alphabet of X then

X = F(X)

has a unique solution with alphabet A.

This solution is something more convenient to denote as
µX:A • F(X)

read as “process X with alphabet A such that X = F(X)”

Question 13

Example:

VMS = (coin -> (choc -> VMS))

vs

VMS = µX:{coin, choc} • (coin -> (choc -> X))

Answer 13

Second representation is a more formal definition of the same thing above expressing the alphabet and the expression used to recursively define it.

As well it defines it in an abstract way so that it doesn’t depend on a exact name so that it can be used in other equations.

Question 14

Explain:

Reasoning behind the solutions of the guarded equations.

Answer 14

Claim that guarded equations have a solution and that it is unique can be justified through the substitutions.

Any finite amount of behavior can be expressed by substituting the process within the RHS of the equation.

If two objects have same bahavior until some period in time they are essentially same process.

Question 15

Define:

choice

(x -> P | y -> Q)

“x then P choice y then Q”

Answer 15

By prefix and recursion we can just describe processes which are sequential.

Introduction of choice provides option to have different behavior based on the interaction of an object with its environment.

(x -> P | y -> Q) describes and object which first engages with event x or y and proceeds with the process P or Q respectively.

α(x → P | y → Q ) = αP provided {x, y} ⊆ αP and αP = αQ

Question 16

Provide some examples of non-trivial processes with the choice as part of its behavior.

Answer 16

Free form thinking :)

Question 17

Define:

multiple choice processes

Answer 17

In practice processes might have part of the alphabet or whole alphabet in the choice providing some kind of *menu *of prefixes based on alphabet.

(x:B → P(x)) would define the set of choices based on the alphabet B and set of expressions which are following the choice x. Every x would have its own P(x) value from the set of expressions.

Question 18

Explain example:

(a -> P | b -> Q) = (x:B -> R(x))

R(x) = if x == a then P else Q

Answer 18

This example shows the operational meaning of the choice menu notation for the restriction to 2 processes.

Question 19

Mutual recursion and indexed representation of the mutually recursive processes.

Answer 19

Definition of only one process is somewhat limited.

With the mutual recursion we introduce ability to express transition between different process by exercising the events from a mutually shared alphabet.

With the indexed representation we can make expressions that are generalized to unlimited number of involved processes.

Question 20

Explain an example of the mutually recursive process (up, down moving body, around on ground).

Answer 20

Example of a body moving in the air up and down and around on the floor

CT0 = (up → CT1 | around → CT0)
CTn+1 = (up → CTn+2 | down → CTn)

Question 21

Explain law:

(x:A → P(x)) = (y:B → Q (y)) ≡ (A = B ∧ ∀ x:A • P(x) = Q (x))

Answer 21

Two processes with the set of choices are the same if their alphabets are the same and if after every selected choice following process is the same in both cases.

Question 22

Explain law:

If F(X) is a guarded expression

then

Y = F(Y) ≡ (Y = µX • F(X))

Answer 22

This laws is a formalization of the statement that equation

X = F(X)

has only one solution.

Example describes the power of the definition:

Let VM1 = (coin → VM2) and VM2 = (choc → VM1)
Required to prove VM1 = VMS.

Proof : VM1 = (coin → VM2)
= (coin → (choc → VM1))

Therefore VM1 = VMS

Question 23

Explain generalization of the law of the uniqueness of the guarded equation solution to the mutually recursive processes.

if (∀ i : S • (Xi = F (i, X ) ∧ Yi = F (i, Y))) then X = Y

Answer 23

Set of guarded equations can be defined as

X_i = F(i, X), for all i in S

• S - indexing set for a member for each equation
• X - array of proceeses
• F(i, X) - guarded expression for the case i

The law states that there is only one array whose elements satisfy all the equations.