| Version imprimable |
| Analyse probabiliste de protocoles de population (Probabilistic analysis of population protocols) | ||
Mocquard, Yves - (2018-12-13) / Universite de Rennes 1 - Analyse probabiliste de protocoles de population Langue : Français Directeur de thèse: Sericola, Bruno; Anceaume, Emmanuelle Laboratoire : IRISA Ecole Doctorale : MATHSTIC Thématique : Informatique | ||
Mots-clés : protocoles de population, diffusion de rumeur, boules et urnes, moyenne, probabilités, Protocoles de réseaux d'ordinateurs, Probabilités Résumé : 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. Résumé (anglais) : We are in the context of the population protocols model. This model, introduced in 2004 by Angluin et al., provides the theoretical basis for analyzing the properties emerging from a system consisting of anonymous agents interacting in pairs. In this framework, we analyze in depth four protocols: the spreading protocol, average with integers, average with reals and the clock protocol. Regarding the spreading protocol, our analysis provides a precise and simple expression of the spreading time distribution tail. We also analyze in depth the asymptotic behavior of the distribution when n tends to infinity. Regarding the average protocol with integers, we demonstrate that the protocol converges in a parallel time of O(log n) to a state where the maximum difference between two values is 2. This result allows us to prove the space and time optimality of our proportion and counting protocols. Regarding the average protocol with reals, using the 4-norm, we significantly reduce the constants of the convergence time bounds. Regarding the clock protocol, we explain the constants of the bounds. Next, we build proportion protocol with convergence detection, which uses our results on diffusion, proportion, and clock. We also show that this convergence detection protocol can be applied to any protocol which is explicitly known as a convergence time bound with high probability. Identifiant : rennes1-ori-wf-1-11819 | ||
| Exporter au format XML |