Petra Berenbrink
Time-space trade-offs in population protocols for the majority problem
Berenbrink, Petra; Elsässer, Robert; Friedetzky, Tom; Kaaser, Dominik; Kling, Peter; Radzik, Tomasz
Authors
Robert Elsässer
Dr Tom Friedetzky tom.friedetzky@durham.ac.uk
Associate Professor
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 |
Public URL | https://durham-repository.worktribe.com/output/1294677 |
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
Infinite Balanced Allocation via Finite Capacities
(2021)
Presentation / Conference Contribution
Randomized renaming in shared memory systems
(2021)
Journal Article
Tight & Simple Load Balancing
(2019)
Presentation / Conference Contribution
A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states
(2018)
Presentation / Conference Contribution
Self-Stabilizing Balls and Bins in Batches
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search