Conception et Analyse de quelques Algorithmes Distribués Probabilistes

Résumé

Un système distribué est un environnement où plusieurs processus collaborent pour réaliser un objectif commun. Dans un réseau, les différents processus ne peuvent communiquer directement qu’avec un nombre limité d’autres processus, leurs « voisins ». L’algorithmique distribuée a pour but de décrire quelles sont les tâches qui peuvent être réalisées dans de tels systèmes. Autrement dit, elle cherche à déterminer quels sont les comportements globaux qui peuvent être obtenus dans de tels systèmes où les comportements des différents processus ont des effets locaux. Un élément du réseau est un « noeud » et ce qui permet de distinguer un noeud d’un autre peut être un identifiant (comme une adresse IP sur Internet), mais plus généralement, c’est la position de chaque noeud dans le réseau qui permet de le distinguer. Ce qui caractérise les systèmes distribués est qu’il n’existe pas a priori de système de centralisation qui peut coordonner globalement les différents processus. Les travaux de cette thèse s’intègrent dans ce contexte et présentent l’évolution et l’analyse des performances des algorithmes probabilistes entièrement distribués et décentralisés et ce dans des systèmes distribués anonymes, asynchrones et de topologies différentes. Dans un premier temps nous proposons et étudions un algorithme d’élection probabiliste uniforme dans des structures de type « graphes à grilles triangulaires ». Cet algorithme est basé sur l’utilisation des délais aléatoires associés aux sommets supprimables (les sommets simpliciaux). Ces délais sont indépendants et peuvent être générés localement par des sommets au fur et à mesure qu’ils deviennent supprimables. Pour la classe de graphes citée ci-dessus, notre résultat principal est l’introduction d’un algorithme d’élection totalement équitable, c’est-à-dire que quelque soit l’emplacement d’un sommet dans un graphe, il a la même probabilité d’être « élu » que tous les autres sommets. Dans un second temps, nous introduisons et analysons deux algorithmes distribués probabilistes de construction d’arbre couvrant minimal. Ces algorithmes sont basés essentiellement sur un algorithme de rendez-vous. Tout d’abord, chaque arête sur laquelle un rendez-vous à eu lieu est considérée comme un sous-arbre couvrant. A chaque tour de l’exécution de l’algorithme, les sous-arbres couvrants sont fusionnés. La construction de l’arbre couvrant minimal s’arrête lorsque tous les sous-arbres couvrants sont fusionnés en un seul. Nous montrons par la suite que le graphe construit est un arbre couvrant minimal. Finalement, nous présentons une plate-forme de simulation des algorithmes distribués permettant d’implémenter, tester et vérifier les algorithmes distribués codés sous forme de calculs locaux et spécialement ceux décrits sous forme de règles de réécriture.

Citer ce document

Accès au document

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Statistiques

Consultations : 4

Téléchargements : 0