Soutenance mémoire
Les réseaux informatiques modernes sont de taille de plus en plus gigantesques et la distribution des calculs est un passage obligé. Cette distribution peut se contrôler de manière centralisée. Cela conduit à deux inconvénients : d’une part le système devient entièrement dépendant de la machine qui est au centre et contrôle la distribution, rendant le système extrêmement vulnérable à une attaque ou même tout simplement à une panne ; d’autre part les échanges se faisant essentiellement entre cette machine centrale et les autres, un goulot d’étranglement sur la bande passante existera obligatoirement au niveau de la machine centrale.
Avec un système distribué non centralisé, il est important d’obtenir des informations sur l’état global du système ce qui est loin d’être trivial en l’absence de centralisation. Les protocoles de population offrent une solution en permettant l’émergence de certaines données globales du système uniquement au moyen d’interactions pair à pair aléatoires. Les données globales qui peuvent ainsi être collectées, sont la proportion, le nombre ou la majorité de noeuds dans un certain état, ou encore un horodatage du système où l’unité de temps est soit l’interaction par site, soit le temps d’une diffusion.
Déroulement de la thèse
Premier contact avec les protocoles de population
En 2015, dans le cadre de mon stage de Master 2 à l’Irisa sur les protocoles de population, j’ai lu un article de Aspnes et Ruppert [15] qui présente un protocole de majorité [15]. En effectuant des simulations, je me suis rendu compte que le protocole ne fonctionnait pas. Nous avons prouvé que la probabilité qu’il fonctionne était inférieure à 1/n!, n étant la taille du système. Nous avons informé James Aspnes qui nous a indiqué de supprimer la dernière interaction. Effectivement, cette suppression a permis d’obtenir le protocole à quatre états déjà publié dans [33] et [51]. Ce fut le point de départ d’échanges fructueux sur nos travaux respectifs, particulièrement sur les protocoles basés sur la moyenne avec des nombres réels ou entiers.
Le protocole basé sur la moyenne
Dans le cadre de la thèse, les simulations montraient que le protocole de moyenne pouvait être amélioré en diminuant le nombre d’états nécessaires, sans que la performance en nombre d’interactions en pâtisse. En effet, au regard des simulations nous constatons qu’un protocole de moyenne avec des entiers converge vers un état où la différence maximale entre deux valeurs est inférieure ou égale à 2, en O(n log n) interactions.
Le protocole de diffusion de rumeur
Au printemps 2016, nous avons travaillé sur la diffusion de rumeur. Des résultats nouveaux ont été obtenus sur la queue de distribution et sur la fonction de répartition du temps de convergence du protocole de diffusion de rumeur. Nous avions également des résultats intéressants sur le comportement de la fonction de répartition du temps de convergence autour de l’espérance quand on fait tendre n (la taille du système) vers l’infini.
Le modèle des protocoles de population
Le modèle formel et conventions d’écriture
Définition Un protocole de population sur un graphe d’interaction complet se caractérise par un sextuplet (Σ, Q, Ξ, ι, f, ω) comprenant :
• un ensemble d’entrée : Σ est l’ensemble fini des états d’entrée. C’est l’ensemble des états possibles des agents à l’origine.
• un ensemble d’états : Q est l’ensemble fini des états de travail de chaque agent. Ce sont ces états qui entrent en jeu lors d’une interaction entre deux agents.
• un ensemble de sortie : Ξ est l’ensemble fini des états de sortie. Quand on interroge un agent, le résultat est un élément de cet ensemble.
• une fonction d’entrée ι : Σ → Q, est la fonction qui permet d’initialiser l’état de travail à partir de l’état d’entrée.
• une fonction de transition f : Q × Q → Q × Q, fonction de transition, elle définit la mise à jour des états de chaque agent lors d’une interaction.
• une fonction de sortie ω : Q → Ξ, fonction qui donne le résultat de l’interrogation d’un agent. C’est une fonction de l’état de travail.
Chaque sommet du graphe d’interaction est un agent et chaque arête a pour poids la probabilité d’interaction entre deux agents.
Initialement, chaque agent possède un symbole de Σ, la fonction d’entrée permet, en fonction de ce symbole, d’initialiser l’état de chaque agent avec un élément de Q. Puis, lors des interactions entre les agents, cet état est mis à jour selon la fonction de transition f. A tout instant, on peut interroger un agent qui répondra par un élément de Ξ, cet élément est l’image par la fonction ω de l’état de cet agent.
Les interactions entre agents sont orchestrées par un ordonnanceur aléatoire : à chaque instant discret, deux agents sont choisis au hasard pour interagir. La notion de temps dans les protocoles de population désigne le nombre d’interactions global, tandis que le temps parallèle désigne la moyenne du nombre d’interactions initiées par chaque agent [15]. Le temps parallèle est donc le temps global divisé par la taille n du système. Les agents sont anonymes, ils ne gèrent ni n’utilisent d’identifiant. Cependant, pour faciliter la présentation, les agents sont numérotés de 1 à n. Pour conserver la notion d’anonymat, il va de soi qu’aucun agent ne connaît son numéro. Les agents n’ont aucune connaissance directe du temps. Cependant, ils sont représentés par une composante d’un vecteur indicé par le temps t qui représente le nombre total d’interactions ayant eu lieu dans le système depuis l’origine.
Performance d’un protocole de population
Un problème étant posé, il peut y avoir plusieurs protocoles permettant de le résoudre. nous examinons les deux critères fondamentaux qui mesurent la performance de ces protocoles. Ces deux critères, par analogie avec les problèmes algorithmiques classiques, sont nommés le temps et l’espace.
Le temps de convergence
Le temps de convergence est, comme nous l’avons déjà dit, une variable aléatoire. Pour un protocole, ce temps correspond à la durée nécessaire pour atteindre la convergence qui est son objectif. Comme en algorithmique classique, plus ce temps est réduit plus le protocole est performant. Deux indicateurs sur le temps de convergence nous permettent de cerner les performances temporelles d’un protocole de population.
• Le temps de convergence moyen ou espérance du temps de convergence
• Le temps de convergence avec probabilité élevée est le temps après lequel la probabilité de convergence est supérieure à 1−1/n, n étant le nombre d’agents.
Le temps de convergence avec probabilité élevée possède deux autres formulations plus précises. Pour l’une il s’agit, σ > 0 étant donné, du temps après lequel la probabilité de convergence est supérieure à 1 − 1/nσ . Pour l’autre, δ ∈]0; 1[ étant donné, il s’agit du temps après lequel la probabilité de convergence est supérieure à 1−δ. Il est clair que ces deux dernières formes sont équivalentes et elles impliquent la première (en prenant σ = 1 ou δ = 1/n). Nous préférons utiliser la formulation avec δ dans la mesure où cela donne une information plus fine sur le temps de convergence.
|
Table des matières
INTRODUCTION
1 Introduction
1.1 Déroulement de la thèse
1.1.1 Premier contact avec les protocoles de population
1.1.2 Le protocole basé sur la moyenne
1.1.3 Le protocole de diffusion de rumeur
1.1.4 Une mesure fructueuse
1.1.5 Le protocole de diffusion de rumeur, suite
1.1.6 L’horloge globale
1.1.7 La détection de convergence
1.2 Méthodologie
1.2.1 Les simulations
1.2.2 Les démonstrations
1.3 Organisation du manuscrit
2 Le modèle des protocoles de population
2.1 Les protocoles de population
2.2 Le modèle formel et conventions d’écriture
2.3 Performance d’un protocole de population
2.3.1 Le temps de convergence
2.3.2 Le nombre d’états
2.4 Précisions sur le modèle
2.4.1 Push, pull et push/pull
2.4.2 Synchrone/asynchrone
2.4.3 Modèle de fautes
2.4.4 Temps discret/continu
3 Problèmes étudiés
3.1 La diffusion de rumeur
3.1.1 Définition
3.1.2 État de l’art
3.1.3 Nos résultats
3.2 Le comptage
3.2.1 Définition
3.2.2 État de l’art
3.2.3 Nos résultats
3.3 Le problème de la proportion
3.3.1 Définition
3.3.2 État de l’art
3.3.3 Nos résultats
3.4 La majorité
3.4.1 Définition
3.4.2 État de l’art
3.4.3 Nos résultats
3.5 L’horloge globale ou horloge sans leader
3.5.1 Définition
3.5.2 État de l’art
3.5.3 Nos résultats
4 Diffusion de rumeur
4.1 Introduction
4.2 Diffusion de rumeur en temps discret
4.2.1 Modélisation
4.2.2 La diffusion
4.2.3 Analyse du temps de diffusion
4.2.3.1 Espérance et variance de Tn
4.2.3.2 Expression explicite de la distribution de Tn
4.2.3.3 Bornes et queue de la distribution de Tn
4.2.4 Analyse asymptotique de la distribution de Tn
4.2.5 Simulation de la diffusion de rumeur
4.3 Diffusion de rumeur en temps continu
4.3.1 Espérance et variance de Θn
4.3.2 Expression explicite de la distribution de Θn
4.3.3 Bornes et queue de la distribution de Θn
4.3.4 Analyse asymptotique de la distribution de Θn
4.4 Conclusion
5 Protocoles basés sur la moyenne
CONCLUSION
