Simulating population protocols in sub-constant time per interaction

Petra Berenbrink, David Hammer, Dominik Kaaser, Ulrich Meyer, Manuel Penschuck, Hung Tran

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

10 Downloads (Pure)

Abstract

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.

Original languageEnglish
Title of host publication28th Annual European Symposium on Algorithms, ESA 2020
EditorsFabrizio Grandoni, Grzegorz Herman, Peter Sanders
Number of pages22
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date1. Aug 2020
Article number16
ISBN (Electronic)9783959771627
DOIs
Publication statusPublished - 1. Aug 2020
Event28th Annual European Symposium on Algorithms, ESA 2020 - Virtual, Pisa, Italy
Duration: 7. Sep 20209. Sep 2020

Conference

Conference28th Annual European Symposium on Algorithms, ESA 2020
Country/TerritoryItaly
CityVirtual, Pisa
Period07/09/202009/09/2020
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume173
ISSN1868-8969

Keywords

  • Dynamic Alias Table
  • Population Protocols
  • Random Sampling
  • Simulation

Fingerprint

Dive into the research topics of 'Simulating population protocols in sub-constant time per interaction'. Together they form a unique fingerprint.

Cite this