Distributed calculations using mobile agents

Shehla Abbas

Description

Sous la direction de Mohamed Mosbah
Thèse soutenue le 15 décembre 2008: Bordeaux 1
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.
-Agents mobiles
-Marche aléatoire
-Algorithmes Distribués
-Analyse de complexité
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.
-Mobiles Agents
-Random Walks
-Complexity Analysis
Source: http://www.theses.fr/2008BOR13716/document

Sujets

• Marche aléatoire

Informations

• Publié par: Thesee
• Nombre de lectures: 27
• Langue: English

Extrait

◦N d’ordre : 3716
THÈSE
présentée à
L’UNIVERSITÉ BORDEAUX I
ÉCOLE DOCTORALE DE MATHÉMATIQUES ET INFORMATIQUE
par Shehla ABBAS
POUR OBTENIR LE GRADE DE
DOCTEUR
SPÉCIALITÉ : Informatique
Distributed Calculations using
Mobile Agents
Soutenue le : lundi 15 décembre 2008
Après avis de :
MM. Olivier FLAUZAC ......... Professeur
Stefan GRUNER .......... Professeur Rapporteurs
Devant la commission d’examen formée de :
MM. Yves MéTIVIER ........... Professeur Président
Olivier FLAUZAC ......... Professeur Rapporteur
Emmanuel GODARD ...... Maître de Conférences Examiner
Mohamed MOSBAH ....... Professeur Directeur
Akka ZEMMARI .......... Maître de Conférences Co-Directeur
– 2008 –iiAcknowledgements
I would like to thank the members of the jury Mr. Yves Métivier who honored me by
presiding the jury for this thesis, Mr Emmanuel Godard and the reporters Mr. Olivier
Flauzac and Mr. Stefan Gruner for their critical and interesting remarks which helped me
in improving my thesis.
I would also like to take this oppourtunity to thank my thesis supervisors Professor
Mohamed Mosbah and Akka Zemmari without whose help this task would not have been
possible. Their continuous support and guidance helped me in the accomplishment of this
task.
I am also thankful to my colleagues working in the lab. LaBRI has provided me with
all the necessary resources to facilitate my research work. I also acknowledge the support
of the administrative department, the technicians, the professors specially Nasser Saheb
who encouraged me a lot and inspired me all the times to work hard. My fellow colleagues
Anthony, Hejer, Mubashar and others were also a source of strength for me and also
extended their support whenever I needed. We have been sharing both moments of joy
and critical moments.
Last but not least I thank my parents whose prayers have always been with me and
they always motivated me in achieving this goal. I also can not forget my husband’s
support who sacrificed for me by moving with me and supporting me all the times. I also
feel delighted to make a mention of my expected child to whom I wish to welcome in this
world.
iiiivCalculs Distribués par des Agents Mobiles
Résumé : 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 diffé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écessaireoutouslesk agentsfusionnentenunseuletuniqueagent. Onprésentunechaîne
de Markov pour le comportement des agents, et on montre comment on peut utiliser cette
techniquepourcalculerlabournesupérieur. Onétudielemêmeproblèmequandlesagents
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.
Mots-clef : Les agents mobiles, marche aléatoire, algorithmes distribués, analyse de com-
plexité, rendezvous.
Discipline : Informatique
Distributed Calculations using Mobile Agents
Abstract : 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 describea distributed algorithmfor computingspanningtrees in dynamicnetworks
by using mobile agents. The agents mark the nodes on which they arrive. They use two
different 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
underlyinggraph, theymergeintoasingleagent. Theparameterofinterestistheexpected
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.
Keywords: MobileAgents,RandomWalks,DistributedAlgorithms,ComplexityAnalysis,
Rendezvous.
Field : Computer Science
vviContents
Résumé / Abstract v
Résumé 1
Introduction 5
I PRELIMINARIES 9
1 Definitions and Notations 11
1.1 Graph Theory Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.2 Particular Classes of Graphs . . . . . . . . . . . . . . . . . . . . . . 13
1.1.3 Graph Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 The Synchronism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Randomized Algorithms and Random Walks . . . . . . . . . . . . . . . . . . 14
1.3.1 Randomized Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.2 Random Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Mobile Agents. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Mobile Agents: Parameters and Models 19
2.1 Mobile Agent Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Mobile Agents Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.1 Mobile Robots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.2 Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3 Mobile agents model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1 Mobile Agents’ Placement . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.2 Single vs Multiple agents . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4 Mobile agents’ behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5 Mobile agents applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Mobile agents rendezvous on different classes of graphs . . . . . . . . . . . . 32
II MOBILE AGENTS ALGORITHMS 35
3 Distributed Computation of a Spanning Tree in a Dynamic Graph by
Mobile Agents 37
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
vii3.2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4 Wave Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4.1 Termination detection . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4.2 Dynamicity: mobility of network . . . . . . . . . . . . . . . . . . . . 50
3.5 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.5.1 Visidia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.5.2 Implementation of algorithm . . . . . . . . . . . . . . . . . . . . . . 53
3.5.3 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.6 Conclusion and Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4 A Generic Algorithm for Computing by Random Mobile Agents 59
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.1.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.1.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.2 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3 Generic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
III COMPLEXITY ANALYSIS ISSUES 73
5 Merging Time of Random Mobile Agents 75
5.1 Introduction . . . .