On utilizing speed in networks of mobile agents

Joffroy Beauquier 1, 2 Janna Burman 3 Julien Clément 4 Shay Kutten 5
2 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
3 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Population protocols are a model presented recently for networks with a very large, possibly unknown number of mobile agents having small memory. This model has certain advantages over alternative models (such as DTN) for such networks. However, it was shown that the computational power of this model is limited to semi-linear predicates only. Hence, various extensions were suggested. We present a model that enhances the original model of population protocols by introducing a (weak) notion of speed of the agents. This enhancement allows us to design fast converging protocols with only weak requirements (for example, suppose that there are different types of agents, say agents attached to sick animals and to healthy animals, two meeting agents just need to be able to estimate which of them is faster, e.g., using their types, but not to actually know the speeds of their types). Then, using the new model, we study the gathering problem, in which there is an unknown number of anonymous agents that have values they should deliver to a base station (without replications). We develop efficient protocols step by step searching for an optimal solution and adapting to the size of the available memory. The protocols are simple, though their analysis is somewhat involved. We also present a more involved result - a lower bound on the length of the worst execution for any protocol. Our proofs introduce several techniques that may prove useful also in future studies of time in population protocols.
Type de document :
Communication dans un congrès
ACM Symposium on Principles of Distributed Computing, PODC 2010, Jul 2010, Zurich, Switzerland. ACM, 2010, 〈10.1145/1835698.1835775〉
Liste complète des métadonnées

Contributeur : Janna Burman <>
Soumis le : mardi 2 novembre 2010 - 17:02:22
Dernière modification le : jeudi 15 novembre 2018 - 20:26:55



Joffroy Beauquier, Janna Burman, Julien Clément, Shay Kutten. On utilizing speed in networks of mobile agents. ACM Symposium on Principles of Distributed Computing, PODC 2010, Jul 2010, Zurich, Switzerland. ACM, 2010, 〈10.1145/1835698.1835775〉. 〈inria-00531438〉



Consultations de la notice