-------------------------------------------------------------------------------
                                       
                                       
		       B O S T O N   U N I V E R S I T Y
				       
			  Computer Science Department
				       
			      C O L L O Q U I U M
				       
			   Wednesday April 13, 1994
				       
				    3:00pm
			   (Coffee served at 2:30pm)
				       
			    Seminar Room / MCS 135
                                       

-------------------------------------------------------------------------------


			      ATOMIC TRANSACTIONS

      A Language Primitive for Programming Concurrent/Distributed Systems


				  Nancy Lynch

				      MIT



    The {\em atomic transaction}  programming abstraction originated in the
    setting  of   concurrent database   processing, and   has proved  to be
    successful  in the more  general  setting of data-oriented  distributed
    computing.  This  notion allows the  programmer to specify  a series of
    elementary  data-processing actions that are to  be performed ``as if''
    atomically.  The series of actions   should be executed {\em either  in
    its entirety  or  not at all},  and  the originator  of the transaction
    should  be informed as to which  of these two  has occurred.  Moreover,
    the transaction  should appear as if  all of its  actions occurred at a
    single moment, {\em  without any interruption from other transactions}.
    This transaction  semantics should hold in  spite of the usual sorts of
    failures  that  occur in concurrent  and distributed  systems,  such as
    stopped processors and communication links.   A useful extension of the
    basic notion is to allow transactions to be {\em nested}, that is, each
    transaction can have subtransactions that are themselves to be executed
    atomically with respect to each other.

    The notion  of transaction is easy to  use for distributed programming,
    because it permits the programmer to  pretend that his/her programs are
    being executed on a sequential processor.  On the other hand, the costs
    of providing such a   clean user interface,  in  terms of latency   and
    amount of communication, can be high.  These costs can often be reduced
    by   careful consideration  of  exactly  which operations    need to be
    performed atomically, and by appropriate definition of the types of the
    data objects.  Also, clever optimizations  are often carried out to fit
    algorithms to particular system architectures.

    The correctness conditions   for nested transactions   are sufficiently
    subtle, and the  implementing algorithms sufficiently complex, that  it
    is  very difficult   to reason about   them  using the usual   informal
    methods.   In this talk,  the  atomic transaction concept is  described
    informally, and  a formal framework for  describing and reasoning about
    them is  presented.  It is  then shown  how  this framework is  used to
    specify   the  correctness  conditions   that   nested transactions are
    supposed to   satisfy, to    describe a  wide   range  of  implementing
    algorithms, and to  give   rigorous proofs  that those algorithms   are
    correct.

    This work is summarized here from the new book ``Atomic Transactions'',
    by Lynch, Merritt, Weihl and Fekete.

    Host: Azer Bestavros

-------------------------------------------------------------------------------
    For more information contact Prof. Azer Bestavros <bestavros@cs.bu.edu>
-------------------------------------------------------------------------------