Le chemin vers une cohérence disponible

Campus de Beaulieu Salle i-51 - bât. 12D

Intervention de Marc Shapiro directeur de recherche émérite INRIA, dans l'équipe Delys, dans le laboratoire LIP6 situé à Sorbonne Université, dans le cadre des séminaires du département Informatique.

/medias/photo/seminaire-di_1630676501273-jpg

Cet exposé concerne la tension entre correction et disponibilité dans un système réparti.

Un programme séquentiel est sûr si chaque transition maintient un invariant spécifique.  Cependant, pour assurer l’efficacité et la disponibilité malgré les ruptures du réseau, un programme réparti est concurrent et asynchrone ; cela perturbe la sûreté séquentielle, laissant se produire des anomalies.

Certains types d’anomalies se résolvent sans diminuer la disponibilité.  Ainsi, l’anomalie de convergence se résout grâce aux types de données répliquées sans conflit (Conflict-free Replicated Data Types CRDT) ; l’anomalie de

séparation grâce aux transactions atomiques ; l’anomalie d’ordre grâce à la cohérence causale.  Les mécanismes correspondants sont locaux, sans impact sur la concurrence et l’asynchronisme, et donc sur la disponibilité lors d’une rupture réseau.

Par contre, pour éviter l’anomalie de la précondition instable (celle visée par the théorème CAP) il faut un consensus distribué sur l’ordre des mises à jour.  Notre analyse CISE permet de déduire l’ensemble minimal d’opérations qui doivent se coordonner afin d’assurer la sûreté.  In fine, c’est au développeur de faire le choix entre invariant fort et disponibilité.

Thématique(s)

Formation, Recherche - Valorisation

Contact

Killian Barrere