Accueil > Manifestations > Thèses et HDR > Thèses > Matthieu Perrin

Matthieu Perrin

Directeur de thèse

Claude Jard
Achour Mostefaoui

Résumé

Dans les systèmes répartis à très large échelle, les critères de cohérence forts comme la cohérence séquentielle et la linéarisabilité sont souvent trop coûteux, voire impossibles à obtenir. Dans cette thèse, nous nous posons la question de la spécification des objets que l’on peut tout de même obtenir. Nous soutenons qu’il est toujours possible de séparer leur spécification en deux facettes : un type de données abstrait qui spécifie l’aspect fonctionnel des opérations et un critère de cohérence faible qui décrit la qualité de service garantie par l’objet dans son environnement réparti. Nous illustrons ces concepts par une mise en œuvre dans le
langage D : les types de données abstraits sont les classes du programme et les critères de cohérence sont choisis dans une liste fournie par la
bibliothèque CODS.
Nous dressons une carte de l’espace des critères faibles organisée autour de trois familles de critères primaires (localité d’état, convergence et validité) et trois familles de critères secondaires (cohérence d’écritures, cohérence pipeline et sérialisabilité). Chaque critère secondaire renforce deux critères primaires, mais les trois critères
primaires ne peuvent pas être implémentés ensembles dans les systèmes
considérés. Nous étudions également l’effet de la causalité sur ces familles.

Mots-clés :

CODS, Cohérence causale, Cohérence d’écritures, Cohérence faible, Cohérence pipeline, Cohérence séquentielle, Convergence, Critère de cohérence, Localité d’états, Orc, Sémantique opérationnelle structurelle, Sérialisabilité, Systèmes sans-attente, Type de données abstrait, Validité.

Abstract :

In large scale distributed systems, strong consistency criteria like sequential consistency and linearizability are often very expensive or even unachievable. This thesis investigates the best ways to specify the objects that are still possible to implement in these systems. We assert that it is still possible to separate their specification in two complementary facets : an abstract data type that specifies the functional aspect of the operations and a weak consistency criterion that describes
the level of quality of service ensured by the object in its distributed environment. We illustrate these concepts by an implementation in the D programming language : abstract data types are described by classes in the program and consistency criteria are taken from a list in the CODS library.

We also draw up a map of the space of weak consistency criteria, organised around three families of primary criteria (state locality, eventual consistency and validity) and three families of secondary criteria (update consistency, pipelined consistency and serializability). Each secondary criterion strenghtens two primary criteria, but the three criteria can not be implemented together in considered systems. We also study the effects of causality on these families.

Key words :

Abstract data types, Causal consistency, CODS, Consistency criterion, Eventual consistency, Orc, Pipeline consistency, Sequential consistency, Update consistency, Serializability, State locality, Structural operational semantics, Validity, Wait-free systems, Weak consistency

Composition du jury :

  • M. Luc BOUGÉ, Professeur, École Normale Supérieure de Rennes, Rapporteur
  • Mme. Maria POTOP-BUTUCARU, Professeur, Université Pierre et Marie Curie,
    Paris, Rapporteur
  • Mme. Alessia MILANI, Maître de conférences, ENSEIRB-MATMECA, Bordeaux, Examinateur
  • M. Jean-Marc MENAUD , Professeur, École des Mines de Nantes, Examinateur
  • M. Claude JARD, Professeur, Université de Nantes, Directeur de thèse
  • M. Achour MOSTÉFAOUI, Professeur, Université de Nantes, Co-encadrant

Dernière modification : dimanche 5 juin 2016