Technical report detail

Optimistic Algorithms for Partial Database Replication

by Schiper, Nicolas and Schmidt, Rodrigo and Pedone, Fernando

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.

Technical report 2006/02, August 2006

BibTex entry

@techreport{06optimistic, author = {Schiper, Nicolas and Schmidt, Rodrigo and Pedone, Fernando}, title = {Optimistic Algorithms for Partial Database Replication}, institution = {University of Lugano}, number = {2006/02}, year = 2006, month = aug }