Séminaire REGAL
Presque tous les objets atomiques implémentés dans des systèmes asynchrones avec transmission de messages sont universels : la hiérarchie de Herlihy devient (presque) plate
Thursday, March 8, 2007C. Delporte (LIAFA), H. Fauconnier(LIAFA), R. Guerraoui(EPFL).
Dans une implémentation wait-free, chaque processus peut terminer le protocole sans l'aide des autres processus. De cette façon, une implémentation wait-free peut tolérer un nombre quelconque de pannes crash.
Dans un système asynchrone a mémoire partagée, un objet consensus est universel dans le sens ou il permet d'implémenter de façon wait-free tout objet (tel que compare_and_swap test_and_set). D'autre part, on peut montrer qu'un objet qui permet de résoudre le consensus parmi k processus est strictement plus faible qu'un objet permettant de résoudre le consensus parmi k' processus avec k' inférieur à k. De cette façon on peut définir une hiérarchie entre les objets: pour un objet o, h(o) est le nombre maximal de processus pour lesquels le consensus peut être implémenter avec l'aide de o. On peut alors montrer que le test_and_set est strictement plus faible que le compare_and_swap Mais qu'arrive-t-il si au lieu de considérer un système asynchrone à mémoire partagée on considère un système asynchrone où les processus communiquent par échange de messages enrichi de détecteurs de défaillances?