Distributed data structures and consistency criteria

Les systèmes distribués sont divers mais peuvent être classés en deux classes principales, ceux à communication par messages et ceux à mémoire partagée. Depuis qu'il a été montré par Attiya et al. que les deux modèles sont équivalents et que l'on peut émuler l'un au dessus de l'autre, une littérature abondante a été produite sur l'émulation de différentes structures de données partagées. Un point important concerne la cohérence garantie par une implémentation d'un objet donné. Un nombre important de critères de cohérence a été proposé par différentes communautés (atomicité, PRAM, cohérence causale, cohérence cache, cohérence à terme, etc.). Le critère le plus intuitif étant la linéarisabilité. Une implémentation linéarisable se comporte exactement comme si l'objet était physiquement unique et accédé en concurrence. Ce critère étant coûteux à mettre en oeuvre, des critères plus faibles. L'un deux la cohérence séquentielle en est la plus proche. Elle offre les mêmes garanties que la linéarisabilité à un coût théoriquement plus faible. Cependant, ce critère n'est pas composable. Dans la présentation présente, on propose une mise en oeuvre d'une mémoire partagée séquentiellement cohérente beaucoup moins coûteuse qu'une mémoire linéarisable et on donne deux contextes d'utilisation très couramment rencontrés où la cohérence séquentielle est composable.