Space-Optimal Counting in Population Protocols [Extended Version]

Abstract : In this paper, we study the fundamental problem of counting, which consists in computing the size of a system. We consider the distributed communication model of population protocols of finite state, anonymous and asynchronous mobile devices (agents) communicating in pairs (according to a fairness condition). This work significantly improves the previous results known for counting in this model, in terms of (exact) space complexity. We present, prove correct and analyze the time complexities of the first space-optimal protocols solving the problem for two classical types of fairness, global and weak. Both protocols require no initialization of the counted agents. The protocol designed for global fairness, surprisingly, uses only one bit of memory (two states) per counted agent. The protocol, functioning under weak fairness, requires the necessary log P bits (P states, per counted agent) to be able to count up to P agents. Interestingly, this protocol exploits the intriguing Gros sequence of natural numbers, which is also used in the solutions to the Chinese Rings and the Hanoi Towers puzzles. The convergence time of the protocol is exponential, but we prove that this is necessary (within a constant factor) for obtaining a space-optimal and semi-uniform solution.
Type de document :
Communication dans un congrès
Distributed Computing - 29th International Symposium, DISC 2015, Oct 2015, Tokyo, Japan. 2015
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger
Contributeur : Janna Burman <>
Soumis le : dimanche 10 juillet 2016 - 16:02:34
Dernière modification le : mardi 24 avril 2018 - 13:38:18


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


  • HAL Id : hal-01169634, version 4


Joffroy Beauquier, Janna Burman, Simon Clavière, Devan Sohier. Space-Optimal Counting in Population Protocols [Extended Version]. Distributed Computing - 29th International Symposium, DISC 2015, Oct 2015, Tokyo, Japan. 2015. 〈hal-01169634v4〉



Consultations de la notice


Téléchargements de fichiers