From: Ron Ten-Hove <Ronald.Ten-Hove@Sun.COM>

Date: Mon, 24 Nov 2003 10:57:17 -0800

To: Andrew Berry <andyb@whyanbeel.net>

Cc: public-ws-chor@w3.org

Message-id: <3FC2548D.4080501@sun.com>

Date: Mon, 24 Nov 2003 10:57:17 -0800

To: Andrew Berry <andyb@whyanbeel.net>

Cc: public-ws-chor@w3.org

Message-id: <3FC2548D.4080501@sun.com>

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 >Received on Monday, 24 November 2003 14:20:38 UTC

*
This archive was generated by hypermail 2.4.0
: Friday, 17 January 2020 19:30:14 UTC
*