Options
On counting the population size
Publikationstyp
Conference Paper
Date Issued
2019-07
Sprache
English
Author(s)
Start Page
43
End Page
52
Citation
Proceedings of the 38th ACM Symposium on Principles of Distributed Computing: 43-52 (2019)
Contribution to Conference
Publisher DOI
ArXiv ID
Publisher
Association for Computing Machinery
ISBN
978-1-4503-6670-0
978-1-4503-6217-7
We consider the problem of counting the population size in the population model. In this model, we are given a distributed system of n identical agents which interact in pairs with the goal to solve a common task. In each time step, the two interacting agents are selected uniformly at random. In this paper, we consider so-called uniform protocols, where the actions of two agents upon an interaction may not depend on the population size n. We present two population protocols to count the size of the population: protocol Approximate, which computes with high probability either [log n] or [log n], and protocol CountExact, which computes the exact population size in optimal O(log n) interactions, using Õ (n) states. Both protocols can also be converted to stable protocols that give a correct result with probability 1 by using an additional multiplicative factor of O(log n) states.
Subjects
population protocols | population size | counting | Computer Science - Distributed | Parallel | Cluster Computing
DDC Class
600: Technology