Anatolii Kostrygin soutiendra sa thèse intitulée «Analyse précise des algorithmes épidémiques» le mardi 29 août 2017 à 14h00 dans la salle Grace Hopper.

Résumé: Dans cette thèse nous étudions le problème de propagation de rumeur, c.-à-d. la dissémination collaborative, robuste et anonyme d’une information entre tous les agents d’un système distribué. Ce problème est à la base de nombreux algorithmes de communication sur des réseaux de capteurs sans-fil ou des réseaux mobiles ad-hoc. Il est aussi une brique centrale pour les nombreux algorithmes distribués avancés.

Nous proposons une méthode générale d’analyse des protocoles de la propagation de rumeur dans les graphes complets. Contrairement aux résultats précédents basés sur la structure précise des processus étudiés, notre analyse est basée sur la probabilité et la covariance des évènements correspondants au fait qu’un agent non-informé s’informe. Cela nous permet de reproduire les résultats basiques concernant les protocoles classiques de push, pull et push-pull ainsi qu’analyser les certaines variations telles que les échecs de communications ou les communications multiples réalisées par chaque agent. De plus, nous sommes capables d’analyser les certains modèles dynamiques quand le réseaux forme un graphe aléatoire échantillonné à nouveau à chaque étape. Notre méthode nous permet de déterminer l’espérance du temps de la diffusion à une constante additive près, ce qu’il est plus précis que la plupart des résultats précédents. Nous montrons que la déviation du temps de la diffusion par rapport à son espérance est inférieure d’une constante r avec la probabilité au moins 1 − exp(Ω(r)).

Nous discutons d’une hypothèse classique que les agents peuvent répondre à plusieurs appels entrants. La restriction à un seul appel entrant par agent provoque un ralentissement important de la diffusion pour un protocole de push-pull. Nous proposons une variation simple du protocole de push-pull qui rétablit une phase double logarithmique à nouveau et donc le nombre de messages passés redescend sur sa valeur optimal.