#Number
TR-PDS-1997-002

#Title
Optimistic agreement in asynchronous distributed systems

#Author
J. Roger Mitchell
Vijay K. Garg

#Abstract
Coordination among a group of processes is often performed
in distributed systems.  When failures can occur, this agreement on
coordination becomes more difficult.  Often, the agreement can take
several rounds of message exchanges among the group.  When a failure
occurs, the latency increases, for example in a system where the group
waits for a member to recover.  In this paper we present a method for
reducing the latency in these situations using optimism.  We present a
method for general agreement problems in which the agreement type is
specified using two functions.  We demonstrate how to do this for the
problems of binary agreement, approximate agreement, and leader
election.  We give experimental results that show that this approach
allows processes to perform useful work when they otherwise would have
waited.  For example, our implementation of approximate agreement
allows processes to perform useful work for more than 80\% of the
period they would have otherwise waited (from 5 to 11 rounds).
	
#Bib
@InProceedings{,
  author = 	 "J. Roger Mitchell and Vijay K. Garg",
  title = 	 "Optimistic agreement in asynchronous distributed systems",
  institution =	 "University of Texas at Austin",
  month =	 "February",
  note =	 1997,
  note =	 "available via ftp or WWW at maple.ece.utexas.edu
		  as technical report TR-PDS-1997-002"
}