[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[moca] Re: RE: RE : synchronous implementation of Pi calculus with choice?
Hi,
> The thing that struck me is the problem of implementing a language
which
> may have multiple channels involved in multiple distributed choice
> operations.
Besides the problem of failures that is already being discussed by
others people in this forum, there is another consensus problem
that arises when trying to implement in a distributed system a language
like the full pi-calculus (as described in the first paper on the
pi-calculus by Milner et al.) or more in general a language with mixed
choice, i.e. choice involving both input and output channels(*). This
is
related to impossibility results like the leader election on certain
symmetric networks or the (symmetric) dining philosophers.
If you are interested, you can find a description of the problem on
C. Palamidessi. Comparing the Expressive Power of the Synchronous and
the Asynchronous pi-calculus. Mathematical Structures in Computer
Science. To appear.
(http://www.cse.psu.edu/~catuscia/papers/pi_calc/mscs.ps)
Mihaela Herescu and myself have proposed a probabilistic solution to
the
problem: we have gives an embedding of the full pi-calculus in a
probabilistic version of the asynchronous pi-calculus, and we have
proposed a distributed implementation of the latter (the code is
written
in Java, but the implementation is distributed in the sense that it
uses
message-passing, not shared memory). You can find the details in
M. Herescu and M. Herescu. Probabilistic asynchronous $\pi$-calculus.
Proceedings of FOSSACS 2000, volume 1784 of Lecture Notes in Computer
Science, pages 146--160. Springer-Verlag, 2000.
(http://www.cse.psu.edu/~catuscia/papers/Prob_asy_pi/report.ps)
C. Palamidessi and M. Herescu.A Randomized Distributed Encoding of the
Pi-Calculus with Mixed Choice. IFIP TCS 2002: 537-549
(http://www.cse.psu.edu/~catuscia/papers/prob_enc/report.ps)
Mihaela Herescu, Phd Thesis. http://www.cse.psu.edu/~herescu/thesis.ps
(*) Note: I think that the full pi-calculus with mixed choice is
more suitable than its less expressive versions (pi-calculus with
input-guarded choice only, asynchronous pi-calculus), to describe
transactions. I am very much interested in this topic too.
Unfortunately
I am traveling and I am not able to check my email regularly. I will be
back next Monday and I hope it won't be too late to be involved in this
very interesting discussion.
Greetings to all the people of the moca list, -Catuscia
__________________________________________________
Do you Yahoo!?
Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The "models for mobility" mailing list mailto:moca@xxxxxxxxxxxxxxx
http://www-sop.inria.fr/mimosa/personnel/Davide.Sangiorgi/moca.html