Questions: Process Calculi: CCS and Pi-Calculus

Question 1

In CCS, what happens when process P = a.P' is placed in parallel with process Q = a-bar.Q' (where a-bar is the co-action of a)?

• A. Both processes block forever because they are trying to use the same channel
• B. P sends on channel a and Q receives on a (the complementary actions synchronize), producing a silent tau transition, and the system evolves to P' | Q'
• C. The parallel composition is invalid because two processes cannot use the same channel
• D. One process is chosen nondeterministically and the other is discarded

Answer: (B)

CCS models communication by synchronization on complementary actions. Action a represents one direction (conventionally an output) and a-bar the other (input). When P offers a and Q offers a-bar, they can synchronize, producing an internal (tau) transition. The resulting system P' | Q' continues with whatever behavior the respective continuations specify. This handshake mechanism is the fundamental communication primitive in CCS.

Question 2

The pi-calculus extends CCS by allowing channel names to be transmitted as messages. Why is this capability important?

Model answer: Name passing enables dynamic reconfiguration of communication topology. A process can receive a channel name and then use it to communicate with a previously unknown partner, modeling scenarios like passing a callback, establishing a private communication link, or delegating a session to another process. CCS's communication topology is fixed by the process syntax; the pi-calculus's topology can evolve during execution, making it expressive enough to model mobile and reconfigurable systems.

This is the fundamental innovation of the pi-calculus: communication channels are first-class values that can be created, passed, and received. The process (new c)(a<c>.P | a(x).Q) creates a fresh channel c, sends it over a, and the receiver Q can then communicate on c — establishing a private link that did not exist before. This expressiveness makes the pi-calculus a natural foundation for modeling object-oriented systems (objects are processes, method calls are channel communications), mobile code, and session-based protocols.

Question 3

What is bisimulation, and why is it preferred over trace equivalence for comparing processes in CCS?

Model answer: Bisimulation is a relation R between processes such that if (P, Q) are in R and P can do action a to become P', then Q can do action a to become Q' where (P', Q') is also in R — and vice versa. It is preferred over trace equivalence because trace equivalence only compares the sequences of visible actions (traces) while ignoring branching structure. Two processes can have the same traces but different branching behavior (one offers a choice that the other does not), and bisimulation distinguishes them. Bisimulation captures the full observable behavior including when choices are made.

The classic example: P = a.b + a.c (choose between doing a-then-b or a-then-c) and Q = a.(b + c) (do a, then choose between b and c). These have the same traces ({ab, ac}) but are NOT bisimilar: P commits to b or c before doing a, while Q commits after a. An external observer interacting with P can force the choice of b-or-c before a completes, but cannot do so with Q. Bisimulation respects this difference, making it the standard equivalence in process calculi.

Question 4

The pi-calculus can encode the lambda calculus, making it Turing-complete.

• T. True
• F. False

Answer: True

Milner showed that the pi-calculus can faithfully encode the lambda calculus: every lambda term can be translated into a pi-calculus process that simulates its reduction behavior. This means the pi-calculus is Turing-complete — it can express any computable function. The encoding works by representing function application as communication: applying a function sends the argument on the function's channel and receives the result. This universality result establishes the pi-calculus as a foundational model of computation alongside the lambda calculus and Turing machines.