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.