Local Maps: New Insights into Mobile Agent Algorithms

Bilel Derbel 1, 2, *
* Auteur correspondant
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : In this paper, we study the complexity of computing with mobile agents having small local knowledge. In particular, we show that the number of mobile agents and the amount of local information given initially to agents can significantly influence the time complexity of resolving a distributed problem. Our results are based on a generic scheme allowing to transform a message passing algorithm, running on an $n$-node graph $G$, into a mobile agent one. By generic, we mean that the scheme is independent of both the message passing algorithm and the graph $G$. Our scheme, coupled with a well-chosen clustered representation of the graph, induces $\widetilde{O}(1) ratio between the time complexity of the obtained mobile agent algorithm and the time complexity of the original message passing counterpart, while using $\widetilde{O}(n)$ mobile agents. If only $k$ agents are allowed ($k$ is an integer parameter), then we show that the time ratio is $O(n/\sqrt{k})$. As a consequence, we show that any global labeling function of $G$ can be computed by exactly $n$ mobile agents knowing their $n^{\epsilon}$-neighborhood in $\widetilde{O}(D)$ time, $D$ is the diameter of the graph and $\epsilon$ is an arbitrary small constant. We apply our generic results for the fundamental problem of computing a leader (resp. a BFS tree) under the additional restriction of $\widetilde{O}(1)$ (resp. $\widetilde{O}(n)$) memory bits per agent, and obtain $\widetilde{O}(D)$ time algorithms.
Type de document :
Rapport
[Research Report] RR-6511, INRIA. 2008, pp.23
Liste complète des métadonnées

Littérature citée [49 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00271624
Contributeur : Bilel Derbel <>
Soumis le : lundi 21 avril 2008 - 12:01:39
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 21:56:39

Fichier

RR-6511.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00271624, version 3

Citation

Bilel Derbel. Local Maps: New Insights into Mobile Agent Algorithms. [Research Report] RR-6511, INRIA. 2008, pp.23. 〈inria-00271624v3〉

Partager

Métriques

Consultations de la notice

257

Téléchargements de fichiers

241