Report Number: CS-TR-92-1446
Institution: Stanford University, Department of Computer Science
Title: Independent updates and incremental agreement in replicated databases
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 discussed.
http://i.stanford.edu/pub/cstr/reports/cs/tr/92/1446/CS-TR-92-1446.pdf