Document Open Access Logo

A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States

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

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.10.pdf
  • Filesize: 497 kB
  • 18 pages

Document Identifiers

Author Details

Petra Berenbrink
  • Universität Hamburg, Hamburg, Germany
Robert Elsässer
  • University of Salzburg, Salzburg, Austria
Tom Friedetzky
  • Durham University, Durham, U.K.
Dominik Kaaser
  • Universität Hamburg, Hamburg, Germany
Peter Kling
  • Universität Hamburg, Hamburg, Germany
Tomasz Radzik
  • King’s College London, London, U.K.

Funding

  • Elsässer, Robert: Robert Elsässer’s work has been supported by grant no. P 27613 of the Austrian Science Fund (FWF), "Distributed Voting in Large Networks".
  • Radzik, Tomasz: Tomasz Radzik’s work has been supported by EPSRC grant EP/M005038/1, "Randomized algorithms for computer networks".

Cite AsGet BibTex

Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.10

Abstract

A population protocol is a sequence of pairwise interactions of n agents. During one interaction, two randomly selected agents update their states by applying a deterministic transition function. The goal is to stabilize the system at a desired output property. The main performance objectives in designing such protocols are small number of states per agent and fast stabilization time. We present a fast population protocol for the exact-majority problem, which uses Theta(log n) states (per agent) and stabilizes in O(log^{5/3} n) parallel time (i.e., in O(n log^{5/3} n) interactions) in expectation and with high probability. Alistarh et al. [SODA 2018] showed that exact-majority protocols which stabilize in expected O(n^{1-Omega(1)}) parallel time and have the properties of monotonicity and output dominance require Omega(log n) states. Note that the properties mentioned above are satisfied by all known population protocols for exact majority, including ours. They also showed an O(log^2 n)-time exact-majority protocol with O(log n) states, which, prior to our work, was the fastest exact-majority protocol with polylogarithmic number of states. The standard design framework for majority protocols is based on O(log n) phases and requires that all agents are well synchronized within each phase, leading naturally to upper bounds of the order of log^2 n because of Theta(log n) synchronization time per phase. We show how this framework can be tightened with weak synchronization to break the O(log^2 n) upper bound of previous protocols.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • Population Protocols
  • Randomized Algorithms
  • Majority

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. Time-space trade-offs in population protocols. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2560-2579. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.169.
  2. Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2221-2239, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.144.
  3. Dan Alistarh, Rati Gelashvili, and Milan Vojnovic. Fast and exact majority in population protocols. In Chryssis Georgiou and Paul G. Spirakis, editors, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, pages 47-56. ACM, 2015. URL: http://dl.acm.org/citation.cfm?id=2767386, URL: http://dx.doi.org/10.1145/2767386.2767429.
  4. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235-253, 2006. URL: http://dx.doi.org/10.1007/s00446-005-0138-3.
  5. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183-199, 2008. Google Scholar
  6. James Aspnes and Eric Ruppert. An introduction to population protocols. In Benoît Garbinato, Hugo Miranda, and Luís Rodrigues, editors, Middleware for Network Eccentric and Mobile Applications, pages 97-120. Springer-Verlag, 2009. Google Scholar
  7. Florence Bénézit, Patrick Thiran, and Martin Vetterli. Interval consensus: From quantized gossip to voting. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2009, 19-24 April 2009, Taipei, Taiwan, pages 3661-3664. IEEE, 2009. URL: http://dx.doi.org/10.1109/ICASSP.2009.4960420.
  8. Petra Berenbrink, Robert Elässser, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. Majority &stabilization in population protocols. Unpublished manuscript, available on arXiv, May 2018. Google Scholar
  9. Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. A population protocol for exact majority with O(log^5/3 n) stabilization time and asymptotically optimal number of states. Unpublished manuscript, available on arXiv, May 2018. URL: http://arxiv.org/abs/1805.05157.
  10. Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, and Chris Wastell. Plurality consensus via shuffling: Lessons learned from load balancing. CoRR, abs/1602.01342, 2016. URL: http://arxiv.org/abs/1602.01342.
  11. Andreas Bilke, Colin Cooper, Robert Elsässer, and Tomasz Radzik. Brief announcement: Population protocols for leader election and exact majority with O(log^2 n) states and O(log^2 n) convergence time. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 451-453. ACM, 2017. Full version available at arXiv:1705.01146. URL: http://dx.doi.org/10.1145/3087801.3087858.
  12. Moez Draief and Milan Vojnovic. Convergence speed of binary interval consensus. In INFOCOM 2010. 29th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 15-19 March 2010, San Diego, CA, USA, pages 1792-1800. IEEE, 2010. URL: http://dx.doi.org/10.1109/INFCOM.2010.5461999.
  13. Leszek Gasieniec and Grzegorz Stachowiak. Fast space optimal leader election in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2653-2667, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.169.
  14. Leszek Gasieniec, Grzegorz Stachowiak, and Przemyslaw Uznanski. Almost logarithmic-time space optimal leader election in population protocols. CoRR, abs/1802.06867, 2018. URL: http://arxiv.org/abs/1802.06867.
  15. Mohsen Ghaffari and Merav Parter. A polylogarithmic gossip algorithm for plurality consensus. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing PODC, pages 117-126, 2016. Google Scholar
  16. A. Kosowski and P. Uznański. Population Protocols Are Fast. ArXiv e-prints, 2018. URL: http://arxiv.org/abs/1802.06872v2.
  17. George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, and Paul G. Spirakis. Determining majority in networks with local interactions and very small local memory. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming, volume 8572 of Lecture Notes in Computer Science, pages 871-882. Springer Berlin Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_72.
  18. Thomas Sauerwald and He Sun. Tight bounds for randomized load balancing on arbitrary network topologies. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 341-350. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.86.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact