Series: Logic Seminar

Date: Tuesday, November 2, 1999

Speaker: Mihaela Herescu (Penn State, Computer Science)

Title: A Randomized Implementation of the Pi-Calculus with Mixed
Choice, Part 1

Time: 2:30 - 3:20 PM

Place: 122 Thomas Building

Abstract: 

The pi-calculus is a language for the specification of concurrent
processes proposed recently by Milner, Parrow and Walker. It is known
to be very expressive, but not easily implementable in a distributed
system.  A fragment of it, the asynchronous pi-calculus, is on the
other hand less expressive, but easier to implement.

We consider the problem of encoding the pi-calculus into its
asynchronous fragment via a translation which preserves
distribution. It has been shown that this is not possible with an
exact (i.e. deterministic) encoding.  We suggest therefore a
randomized approach, based on extending the asynchronous pi-calculus
with a notion of probabilistic choice.

In this first talk we present the probabilistic extension of the
pi-calculus and its operational semantics, which has the
characteristic of distinguishing between the internal probabilistic
behaviour and the nondeterministic behaviour of an external
scheduler. This separation will allow us to reason about "adversary
schedulers", i.e. schedulers which do not cooperate or even try to
sabotage the attempts of the system to achieve certain goals.
Furthermore, we show an implementation of this langauge in a Java-like
language.