Re: Pi for distributed computation

Andy,

    Hennesy and Riely 
<http://citeseer.nj.nec.com/cache/papers/cs/8736/http:zSzzSzwww.infosys.tuwien.ac.atzSzResearchzSzAgentszSzarchivezSz98TR-resources.pdf/hennessy98resource.pdf> 
have published the distributed pi-calculus D?. This introduces named 
locations and channels connecting locations. Other researchers are 
expanding on this work. September's ACM Transactions on Programming 
Languages and Systems has a paper on something termed The Receptive 
Distributed ?-Calculus, which is quite interesting.

    The pi-calculus is evolving to address some of the issues you 
raised, but "classic" pi-calculus is not the silver bullet some would 
have us believe it is. It is a useful model.

Cheers,
-Ron

Andrew Berry wrote:

>
> As I've stated previously, I have many doubts about the suitability of 
> pi calculus for modelling distributed computation. Greg suggested in a 
> previous email that pi calculus is more powerful than other 
> formalisms, in particular having:
>
>> 1. completeness -- i.e. Turing complete
>> 2. compositionality -- the model is an algebra, the practical advantage
>> of which is that large(r) programs are built from small(er) ones
>> 3. concurrency -- the model has an explicit account of autonomous
>> execution
>> 4. cost -- the model has an explicit account of resources like time and
>> space
>
>
> While I'm not a sufficiently experienced theorist to dispute the 
> utility of these properites, my argument against pi calculus is based 
> on fundamental problems in the operational semantics that cannot 
> easily be overcome through adding to a framework based on pi 
> calculus.  There are workarounds, but the cumulative effect of 
> applying those workarounds weakens the model significantly in my 
> opinion.  Specifically:
>
> 1. Locality is a fundamental concept.  Any reasoning about partial 
> state, composition and communication must recognise locality.  
> Previous email on this topic has discussed the issues.
> 2. Causality is a fundamental concept.  In particular, it must be 
> possible to determine and specify that two occurences are causally 
> related or unrelated.  The interleaved concurrency model of pi 
> calculus requires that either A happened before B or B happened before 
> A.  In a distributed system, this is simply not the case.  When 
> reasoning about or auditing the execution of a distributed process, 
> the distinction is very important.
> 3. Time is an essential part of the model.  While reasonably accurate 
> synchronisation of time is possible in a co-operative environment, the 
> reality is that time is only loosely synchronised in a distributed 
> setting with autonomous participants.  A non-linear model of time tied 
> to locality is preferable.
>
> I cannot point at a widely-recognised model for distributed 
> computation that addresses these issues adequately.  My own work 
> proposes a model but is limited in scope and has not been pursued to 
> an extent that allows us to reason about distributed computations 
> specified in terms of the model.  There is a fairly solid basis for 
> reasoning about its partially-ordered model in event structures 
> (Winskel) but again this has not yet been pursued.
>
> So where do we go?  It is possible that the approximation of a 
> distributed computation provided by pi calculus is sufficient for the 
> purposes of a CDL when augmented with semantics for locality etc.  It 
> is also possible that it is insufficient or unworkable: the gaps that 
> have already been identified are significant.  Until proven in this 
> context, I think it would be dangerous to assume pi calculus will work 
> and not explore alternatives.
>
> Ciao,
>
> AndyB
>