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. Simulating population protocols in sub-constant time per interaction
 
Options

Simulating population protocols in sub-constant time per interaction

Publikationstyp
Conference Paper
Date Issued
2020
Sprache
English
Author(s)
Berenbrink, Petra  
Hammer, David  
Kaaser, Dominik 
Meyer, Ulrich  
Penschuck, Manuel  
Tran, Hung  
TORE-URI
http://hdl.handle.net/11420/15137
First published in
Leibniz international proceedings in informatics (LIPIcs)  
Number in series
173
Article Number
16
Citation
28th Annual European Symposium on Algorithms : ESA 2020, September 7-9, 2020, Pisa, Italy (virtual conference). - (Leibniz International Proceedings in Informatics, LIPIcs ; vol. 173). - Art. no. 16 (2020)
Contribution to Conference
28th Annual European Symposium on Algorithms, ESA 2020  
Publisher DOI
10.4230/LIPIcs.ESA.2020.16
Scopus ID
2-s2.0-85092442374
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH
We consider the efficient simulation of population protocols. In the population model, we are given a system of n agents modeled as identical finite-state machines. In each step, two agents are selected uniformly at random to interact by updating their states according to a common transition function. We empirically and analytically analyze two classes of simulators for this model. First, we consider sequential simulators executing one interaction after the other. Key to the performance of these simulators is the data structure storing the agents’ states. For our analysis, we consider plain arrays, binary search trees, and a novel Dynamic Alias Table data structure. Secondly, we consider batch processing to efficiently update the states of multiple independent agents in one step. For many protocols considered in literature, our simulator requires amortized sub-constant time per interaction and is fast in practice: given a fixed time budget, the implementation of our batched simulator is able to simulate population protocols several orders of magnitude larger compared to the sequential competitors, and can carry out 250 interactions among the same number of agents in less than 400 s.
Subjects
Dynamic Alias Table
Population Protocols
Random Sampling
Simulation
DDC Class
004: Informatik
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