Titre : Wait-Free, Obstruction-Free
Encadrants : C. Delporte, H. Fauconnier
Contact : cd@liafa.jussieu.fr, hf@liafa.jussieu.fr
Lieu : LIAFA-Université Paris 7, 173 rue du Chevaleret 75013 PARIS.
Un objet atomique partagé [1] (registres atomiques, test-and-swap, compare-and-swap, Load-Locked/Store-Conditional, consensus… ) est une structure de données partagée avec une spécification séquentielle définissant les propriétés de son invocation. On considère ici des implémentations d’objets partagés dans des systèmes asynchrones (ou partiellement synchrones). Toutes ces implémentations assurent les propriétés de safety mais n’assurent pas toujours la liveness.
Une implémentation est Wait-Free si elle assure toujours la terminaison des invocations même sans la coopération des autres processus. Cela signifie en particulier que cette implémentation tolère un nombre quelconque de défaillances et que, dans une implémentation wait-free, un processus peut toujours terminer seul son invocation. Le résultat d’impossibilité du consensus en asynchrone prouve qu’il n’existe pas d’implémentation wait-free pour tout objet qui permettrait de réaliser le consensus. Un résultat de [1] montre que le consensus est universel pour l’implémentation wait-free des objets atomiques : avec des objets consensus et des registres atomiques on peut implémenter de façon wait-free n’importe quel objet atomique.
Comme une implémentation wait-free est difficile à réaliser on peut restreindre les propriétés de liveness en considérant des implémentations Lock-Free : une telle implémentation assure toujours la progression d’au moins un processus dans le système, mais ne garantit pas nécessairement la terminaison de toutes les invocations. Plus récemment une autre notion a été proposée : une implémentation Obstruction-Free [2] assure la terminaison si le processus qui fait l’invocation s’exécute en isolation. Un résultat intéressant [3] montre que sous certaines conditions de synchronisme on peut transformer une implémentation obstruction-free en implémentation wait-free. Contrairement aux implémentations wait-free il semble toujours possible d’implémenter un objet atomique de façon obstruction-free et ainsi avec le résultat de [2] on obtient une autre façon de réaliser des implémentations Wait-Free d’objets atomiques
Le but de ce stage est d’étudier dans quelle mesure la notion d’obstruction-free peut simplifier l’approche wait-free et dans quelle mesure on peut déterminer des conditions de synchronie permettant le passage d’obstruction-free à wait-free.
[1] M.P.
Herlihy. Wait-free
synchronization. ACM Transactions on Programming Languages and Systems,
13(1):124--149, January 1991.
[2] M.P. Herlihy, V. Luchangco, and M.
Moir. Obstruction-free
Synchronization: Double-ended Queues as an Example. Proceedings of the
23rd IEEE International Conference on Distributed Computing Systems (ICDCS),
[3] Faith
Ellen Fich,