Pi for distributed computation

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

Received on Sunday, 23 November 2003 07:31:20 UTC