Abstract FR:

Dans cette thèse, nous étudions différents aspects liés à la localité des algorithmes distribués. D'abord, dans le modèle avec échange de messages, nous donnons des algortithmes déterministes sous linéaires en temps pour la construction de décompositions peu denses de graphes et des applications sou-jacentes. Nous donnons aussi des algortithmes ayant une complexité en temps mieux que ous linéaire pour la construction de sous graphes couvrants ayalnt 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. Parmis nos résultats, nous obtenons de nouvelles idées pour améliorer les algortithmes existants dans le modèle avec échange de messages. Dans une approche plus formelle, nous montrons à travers plusieurs exemples comment on peut coder des algorthmes distribués complexes en utilisant le formalisme des systèmes de réétiquetage. Dans une approche plus pratique, nous exposons nos contributiond dans le développement de la plateforme logicielle ViSiDiA pour la simulation et la visualisation d'algorithmes distribués.