Auditorium (IMAG)
1er septembre 2017 - 09h30
Algorithmes distribués efficaces adaptés à un contexte incertain (Phd Defense)
par Anaïs Durand de Verimag
Résumé : Les systèmes distribués sont de plus en plus grands et complexes, alors que leur utilisation s'étend à de nombreux domaines (par exemple, les communications, la domotique, la surveillance, le ``cloud''). Par conséquent, les contextes d'exécution des systèmes distribués sont très divers. Dans cette thèse, nous nous focalisons sur des contextes incertains, autrement dit, le contexte n'est pas complètement connu au départ ou il est changeant. Plus précisément, nous nous focalisons sur deux principaux types d'incertitudes : une identification incomplète des processus et la présence de fautes. L'absence d'identification est fréquente dans de grands réseaux composés d'appareils produits et déployés en masse. De plus, l'anonymat est souvent une demande pour la sécurité et la confidentialité. De la même façon, les grands réseaux sont exposés aux pannes comme la panne définitive d'un processus ou une perte de connexion sans fil. Néanmoins, le service fourni doit rester disponible.
Cette thèse est composée de quatre contributions principales. Premièrement, nous étudions le problème de l'élection de leader dans les anneaux unidirectionnels de processus homonymes (les processus sont identifiés mais leur ID n'est pas forcément unique). Par la suite, nous proposons un algorithme d'élection de leader silencieux et autostabilisant pour tout réseau connecté. Il s'agit du premier algorithme fonctionnant sous de telles conditions qui stabilise en un nombre polynomial de pas de calcul. La troisième contribution est une nouvelle propriété de stabilisation conçue pour les réseaux dynamiques qui garantit des convergences rapides et progressives après des changements topologiques. Nous illustrons cette propriété avec un algorithme de synchronisation d'horloges. Finalement, nous considérons la question de la concurrence dans les problèmes d'allocation de ressources. En particulier, nous étudions le niveau de concurrence qui peut être atteint dans une grande classe de problèmes d'allocation de ressources, l'allocation de ressources locales.
Jury:
- Karine Altisen, Mcf, Grenoble INP/VERIMAG (directrice)
- Stéphane Devismes, Mcf UGA/VERIMAG (encadrant)
- Paola Flocchini, Pr, Univ. Ottawa (examinatrice)
- Pierre Fraigniaud, DR, CNRS/IRIF (examinateur)
- Colette Johnen, Pr, Univ. Bordeaux/LabRI (examinatrice)
- Christian Scheideler, Pr, Univ Paderborn (rapporteur)
- Michel Raynal, Pr, Univ. Rennes/IRISA (examinateur)
- Sébastien Tixeuil, Pr, UPMC/LIP6 (rapporteur)
