Vous êtes ici

Analyse probabiliste de protocoles de population

Nous nous situons dans le contexte du modèle des protocoles de population. Ce modèle, introduit en 2004 par Angluin et al., fournit les bases théoriques pour analyser les propriétés émergeant d'un système constitué d'agents anonymes interagissant deux à deux.
Dans ce cadre, nous analysons en profondeur quatre protocoles : le protocole de diffusion, de moyenne avec des entiers, de moyenne avec des réels et le protocole d'horloge.
En ce qui concerne le protocole de diffusion, notre analyse fournit une expression précise et simple de la queue de distribution du temps de diffusion. Nous analysons aussi en profondeur le comportement asymptotique de la distribution quand n tend vers l'infini.
En ce qui concerne le protocole de moyenne avec des entiers, nous démontrons que le protocole converge en un temps parallèle de O(log n) vers un état où la différence maximale entre deux valeurs est égale à 2. Ce résultat nous permet de prouver l'optimalité en espace et en temps de nos protocoles de proportion et de comptage.
En ce qui concerne le protocole de moyenne avec des réels, par l'utilisation de la norme 4, nous réduisons considérablement les constantes des bornes de convergence.
En ce qui concerne le protocole d'horloge, nous explicitons les constantes des bornes.
Ensuite, nous construisons un protocole de proportion avec détection de convergence, qui utilise nos résultats sur la diffusion, la proportion et l'horloge. Nous montrons également que ce protocole de détection de convergence peut s'appliquer à tout protocole dont on connaît explicitement une borne du temps de convergence avec probabilité élevée.

Orateur: 
Yves MOCQUARD
Date: 
Jeudi, 13. décembre 2018 - 10:00
Lieu: 
IRISA Rennes - Salle Métivier
Type soutenance: 
Composition du Jury: 
  • Johanne COHEN, DR CNRS au LRI - Université Paris Sud, Rapportrice
  • Landy RABEHASAINA, MdC HDR au Laboratoire de Mathématiques de Besançon, Rapporteur
  • François CASTELLA, PR à l'IRMAR - Université de Rennes 1, Examinateur
  • Jérémie CHALOPIN, CR CNRS au LIS - Marseille, Examinateur
  • Bruno SERICOLA, DR INRIA - Rennes, Directeur de thèse
  • Emmanuelle ANCEAUME, CR CNRS à l'IRISA - Rennes, Co-encadrante