Re: [moca] Locality and Name matching in Pi-Calculus.

[Martin Berger <martinb@xxxxxxxxxxxxxx>]

Reza Ziaei wrote:
> In their paper, "On asynchrony in name-passing calculi ", Merro and
> Sangiorgi mention that the motivation for imposing locality and
> dropping name matching capability in Lpi comes from language design
> issues and compiler optimization considerations. Can anybody point
> to or give some concrete examples that illustrate these aspects. For
> example, what are some interesting compiler optimizations that would
> not hold in the absence of locality or in the presence of name
> matching capability.

i don't know about compiler optimisations, but locality is quite natural
if you think about distributed systems. in my phd thesis, i investigated
some pi-based models of distributed systems  and gave this justification
for locality. maybe its useful:

   To understand locality, think about your machine. It is probably
   connected to some Ethernet based LAN, which is in turn connected to
   the Internet. This means that your computer will have one or more IP
   addresses to identify its points of interaction with other
   computers. What is peculiar about IP addresses is that they are
   fixed. They cannot be changed (easily). In particular, you
   cannot make one of your IP addresses dependent on data that has just
   come in from the Internet.

   Of course things are more complicated than this. One can always change
   IP addresses of a machine, but that would in itself not be very
   useful, unless the entire Internet was notified about the address
   change. Otherwise routing tables would not contain up-to-date
   information that would allow to route messages properly. This is a
   time consuming process, taking several hours if not longer. As a
   matter of fact, things are even more complicated because some address
   changes can be carried out locally, for example from 236.72.1.61 to
   236.72.1.62, provided both addresses already live in the same
   broadcast LAN and 236.72.1.62 is not already used. Since all
   messages going to 236.72.1.62 will be broadcast, either by the
   gateway router or by some other machine on the LAN, delivery to the
   new address is no problem. But what certainly does not work is to
   assign an arbitrary IP address to a computer and expect that
   instantly messages from anywhere on the net are delivered.  It
   is possibly rather crude, but nevertheless illuminating to model this
   behaviour as pi-calculus-processes, taking names to stand for IP addresses:
   this boils down to prohibiting input subject to be input bound. This
   means not allowing processes like $\IN{x}{v}.\IN{v}{w}$, because the
   input subject $v$ is bound by $\IN{x}{v}$. \PIcs\ where input subjects
   are never bound by inputs are called local. It is easy to
   define typing systems such that typability guarantees locality.

in short: input locality is simple, yet appropriate requirement for
modelling contemporary distributed systems.

martin (http://www.dcs.qmul.ac.uk/~martinb)

 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The "models for mobility" mailing list     mailto:moca@xxxxxxxxxxxxxxx
http://www-sop.inria.fr/mimosa/personnel/Davide.Sangiorgi/moca.html