INDEPENDENT UPDATES AND INCREMENTAL AGREEMENT IN REPLICATED DATABASES

Update propagation and transaction atomicity are major obstacles to th e development of replicated databases. Many practical applications, su ch as automated teller machine networks, flight reservation, and part inventory control, do not require these properties. In this paper we p resent an approach for incrementally updating a distributed, replicate d database without requiring multi-site atomic commit protocols. We pr ove that the mechanism is correct, as it asymptotically performs all t he updates on all the copies. Our approach has two important character istics: it is progressive, and non-blocking. Progressive means that th e transaction's coordinator always commits, possibly together with a g roup of other sites. The update is later propagated asynchronously to the remaining sites. Non-blocking means that each site can take unilat eral decisions at each step of the algorithm. Sites which cannot commi t updates are brought to the same final state by means of a reconcilia tion mechanism. This mechanism uses the history logs, which are stored locally at each site, to bring sites to agreement. It requires a smal l auxiliary data structure, called reception vector, to keep track of the time unto which the other sites are guaranteed to be up-to-date. S everal optimizations to the basic mechanism are also discussed.