Master 2013 2014
Stages de la spécialité SAR
Exploring the design space of transactional consistency models

Site :Equipe Regal
Lieu :LIP6, Université Pierre et Marie Curie, site Jussieu
Encadrant : Masoud Saeida Ardekani & Marc Shapiro
Dates :du 31/03/2014 au 31/08/2014
Rémunération :oui


In distributed systems and databases, there is a fundamental trade-off between the performance and the guarantees offered by a consistency model. The strongest consistency model (strict serializability) offers the guarantees of a highly fault-tolerant sequential system, and is therefore very easy to understand and use, but performs poorly. Performance can be improved, often by orders of magnitude, by weakening the consistency guarantees ; in the extreme, Eventual Consistency (EC) ensures minimal latency and maximal performance, but is extremely challenging to program against.

Practical database systems cover the whole spectrum of intermediate consistency models. For instance, Oracle and other database engines famously do not implement serializability for performance reasons, but only the weaker Snapshot Isolation (SI). As SI itself has inherent bottlenecks, several alternatives have been proposed that weaken the guarantees somewhat still disallowing update conflicts [2,3]. In distributed settings, NoSQL databases such as Riak or Cassandra [1] are highly scalable, at the cost of guarantees no stronger than EC.

Despite the plethora of models, both in research and in practical systems, the differences are poorly understood. How does an application developer navigate this space ? How can he tell what is the right model for his problem ?

The proposed research aims for a systematic and exhaustive exploration of the design space of transactional consistency models, in order to characterise the advantages and limitations of each one.

Many distributed transactional protocols have a common structure, called Deferred Update Replication (DUR). We have shown that protocols of this family differ only in the specific behavior of a few generic functions. We have implemented a generic DUR framework, called Jessy, along with a library of finely-optimized plug-in implementations of the required behaviors. By mixing and matching the appropriate plug-ins, the framework can be customized to provide a high-performance implementation of diverse transactional protocols, which in turn enables a fair, apples-to-apples comparison between them.

The research consists of implementing a number of consistency models of interest by an appropriate selection of plug-ins (and implementing any missing plug-ins). Each such combination will be studied in detail, both analytically and experimentally, in order to characterise precisely its performance and guarantees, its bottlenecks, and the class of applications that it supports (or not). Exploring plugin combinations might generate new consistency models with unexpected properties.

The research will take place at Université Pierre et Marie Curie (UPMC-Paris 6), Laboratoire d’Informatique de Paris 6 (LIP6), in the Latin Quarter in the centre of Paris.

Requirements : - Enrolled in a Master’s in Computer Science / Informatics or a related field. - Excellent academic record. - Motivated by experimental research. - Skills in algorithms, data structures, concurrency, distributed computing, high-performance computing, operating systems, distributed systems, databases, or a related area.

Please provide a CV, a list of courses and your marks, an essay relevant to the topic (1 to 4 pages), and at least two references (whom we will contact ourselves for a recommendation).

Contact : Marc Shapiro or Masoud Saeida Ardekani


Further information

The research will take place at Université Pierre et Marie Curie (UPMC-Paris 6), Laboratoire d’Informatique de Paris 6 (LIP6), in the Latin Quarter in the centre of Paris.