Supporting Linearizable Semantics in Replicated Databases.

L. Rodrigues, N. Carvalho, and E. Miedes.

Selected sections of this report will be published in the Proceedings of the 7th IEEE International Symposium on Network Computing and Applications (IEEE NCA08), Cambridge, MA, USA, July 2008. (short paper)


This paper proposes a novel database replication algorithm that offers strong consistency (linearizable semantics) and allows reads and non-conflicting writes to execute in parallel in multiple replicas. The proposed algorithm supports the use of quorums to trade the availability/efficiency of read and write operations, making a bridge between consensus-based and quorum based solutions for database replication. Furthermore, the algorithm offers better performance for linearizable read-only transactions with a negligible impact on write transactions.

Also available extended report (pdf).

Luís Rodrigues