|
|<
<< Page précédente
1
Page suivante >>
>|
|
documents par page
|
Tri :
Date
Titre
Auteur
|
|
Informatique
/ 13-12-2018
Mocquard Yves
Voir le résumé
Voir le 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.
|
|
|<
<< Page précédente
1
Page suivante >>
>|
|
documents par page
|