On the Impact of the Mobility on Convergence Speed of Population Protocols

Yann Busnel 1 Marin Bertier 1 Anne-Marie Kermarrec 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : Population protocols provide theoretical foundations for mobile tiny device networks in which global behavior emerges from a set of simple interactions between anonymous agents. The works in this area mostly focus on studying the computational power of the model. Results hold as long as a fair scheduler, ensuring that all reachable system states are endlessly reached, governs the interactions between nodes. This assumption is crucial to ensure that the protocols eventually converge. This paper studies for the first time the impact of the agents? mobility model on the convergence speed of population protocols. We perform our study by considering several mobility models traditionally used in the ad-hoc network community. We propose an augmented population protocol model where each edge of the interaction graph is weighted, representing the probability of two agents to interact. This models the behaviour of the scheduler with respect to various mobility models. We empirically show that mobility models do have a significant impact on the convergence speed of the protocols. In fact, we observe that the uniform distribution always provides the best convergence time. Such a model is representative of the well-known random-way point model used to evaluate most of mobile ad-hoc network protocols. We then formally prove that a uniform distribution of weights provides the lowest bound of average convergence speed for any population protocol.
Type de document :
[Research Report] RR-6580, INRIA. 2008, pp.30
Liste complète des métadonnées

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

Contributeur : Yann Busnel <>
Soumis le : jeudi 27 novembre 2008 - 13:00:04
Dernière modification le : vendredi 12 octobre 2018 - 15:10:02
Document(s) archivé(s) le : samedi 26 novembre 2016 - 03:03:48


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00296584, version 2


Yann Busnel, Marin Bertier, Anne-Marie Kermarrec. On the Impact of the Mobility on Convergence Speed of Population Protocols. [Research Report] RR-6580, INRIA. 2008, pp.30. 〈inria-00296584v2〉



Consultations de la notice


Téléchargements de fichiers