#Number
TR-PDS-1995-002

#Title
Dissecting Distributed Coordination in Asynchronous Systems

#Author
Aleta Ricciardi

#Abstract

This paper derives necessary and sufficient communication for distributed
applications that perform certain actions uniformly (if by any process,
then by every process) in asynchronous systems.  We show there is an
essential structure of information flow in any solution to Uniform
Coordination, thereby suggesting message-minimal solutions.  We show that
in the absence of an external membership service, it is necessary for
processes to conspire against each other to make progress around the
impossibility result in Fischer, et.al. [1985], and we show this conspiracy
requires processes to stop communicating with each other.

We also propose that the impossibility arises more as a matter of
specification than necessity.  We view the requirement that all correct
processes take the same action as a simple way of exempting crashed
processes from having to act.  In this light, we show that the primary
partition model is an outgrowth of a very strong exemption, needed to make
an execution in which a process does not crash indistinguishable from one
in which it does.  The ability to define weaker exemptions for distributed
coordination problems gives rise to many problems solvable in asynchronous
systems as well as in systems that partition.  For toolkits that permit
execution during partitions, and for computations over networks especially
prone to partitioning, knowing which actions can be safely taken across a 
partition is crucial.

	
#Bib
@InProceedings{,
  author = 	 "Aleta Ricciardi",
  title = 	 "Dissecting Distributed Coordination",
  booktitle =	 "Submitted to PODC95",
  address =	 "  ",
  month =	 "February",
  note =	 1995,
  note =	 "available via ftp or WWW at maple.ece.utexas.edu
		  as technical report TR-PDS-1995-002"
}