Equipe : Systèmes Parallèles
Mariage Stable Asynchrone et Auto-stabilisant
Début le 01/10/2015
Direction : BEAUQUIER, Joffroy
Ecole doctorale : ED STIC 580
Etablissement d'inscription : vide
Lieu de déroulement : LRI, salle des thèses
Soutenue le 30/09/2020 devant le jury composé de :
- Johanne Cohen, Présidente du Jury
Directrice de Recherche, Université Paris-Saclay (LRI)
- Colette Johnen, Rapporteure & Examinatrice
Professeure, Université Bordeaux (LaBRI)
- Volker Turau, Rapporteur & Examinateur
Professeur, Hamburg University of Technology (Institut für Telematik)
- Hugues Fauconnier, Examinateur
Professeur, Université de Paris (IRIF)
- Sébastien Tixeuil, Examinateur
Professeur, Sorbonne Université (LIP6)
- Joffroy Beauquier, Directeur de thèse
Professeur émérite, Université Paris-Saclay (LRI)
- Thibault Bernard, Co-encadrant
Maître de conférences, Université de Reims (Li-PaRAD, UP-Saclay)
- Janna Burman, Co-encadrante
Maîtresse de conférences, Université Paris-Saclay (LRI)
Activités de recherche :
Résumé :
Le Problème du Mariage Stable (SMP) est un problème d'appariement où les participants ont des préférences à propos de leurs partenaires potentiels. L'objectif est de trouver un appariement optimal (stable dans un sens) au regard des préférences. Ce type d'appariement a de très nombreuses applications comme les affectations d'étudiants à des universités (APB ou ParcourSup), celles des internes en médecine aux hôpitaux, les choix des donneurs pour les patients en attente d'organe, la mise en rapport des taxis et de leurs clients ou encore la diffusion de contenu sur Internet. Certaines de ces applications peuvent être traitées de manière centralisée tandis que d'autres, de par leur nature distribuée et la complexité de leurs données, nécessitent un traitement différent.
Dans ce contexte, nous proposons deux solutions distribuées auto-stabilisantes (i.e. qui tolèrent les défaillances transitoires (ou de courte durée) de n'importe quels nœuds). Pour ces deux algorithmes, les exécutions se déroulent par pas atomiques et un démon (démon distribué inéquitable) exprime la notion d'asynchronisme. Avec ce démon, le temps de stabilisation peut être borné en terme de moves (pas locaux). Cette mesure de complexité permet d'évaluer avec précision la puissance de calcul nécessaire ou l'énergie dissipée par les exécutions de l'algorithme.
Le premier algorithme, basé sur la méthode centralisée de Ackermann et al. (SICOMP' 2011), résout le SMP en O(n^4) moves.
Le point de départ du deuxième algorithme est le schéma de détection locale/correction globale de Awerbuch et al. (DA' 1994). Malheureusement, la définition de la vérifiabilité locale de DA' 1994 ne s'applique pas à notre cas (en particulier en raison du démon inéquitable). Nous proposons donc une nouvelle définition. De plus, nous concevons un algorithme de réinitialisation (reset) asynchrone, distribué et auto-stabilisant.
L'algorithme résultant résout le SMP en Theta(n^2) moves.
