PhD graduated
Team : REGAL
Departure date : 03/31/2015

Supervision : Marc SHAPIRO

Dependable Eventual Consistency with Replicated Data Types

Eventually consistent replicated databases offer excellent responsiveness and fault-tolerance, but expose applications to the complexity of concurrency and failures. Recent databases encapsulate these problems behind a stronger interface, supporting causal consistency, which protects the application from ordering anomalies, and/or Replicated Data Types (RDTs), which ensure convergent semantics of concurrent updates using object interface. However, dependable algorithms for RDT and causal consistency come at a cost in metadata size. This thesis studies the design of such algorithms with minimized metadata, and the limits of the design space.
Our first contribution is a study of metadata complexity of RDTs. RDTs use metadata to provide rich semantics; many existing RDT implementations incur high overhead in storage space. We design optimized set and register RDTs with metadata overhead reduced to the number of replicas. We also demonstrate metadata lower bounds for six RDTs, thereby proving optimality of four implementations.
Our second contribution is the design of SwiftCloud, a replicated causally-consistent RDT object database for client-side applications. We devise algorithms to support high numbers of client-side partial replicas backed by the cloud, in a fault-tolerant manner, with small metadata. We demonstrate how to support availability and consistency, at the expense of some slight data staleness; i.e., our approach trades freshness for scalability (small metadata, parallelism), and availability (ability to fail-over between data centers). We validate our approach with experiments involving thousands of client replicas.

Defence : 01/14/2015

Jury members :

M. Pascal MOLLI, Université de Nantes [Rapporteur]
M. Luis RODRIGUES, INESC-ID Université de Lisbonne [Rapporteur]
M. Carlos Baquero, HASLab, INESC TEC & University of Minho
M. Jerzy Brzeziński, Poznań University of Technology
M. Sebastian Burckhardt, Microsoft Research, Redmond
M. Peter Dickman, Google, Zürich
M. Pierre Sens, LIP6
M. Marc Shapiro, LIP6 [Directeur de thèse]

Departure date : 03/31/2015

2011-2016 Publications

Mentions légales
Site map