Université de Rennes 1 Analyse probabiliste de protocoles de population Probabilistic analysis of population protocols protocoles de populationdiffusion de rumeurboules et urnesmoyenneprobabilités population protocolsrumor spreadingballs-and-binsaverageprobabilities Protocoles de réseaux d'ordinateursThèses et écrits académiques ProbabilitésThèses et écrits académiques 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. 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. Electronic Thesis or DissertationText fr application/pdf1 : 1894 Kohttps://ged.univ-rennes1.fr/nuxeo/site/esupversions/5b01c046-7555-4753-bf6d-898a874cce5b Mocquard Yves 1958-12-15 FR 235444790 mocquard.yves@orange.fr 2018REN1S080 http://www.theses.fr/2018REN1S080 2018-12-13 Informatique Universite de Rennes 1thesis.degree.grantor_1 02778715X Doctorat non ouiSericolaBrunointervenant_1077485343AnceaumeEmmanuelleintervenant_2110342496 MATHSTICecoleDoctorale_1 204770424 Universite Bretagne LoirepartenaireRecherche_1 191639044 IRISA partenaireRecherche_2 026386909 ddc:004 SericolaBrunoAnceaumeEmmanuelleUniversite de Rennes 1Sciences et technologie, medecine, pharmacie, odontologie, droit, economie, gestion, philosophieMATHSTICÉcole doctorale Mathématiques et sciences et technologies de l'information et de la communication (Rennes)Universite Bretagne Loire Communaute des etablissements d enseignement superieur et de recherche (ComuE) IRISA ASCII PDF 1939094