Asynchronous pi-calculus at Work: The Call-by-Need Strategy

In a well-known and influential paper [17] Palamidessi has shown that the expressive power of the Asynchronous π-calculus is strictly less than that of the full (synchronous) $π$-calculus. This gap in expres-siveness has a correspondence, however, in sharper semantic properties for the former calculus, notably concerning algebraic laws. This paper substantiates this, taking, as a case study, the encoding of call-by-need λ-calculus into the $π$-calculus. We actually adopt the Local Asynchronous π-calculus, that has even sharper semantic properties. We exploit such properties to prove some instances of validity of $β$-reduction (meaning that the source and target terms of a $β$-reduction are mapped onto be-haviourally equivalent processes). Nearly all results would fail in the ordinary synchronous $π$-calculus. We show that however the full $β$-reduction is not valid. We also consider a refined encoding in which some further instances of $β$-validity hold. We conclude with a few questions for future work.