Simulating population protocols in sub-constant time per interaction

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

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

8 Downloads (Pure)

Abstrakt

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.

OriginalsprogEngelsk
Titel28th Annual European Symposium on Algorithms, ESA 2020
RedaktørerFabrizio Grandoni, Grzegorz Herman, Peter Sanders
Antal sider22
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato1. aug. 2020
Artikelnummer16
ISBN (Elektronisk)9783959771627
DOI
StatusUdgivet - 1. aug. 2020
Begivenhed28th Annual European Symposium on Algorithms, ESA 2020 - Virtual, Pisa, Italien
Varighed: 7. sep. 20209. sep. 2020

Konference

Konference28th Annual European Symposium on Algorithms, ESA 2020
Land/OmrådeItalien
ByVirtual, Pisa
Periode07/09/202009/09/2020
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind173
ISSN1868-8969

Fingeraftryk

Dyk ned i forskningsemnerne om 'Simulating population protocols in sub-constant time per interaction'. Sammen danner de et unikt fingeraftryk.

Citationsformater