Des calculs locaux aux algorithmes distribués

Abstract

L'objectif de cette thèse est de montrer que le modèle des systèmes de réécriture de graphe est un modèle pertinent pour l'étude, la compréhension et l'implémentation des algorithmes distribués. Dans un algorithme distribué, la détection de terminaison est difficile puisqu'un algorithme est exécuté par plusieurs processus en parallèle et l'algorithme ne se termine que lorsque tous les processus ont fini. Pour résoudre ce problème, nous utilisons un produit particulier de deux systèmes de réécriture de graphe. Le premier code l'algorithme dont nous voulons détecter sa terminaison et le second code un des algorithmes qui détecte la terminaison globale. Les algorithmes asynchrones sont souvent moins performants que les algorithmes correspondants synchrones. Il est très utile de disposer d'une méthode générale qui permet de simuler les algorithmes synchrones sur des systèmes asynchrones. Nous utilisons un autre produit, similaire à celui utilisé pour la résolution du problème de détection de terminaison, pour résoudre ce problème. Nous avons implémenté une plate-forme appelée Visidia qui utilise les systèmes de réécriture de graphe pour implémenter les algorithmes distribués. Visidia permet de tester, expérimenter, valider et visualiser l'exécution des algorithmes distribués codés sous forme de systèmes de réécriture de graphe ou sous forme de calcul local. Nous utilisons Visidia pour faire des expérimentations sur des algorithmes qui résolvent le problème de partage des ressources. Plusieurs algorithmes ont été testés dont la généralisation du problème des philosophes, l'exclusion mutuelle dans un arbre et enfin, une généralisation du problème de l'exclusion mutuelle dans un réseau quelconque.