en fr Presentation and study of some distributed algorithm problems Présentation et étude de quelques problèmes dalgorithmique distribuée Report as inadecuate




en fr Presentation and study of some distributed algorithm problems Présentation et étude de quelques problèmes dalgorithmique distribuée - Download this document for free, or read online. Document in PDF available to download.

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Abstract : In this thesis, we first present a study of several problems in the field of distributed algorithms.
We provide a formal model that relies on anonymous networks.
In this model, we characterize graphs in which it is possible to solve enumeration and leader election problems.
This characterization is based on graph homomorphism.
We introduce two algorithms with polynomial complexities that improve existing works with exponential complexities.
On the other hand, we study the snapshot problem and we introduce the notion of weak snapshot.
We show that there exist solutions for this problem in the context of anonymous networks.
We present several results about distributed snapshots that deal with checkpoint and rollback recovery, termination detection or the cartography computation of a network.
In a practical aspect, we present the conception, the development process and the implementation of these distributed snapshot algorithms within the simulation and visualization software ViSiDiA.


Résumé : Nous proposons tout d-abord une étude de plusieurs problèmes de l-algorithmique distribuée.
Nous fournissons un modèle formel appliqué aux réseaux de diffusion anonymes.
Dans ce modèle, nous caractérisons les graphes dans lesquels il est possible de résoudre l-énumération et l-élection.
Cette caractérisation se base sur la notion d-homomorphisme de graphes.
Nous proposons deux algorithmes dont la complexité est polynomiale et qui améliorent les complexités exponentielles connues jusqu-à présent.
Dans un second temps, nous étudions le problème du calcul de l-état global et nous introduisons la notion de weak snapshot.
Nous montrons qu-il existe des solutions pour ce problème dans les réseaux anonymes.
Nous présentons plusieurs résultats concernant le calcul de l-état global en liaison avec des applications telles que le calcul de points de reprise, la détection de la terminaison ou encore le calcul d-une cartographie du réseau.
Dans un cadre plus pratique, nous présentons la conception, le développement et l-implémentation des algorithmes proposés pour le calcul de l-état global au sein du logiciel de simulation et de visualisation ViSiDiA.


en fr

Keywords : Distributed algorithm Modelization Graph Anonymous network Snapshot Leader election Stable property Debugging Visualization

Mots-clés : Algorithme distribué Modélisation Graphe Réseau anonyme État global Élection Énumération Propriété stable Débogage Visualisation Algorithmes Théorie des Graphes Réseaux anonymes





Author: Thomas Morsellino -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents