#Number
TR-PDS-1995-015

#Title
Reaching Agreement Optimistically in a Faulty Asynchronous System

#Author
J. Roger Mitchell and Vijay K. Garg

#Abstract
Agreement among processes in a faulty distributed system is useful for
the solution to leader election, atomic broadcast, and commit
protocols, among others.  We present a method for solving consensus
using optimism.  Our approach is optimistic in that processes do not wait
on other processes.  Instead they assume all proposals have been
received and continue execution.  Only if this assumption is later
proved wrong, are actions based on these tentative decisions required
to roll back.  With this approach, all processes can decide the same
value in a completely asynchronous distributed system  
that has process, message, or channel failures, and thus can become
partitioned.  Since no protocol can commit in a distributed system
with these characteristics (by the impossibility result), we discuss
methods for using optimistic agreement with other commitment algorithms.
When employed this way, the approach provides benefits of continued
execution in a partition, optimistic execution during commit, and a
loose failure model for the asynchronous agreement group.

#Bib
@TechReport{SC95,
  author = "J. Roger Mitchell and Vijay K. Garg"
  title = "Reaching Agreement Optimistically in a Faulty Asynchronous System",
  institution =  "Parallel and Distributed Systems Laboratory, ECE
                  Dept. University of Texas at Austin",
  year =         "1995",
  number =    "TR-PDS-1995-015",
  note =      "available via ftp or WWW at maple.ece.utexas.edu
                  as technical report TR-PDS-1995-015",
}