Skip to main content

Research Repository

Advanced Search

Time-space trade-offs in population protocols for the majority problem

Berenbrink, Petra; Elsässer, Robert; Friedetzky, Tom; Kaaser, Dominik; Kling, Peter; Radzik, Tomasz

Time-space trade-offs in population protocols for the majority problem Thumbnail


Authors

Petra Berenbrink

Robert Elsässer

Dominik Kaaser

Peter Kling

Tomasz Radzik



Abstract

Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of n identical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion when each agent has one of two opinions. Agents communicate in pairwise interactions with randomly assigned communication partners. Quality is measured in two ways: the number of interactions to complete the task and the number of states per agent. We present protocols for the majority problem that allow for a trade-off between these two measures. Compared to the only other trade-off result (Alistarh et al. in Proceedings of the 2015 ACM symposium on principles of distributed computing, Donostia-San Sebastián, 2015), we improve the number of interactions by almost a linear factor. Furthermore, our protocols can be made uniform (working correctly without any information on the population size n), yielding the first uniform majority protocols that stabilize in a subquadratic number of interactions.

Citation

Berenbrink, P., Elsässer, R., Friedetzky, T., Kaaser, D., Kling, P., & Radzik, T. (2021). Time-space trade-offs in population protocols for the majority problem. Distributed Computing, 34(2), 91-111. https://doi.org/10.1007/s00446-020-00385-0

Journal Article Type Article
Acceptance Date Jul 22, 2020
Online Publication Date Aug 5, 2020
Publication Date 2021-04
Deposit Date Aug 12, 2020
Publicly Available Date Aug 12, 2020
Journal Distributed Computing
Print ISSN 0178-2770
Electronic ISSN 1432-0452
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 34
Issue 2
Pages 91-111
DOI https://doi.org/10.1007/s00446-020-00385-0

Files

Published Journal Article (Advance online version) (538 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
Advance online version This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.





You might also like



Downloadable Citations