<p>Sequential execution is an edge case of concurrent computation.
Robin Milner said this clearly in his  Turing award lecture "<a href="http://delivery.acm.org/10.1145/160000/151240/a1991-milner.pdf?ip=36.227.163.83&amp;id=151240&amp;acc=OPEN&amp;key=4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E6D218144511F3437&amp;CFID=510424625&amp;CFTOKEN=66634591&amp;__acm__=1463745922_2a6c485042bece8180bfafad45c49c1e" rel="nofollow">Elements of interaction</a>" (CACM, 36(1), 1993):</p>

<pre><code>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.
</code></pre>

<p>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.</p>

<p>But this insight is much older and forms the essence of the Actor
model. See for example Hewitt's 1976 "<a href="https://dspace.mit.edu/handle/1721.1/6272" rel="nofollow">Viewing Control Structures as
Patterns of Passing Messages</a>".</p>

<p>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. "<a href="http://www.sciencedirect.com/science/article/pii/S0890540104000288" rel="nofollow">Strong Normalisation in the $\pi$-Calculus</a>".</p>

<p>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.</p>

CC BY-SA 3.0
2016-05-20T14:06:59.177Z
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...
anil keshav
CC BY-SA 3.0
2016-05-20T14:42:19.770Z
@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.
Martin Berger
CC BY-SA 3.0
2016-05-20T12:06:55.880Z
2016-05-20T12:06:55.880Z
Martin Berger
<p>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.</p>

<p>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?</p>

<p>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?. </p>

<p><a href="https://i.sstatic.net/K5ZxC.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/K5ZxC.jpg" alt="enter image description here"></a>
<a href="https://i.sstatic.net/2E7GE.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/2E7GE.jpg" alt="enter image description here"></a></p>

CC BY-SA 3.0
2016-05-20T12:12:56.297Z
This question might be better suited to [cs.stackexchange.com](https://cs.stackexchange.com).
Martin Berger
<pi-calculus>
Sequential execution in π-Calculus
anil keshav
# Sequential execution in π-Calculus

(Asked by: username_0 on 2016-05-20)

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](https://i.sstatic.net/K5ZxC.jpg)](https://i.sstatic.net/K5ZxC.jpg)
[![enter image description here](https://i.sstatic.net/2E7GE.jpg)](https://i.sstatic.net/2E7GE.jpg)

**Tags:** pi-calculus
> **Comments:**
> **username_1**: This question might be better suited to [cs.stackexchange.com](https://cs.stackexchange.com).  

---

## 1 answers

### Answer by username_1 on 2016-05-20. Score: 2

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.

> **Comments:**
> **username_0**: 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...  
> **username_1**: @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.  

---

