Optimistic Algorithms for Partial Database Replication

In this paper, we study the problem of partial database replication. Numerous previous works have investigated database replication, however, most of them focus on full replication. We are here interested in genuine partial replication protocols, which require replicas to permanently store only information about data items they replicate. We define two properties to characterize partial replication. The first one, Quasi-Genuine Partial Replication, captures the above idea; the second one, Non-Trivial Certification, rules out solutions that would abort transactions unnecessarily in an attempt to ensure the first property. We also present two algorithms that extend the Database State Machine to partial replication and guarantee the two aforementioned properties. Our algorithms compare favorably to existing solutions both in terms of number of messages and communication steps.

Published in:
Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS'2006), 81-93
Presented at:
10th International Conference on Principles of Distributed Systems (OPODIS'2006), Bordeaux, France, December 2006
Also published as a Brief Announcement in the Proceedings of the 20th International Symposium on Distributed Computing (DISC'2006)

 Record created 2006-12-20, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)