[moca] Re: Re: RE: RE : synchronous implementation of Pi calculus with choice?

[Pawel.Wojciechowski@xxxxxxx]

> >  The theoretical impossibility results, such as the impossibility of 
> >  solving consensus in an asynchronous system when processes can crash
> >  (Fisher-Lynch-Paterson'85) can be overcome by strengthening the system 
> >  model a bit, e.g. using failure detectors (Chandra-Toueg'95).
> 
> Not really, the impossibility result is just moved from inside the
> model to outside, ie the impossibility of implementing the algorithm
> is replaced by the impossibility of implementing the detectors, except

This is in fact what I meant in my sentence: failure detector (FD) is 
a nice abstraction that can be used to "strengthen the system model" 
in order to avoid the "theoretical impossibility result". The model
with FD is, however, still a model (and, of course, not all classes 
of FDs can be implemented in a real world).

> again on a LAN or on a limited number of nodes in a WAN.

I did not claim that it would be possible to have a very large 
number of nodes (or processes in a group), just said that there 
is no reason why the group communication system should be meant 
to be used only in a LAN.

> >  network will not make the system unusable. It is just that processes
> >  would be more often suspected to have failed and exluded from the current 
> >  group view (they should then rejoin under a new name). Those processes
> >  that are within a current group view can deliver broadcast messages 
> >  undisturbed.
> 
> Group communication systems are useful for some problems, not for all
> problems.  If you are working on peer-to-peer systems with 300 000

correct

Traditionally, group communication has been proposed for building 
fault-tolerant applications in distributed systems. Applications
are made tolerant to crashes by replicating critical processes.

In this context, the group communication system manages the interaction
between the process replicas across the network. I would assume 
that there is no more replicas necessary than a few (but at least 3);
a few is still much less than 300 000..

> nodes, you can hardly build a group or something like that. 

The peer-to-peer application probably does not require to maintain
strong consistency between replicas for all the time, so I would use 
so called "epidemic" or "gossip-based" algorithms instead of those 
based on consensus. 

Look also at work by Robert van Renesse (co-designer of the Ensemble 
group communcation system at Cornell) et al. on the Spinglass project:

	http://www.cs.cornell.edu/Info/Projects/Spinglass/

They claim that they can already support thousands of nodes (and 
hope to be able to support a hundred of thousands nodes).

> Fortunately, in such systems, the tolerance to failure is often
> very simple, and you don't have to use a very powerful mechanisms to
> cope with them, and to ensure the safety properties of your program. 

of course

Pawel


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