DELYS
Mariage stable auto-stabilisant et distribué
Quinta-feira, 28 de março de 2019Marie LAVEAU
Le problème du mariage stable (Stable Marriage problem, SMP) est un problème classique proposé pour la première fois par Gale et Shapley. Issu de l'économie, le SMP a aussi été étudié intensivement en maths et en informatique et a de multiples dérivés et applications (Cloud-computing, programme d'admission des hôpitaux, etc). Ce problème considère classiquement deux ensembles d'agents appelés hommes et femmes. Chaque agent a des préférences par rapport aux membres de l'autre ensemble. L'objectif est de former un appariement M entre ces hommes et ces femmes qui soit stable, i.e., qui soit sans paire dont les membres, non associés, se préfèrent mutuellement par rapport à leur partenaire dans M. Dans ce cadre là, le premier algorithme distribué auto-stabilisant et asynchrone pour ce problème sera présenté, ainsi que quelques adaptations à diverses variantes.
laurent.feuilloley (at) nulllip6.fr