From: Ozalp Babaoglu <ozalp@cs.unibo.it>
Subject: University of Bologna LCS Technical Report Series
Originator: golding@frans.cs.vu.nl
Organization: Laboratory for Computer Science, University of Bologna, Italy
Date: Fri, 22 Jan 1993 18:29:49 GMT

University of Bologna Laboratory for Computer Science (UBLCS) has set
up an anonymous FTP server for the distribution of its Technical
Report Series.  The following reports are now available:

--
Title:  	Consistent Global States of Distributed Systems:
			Fundamental Concepts and Mechanisms
Authors: 	Ozalp Babaoglu and Keith Marzullo
Date: 		January 1993
Report: 	UBLCS-93-1
Length: 	40 pages
Availability: 	anonymous FTP from ftp.cs.unibo.it
Directory: 	/pub/TR/UBLCS
File:		global-states.ps.Z

Abstract:
Many important problems in distributed computing admit solutions that
contain a phase where some global property needs to be detected.  This
subproblem can be seen as an instance of the Global Predicate
Evaluation (GPE) problem where the objective is to establish the truth
of a Boolean expression whose variables may refer to the global system
state.  Given the uncertainties in asynchronous distributed systems
that arise from communication delays and relative speeds of
computations, the formulation and solution of GPE reveal most of the
subtleties in global reasoning with imperfect information.  In this
paper, we use GPE as a canonical problem in order to survey concepts
and mechanisms that are useful in understanding global states of
distributed computations.  We illustrate the utility of the developed
techniques by examining distributed deadlock detection and distributed
debugging as two instances of GPE.


--
Title:  	Understanding Non-Blocking Atomic Commitment
Authors: 	Ozalp Babaoglu and Sam Toueg
Date: 		January 1993
Report: 	UBLCS-93-2
Length: 	31 pages
Availability: 	anonymous FTP from ftp.cs.unibo.it
Directory: 	/pub/TR/UBLCS
File:		atomic-commitment.ps.Z

Abstract:
In distributed database systems, an atomic commitment protocol ensures
that transactions terminate consistently at all participating sites
even in the presence of failures.  An atomic commitment protocol is
said to be non-blocking if it permits transaction termination to
proceed at correct participants despite failures of others.  Protocols
that have this property are desirable since they limit the time
intervals during which transactions may be holding valuable resources.
In this paper, we show how non-blocking atomic commitment protocols
can be obtained through slight modifications of the well-known
Two-Phase Commit (2PC) protocol, which is known to be blocking.  Our
approach is modular in the sense that both the protocols and their
proofs of correctness are obtained by plugging in the appropriate
reliable broadcast algorithms as the basic communication primitives in
the original 2PC protocol.  The resulting protocols are not only
conceptually simple, they are also efficient in terms of time and
message complexity.


-- 
Ozalp Babaoglu					E-mail:	ozalp@cs.unibo.it
University of Bologna, Dept. of Mathematics
Piazza di Porta S. Donato, 5			TEL:	+39 51 354430
40127 Bologna  (ITALY)				FAX:	+39 51 354490
===========================================================================
Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
	    compdoc-techreports-request@ftp.cse.ucsc.edu