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

[Pawel.Wojciechowski@xxxxxxx]

> > Are all these asynchronous implementations sacrificing descriptive
> > power for ease of implementation or is the full semantics
> > unnecessary ?
> 
> Ease of implementation ? Distributed Consensus has been proved to be
> *impossible* to satisfy (FLP85) in an asynchronous(without limits)

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).

> system with simple crash failures. Of course, you can implement it
> with timing assumptions, but then, your system will only be useful in
> LANs under light pressure.

The first group communication systems, such as ISIS (Cornell), which can 
be used to solve an agreement problem within a dynamic group of 
distributed processes, were indeed useful only in a LAN. However, 
some other systems have been designed that can be efficiently employed 
also in a larger network (see also Luis Rodrigues's work). 

More about different exisiting implementations and their limitations
can be found in a recent tech report "A Step Towards a New Generation 
of Group Communication Systems", available at:

	http://lsrwww.epfl.ch/Research/Crystall

BTW, some implementations of the group communication systems use directly
different "consensus" algorithms, e.g. Chandra-Toueg's algorithm with 
a rotating coordinator. They use imperfect failure detectors that can,
of course, make mistakes. However, this is not a problem as long as
the number of suspected processes is less than a half of correct processes.

The long communication delays which are likely to happen in a wide-area 
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.

Best regards,
Pawel Wojciechowski






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