#Number
TR-PDS-1997-003

#Title
Group message logging without orphans for fast output commit

#Author
J. Roger Mitchell
Vijay K. Garg

#Abstract
In current recovery algorithms, the problem of output commit is often
not specifically addressed.  Those schemes that do, incur high latency
before the output message can be sent from the system.  This latency
typically involves synchronous writes to stable storage.  In this
paper we present a method of grouping processes which allows output
commit to occur after a process has received acknowledgements from
other processes.  We keep the number of acknowledgements small by
creating groups of processes within the system, each group $i$ 
tolerates $k_i$ simultaneous failures.  Our experiments show that when
$k_i=2$ or $3$, our algorithm performs output commit over three times
faster than simply writing information to stable storage.  Our
algorithm is based on the family-based message logging approach, but
our approach allows for $k_i$ simultaneous failures in each group,
rather than just $k$ across the entire system.  Our implementation of
family-based logging also never blocks live processes and allows for
parallel recovery during simultaneous failures, something that previous
work has not accomplished.  We introduce the idea of a recovery reply
cut to do this.
	
#Bib
@InProceedings{,
  author = 	 "J. Roger Mitchell and Vijay K. Garg",
  title = 	 "Group message logging without orphans for fast output 
		commit",  
  booktitle =	 "",
  address =	 "",
  month =	 "March",
  note =	 1997,
  note =	 "available via ftp or WWW at maple.ece.utexas.edu
		  as technical report TR-PDS-1997-003"
}