TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publication References
  4. On counting the population size
 
Options

On counting the population size

Publikationstyp
Conference Paper
Date Issued
2019-07
Sprache
English
Author(s)
Berenbrink, Petra  
Kaaser, Dominik 
Data Engineering E-19  
Radzik, Tomasz  
TORE-URI
https://hdl.handle.net/11420/54455
Start Page
43
End Page
52
Citation
Proceedings of the 38th ACM Symposium on Principles of Distributed Computing: 43-52 (2019)
Contribution to Conference
38th ACM Symposium on Principles of Distributed Computing 2019  
Publisher DOI
10.1145/3293611.333163
ArXiv ID
1905.11962v1
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
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback