Report Number: CS-TR-92-1446
Institution: Stanford University, Department of Computer Science
Title: Independent updates and incremental agreement in replicated
Author: Ceri, Stefano
Author: Houtsma, Maurice A. W.
Author: Keller, Arthur M.
Author: Samarati, Pierangela
Date: October 1992
Abstract: Update propagation and transaction atomicity are major
obstacles to the development of replicated databases. Many
practical applications, such as automated teller machine
(ATM) networks, flight reservation, and part inventory
control, do not really require these properties. In this
paper we present an approach for incrementally updating a
distributed, replicated database without requiring multi-site
atomic commit protocols. We prove that the mechanism is
correct, as it asymptotically performs all the updates on all
the copies. Our approach has two important characteristics:
it is progressive, and non-blocking. Progressive means that
the transaction's coordinator always commits, possibly
together with a group of other sites. The update is later
propagated asynchronously to the remaining sites.
Non-blocking means that each site can take unilateral
decisions at each step of the algorithm. Sites which cannot
commit updates are brought to the same final state by means
of a reconciliation mechanism. This mechanism uses the
history logs, which are stored locally at each site, to bring
sites to agreement. It requires a small auxiliary data
structure, called reception vector, to keep track of the time
until which the other sites are guaranteed to be up-to-date.
Several optimizations to the basic mechanism are also