Mariage stable auto-stabilisant et distribué
Time: 14:30 -- Location: LRI, 445
Summary: 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à, nous présenterons notre solution : le premier algorithme distribué auto-stabilisant et asynchrone pour ce problème ainsi que quelques adaptations à diverses variantes.