License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.16
URN: urn:nbn:de:0030-drops-128827
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12882/
Go to the corresponding LIPIcs Volume Portal

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

Simulating Population Protocols in Sub-Constant Time per Interaction

pdf-format:
LIPIcs-ESA-2020-16.pdf (0.7 MB)

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 2^50 interactions among the same number of agents in less than 400s.

BibTeX - Entry

@InProceedings{berenbrink_et_al:LIPIcs:2020:12882,
  author =	{Petra Berenbrink and David Hammer and Dominik Kaaser and Ulrich Meyer and Manuel Penschuck and Hung Tran},
  title =	{{Simulating Population Protocols in Sub-Constant Time per Interaction}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{16:1--16:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12882},
  URN =		{urn:nbn:de:0030-drops-128827},
  doi =		{10.4230/LIPIcs.ESA.2020.16},
  annote =	{Keywords: Population Protocols, Simulation, Random Sampling, Dynamic Alias Table}
}

Keywords: Population Protocols, Simulation, Random Sampling, Dynamic Alias Table
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020
Supplementary Material: Implementations and data: https://ae.cs.uni-frankfurt.de/r/p/pps.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI