Time and Space Optimal Counting in Population Protocols

Abstract : This work concerns the general issue of combined optimality in terms of time and space complexity. In this context, we study the problem of (exact) counting resource-limited and passively mobile nodes in the model of population protocols, in which the space complexity is crucial. The counted nodes are memory-limited anonymous devices (called agents) communicating asynchronously in pairs (according to a fairness condition). Moreover, we assume that these agents are prone to failures so that they cannot be correctly initialized. This study considers two classical fairness conditions, and for each we investigate the issue of time optimality of counting given the optimal space per agent. In the case of randomly interacting agents (probabilistic fairness), as usual, the convergence time is measured in terms of parallel time (or parallel interactions), which is defined as the number of pairwise interactions until convergence, divided by n (the number of agents). In case of weak fairness, where it is only required that every pair of agents interacts infinitely often, the convergence time is defined in terms of non-null transitions, i.e, the transitions that affect the states of the interacting agents. First, assuming probabilistic fairness, we present a " non-guessing " time optimal protocol of O(n log n) expected time given an optimal space of only one bit, and we prove the time optimality of this protocol. Then, for weak fairness, we show that a space optimal (semi-uniform) solution cannot converge faster than in Ω(2^n) time (non-null transitions). This result, together with the time complexity analysis of an already known space optimal protocol, shows that it is also optimal in time (given the optimal space constrains).
Type de document :
Communication dans un congrès
20th International Conference on Principles of Distributed Systems, OPODIS 2016, Dec 2016, Madrid, Spain. 20th International Conference on Principles of Distributed Systems, OPODIS 2015
Liste complète des métadonnées

https://hal.inria.fr/hal-01399797
Contributeur : Janna Burman <>
Soumis le : lundi 21 novembre 2016 - 18:44:44
Dernière modification le : mardi 24 avril 2018 - 13:51:04
Document(s) archivé(s) le : mardi 21 mars 2017 - 02:20:39

Fichiers

countingPP_time.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01399797, version 1
  • ARXIV : 1611.07238

Citation

James Aspnes, Joffroy Beauquier, Janna Burman, Devan Sohier. Time and Space Optimal Counting in Population Protocols. 20th International Conference on Principles of Distributed Systems, OPODIS 2016, Dec 2016, Madrid, Spain. 20th International Conference on Principles of Distributed Systems, OPODIS 2015. 〈hal-01399797〉

Partager

Métriques

Consultations de la notice

495

Téléchargements de fichiers

51