Des aspects locaux dans les algorithmes distribués

Abstract

Dans cette thèse, nous étudions différents aspects liés à la localité des algorithmes distribués. D'abord, dans le modèles avec échange de messages, nous donnons des algorithmes déterministes sous linéaires en temps pour la construction de décompositions peu denses de graphes et des applications sous-jacentes. Nous donnons aussi des algorithmes ayant une complexité en temps mieux que sous linéaire pour la construction de sous graphes couvrants ayant peu d'arêtes et un petit facteur d'étirement. Ensuite, nous étudions le problème de la poignée de main distribuée (ou calcul de couplage en temps constant) dans le modèle avec agents mobiles ainsi que deux autres extentions de ce problème. Parmi nos résultats, nous obtenons de nouvelles idées pour améliorer les algorithmes existants dans le modèle avec échange de messages. Dans une approche plus formelle, nous montrons à travers plusieurs exemples comment on peut coder des algorithmes distribués complexes en utilisant le formalisme des systèmes de réétiquetage. Dans une approche plus pratique, nous exposons nos contributions dans le développement de la plateforme logicielle ViSiDiA pour la simulation et la visualisation d'algorithmes distribués.