0
$\begingroup$

I am just starting into process algebra (π-Calculus) for formally defining the operational semantics of a system. One common statement that I come across that π-Calculus is used for Concurrent and parallel processing systems.

However if two processes share the common link and send some token on the same link, where the later process will not begin until it receives the token then does it represent a sequential execution in π-Calculus ? , is my understanding correct?

So the below shows a sequential execution between process P and Q where: first process P outputs y on channel x and then process Q shares the same channel x and get the token y on it and only then begin?.

enter image description here enter image description here

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

Sequential execution is an edge case of concurrent computation. Robin Milner said this clearly in his Turing award lecture "Elements of interaction" (CACM, 36(1), 1993):

I reject the idea that there can be a unique conceptual model,
or one preferred formalism, for all aspects of something as large
as concurrent computation, which is in a sense the whole of our
subject – containing sequential computation as a well-behaved
special area.

You can see sequential computation as a form of well-behaved, nice concurrent computation. This niceness comes out when comparing the processes of reasoning about, an implementing sequential vs concurrent computation.

But this insight is much older and forms the essence of the Actor model. See for example Hewitt's 1976 "Viewing Control Structures as Patterns of Passing Messages".

There are various ways of enforcing sequential computation in process calculus. A simple one is only to allow processes that have at most one active output, i.e. an output that is not under an input prefix. This can be enforced by typing see e.g. "Strong Normalisation in the $\pi$-Calculus".

Now coming to your question: does interaction on $x$ in $x(v).P \ |\ \overline{x}y.Q \rightarrow P[y/v] \ |\ Q$ represent sequential behaviour as such? No. The reason is that other processes could be running in parallel with $x(v).P \ |\ \overline{x}y.Q$. All we are seeing here is an exchange of messages, a handshake, where the receiver has to wait until the sender's message arrives.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thank you for the answer, However given a scenario where a series of processes wait for the predecessor to receive handshake messages is the same as sequential execution ? and during the current domino execution , no processes run in parallel... $\endgroup$
    – anil keshav
    May 20, 2016 at 14:06
  • 1
    $\begingroup$ @anilkeshav I'm not sure I understand your question. If specific processes exhibit sequential behaviour, yes, then they exhibit sequential behaviour. But why is this an interesting statement? You can model sequential models of computing like Turing machines in $\pi$-calculus, so all sequential behaviour is a special case of $\pi$-calculus. But sequential behaviour is but a small subset of behaviour that can be modeled in $\pi$-calculus. $\endgroup$
    – Martin Berger
    May 20, 2016 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.