Cette thèse traite l’utilisation des agents mobiles dans le domaine des algo- rithmes distribués en les déplaçant de manière aléatoire dans le réseau. Initialement k agents mobiles ayant les identités uniques sont placés dans le réseau. On décrit un algorithme distribué pour calculer un arbre couvrant dans les réseaux dynamiques en utilisant les agents mobiles. Les agents marquent les noeuds sur les quelles ils arrivent. Ils utilisent deux techniques di?érentes : le clonage dans lequel un agent crée son propre clone pour faire quelques tâches et le marquage sur la tableau de bord (un espace mémoire sur les noeuds). Ces techniques sont utilisés dans les applications comme l’arbre couvrant, le rassemblement et la collecte d’information. Chacun des agents détient une information partielle. Quand deux ou plusieurs agents se rencontrent sur un noeud, ils fusionnent en un seul agent. On s’intéresse alors au temps nécessaire ou tous les k agents fusionnent en un seul et unique agent. On présent une chaîne de Markov pour le comportement des agents, et on montre comment on peut utiliser cette technique pour calculer la bourne supérieur. On étudie le même problème quand les agents mobile commencent la marche aléatoire sous un régime stationnaire. On a aussi étudié le problème de Handshake et on l’a analysé en utilisant les agents mobiles. / This thesis deals with the use of mobile agents in distributed algorithms by performing random walks in the network. k mobile agents having unique identities are placed initially in a network. We describe a distributed algorithm for computing spanning trees in dynamic networks by using mobile agents. The agents mark the nodes on which they arrive. They use two di?erent techniques. In one problem they use the cloning in which an agent creates its own clone to do some task assigned. In the second, the mobile agents mark on the whiteboard (a memory location on the nodes). These techniques are used in applications such as spanning tree, gathering and collecting information. The mobile agents have limited knowledge and hence, they are not intelligent and do not have computational capabilities. When two or more agents meet at a node of the underlying graph, they merge into a single agent. The parameter of interest is the expected time for all the agents to merge into a single agent. We present a Markov chain, modelling the agents behavior, and show how this can be used to upper bound the expected time for all the k agents to merge into a single agent. We study the same problem when the mobile agents start their walk directly under stationary regime. Handshake problem is also studied and analyzed using mobile agents.

De nos jours, les systèmes distribués doivent répondre de plus en plus à de nouvelles exigences de qualité de service et à l’émergence de nouvelles applications comme le calcul sur la grille ; ce qui généralement se traduit par des impératifs de dynamicité et de mobilité. Si des solutions satisfaisantes existent pour des environnements distribués statiques, elles sont inadaptées dans le cas où le système devient dynamique (mobilité, évolution, modification de composants). En effet, la conception d’algorithmes distribués est traditionnellement fondée sur l’hypothèse d’un réseau dont la topologie est statique. Notre objectif dans cette thèse est de définir et d’étudier un modèle à base d’agents mobiles pour l’implémentation et l’exécution d’algorithmes distribués codés par des calculs locaux.Ce modèle doit tenir en compte des pannes qui peuvent altérer le fonctionnement du système distribué. Il doit aussi améliorer les performances vis-à-vis des modèles classiques (à envoi de messages) / Today, distributed systems must satisfy increasinglynew requirements for quality of service and the emergence ofnew applications such as Grid Computing, whichgenerally results in requirements of dynamicity andmobility. If satisfactory solutions exist forstatic distributed environments, they are inadequate in the casewhere the system becomes dynamic (mobility, evolution,components change). Indeed, the design of distributed algorithms istraditionally based on the assumption of a network whosetopology is static. Our goal, in this thesis, is to defineand study a model based on mobile agents to implementand execute distributed algorithms encoded by local computations.This model must take into account failures that can alter thethe distributed system operation. It should also improveperformance vis-à-vis the classical models (message passing systems)