Document Open Access Logo

Constant-Space Population Protocols for Uniform Bipartition

Authors Hiroto Yasumi, Fukuhito Ooshita, Ken'ichi Yamaguchi, Michiko Inoue

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2017.19.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

Hiroto Yasumi
Fukuhito Ooshita
Ken'ichi Yamaguchi
Michiko Inoue

Cite As Get BibTex

Hiroto Yasumi, Fukuhito Ooshita, Ken'ichi Yamaguchi, and Michiko Inoue. Constant-Space Population Protocols for Uniform Bipartition. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.OPODIS.2017.19

Abstract

In this paper, we consider a uniform bipartition problem in a population protocol model. The goal of the uniform bipartition problem is to divide a population into two groups of the same size. We study the problem under various assumptions: 1) a population with or without a base station, 2) weak or global fairness, 3) symmetric or asymmetric protocols, and 4) designated or arbitrary initial states. As a result, we completely clarify constant-space solvability of the uniform bipartition problem and, if solvable, propose space-optimal protocols.

Subject Classification

Keywords
  • population protocol
  • uniform bipartition
  • distributed protocol

Metrics

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

References

  1. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L Rivest. Time-space trade-offs in population protocols. In Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2560-2579, 2017. Google Scholar
  2. Dan Alistarh and Rati Gelashvili. Polylogarithmic-time leader election in population protocols. In Proc. of the 42nd International Colloquium on Automata, Languages, and Programming, pages 479-491, 2015. Google Scholar
  3. Dan Alistarh, Rati Gelashvili, and Milan Vojnović. Fast and exact majority in population protocols. In Proc. of the 2015 ACM Symposium on Principles of Distributed Computing, pages 47-56, 2015. Google Scholar
  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. Google Scholar
  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. Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing, 21(2):87-102, 2008. Google Scholar
  7. Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, 2007. Google Scholar
  8. Dana Angluin, James Aspnes, Michael J Fischer, and Hong Jiang. Self-stabilizing population protocols. In International Conference On Principles Of Distributed Systems, pages 103-117. Springer, 2005. Google Scholar
  9. James Aspnes, Joffroy Beauquier, Janna Burman, and Devan Sohier. Time and space optimal counting in population protocols. In Proc. of International Conference on Principles of Distributed Systems, pages 13:1-13:17, 2016. Google Scholar
  10. James Aspnes and Eric Ruppert. An introduction to population protocols. In Middleware for Network Eccentric and Mobile Applications, pages 97-120, 2009. Google Scholar
  11. Joffroy Beauquier, Janna Burman, Simon Claviere, and Devan Sohier. Space-optimal counting in population protocols. In Proc. of International Symposium on Distributed Computing, pages 631-646, 2015. Google Scholar
  12. Joffroy Beauquier, Julien Clement, Stephane Messika, Laurent Rosaz, and Brigitte Rozoy. Self-stabilizing counting in mobile sensor networks with a base station. In Proc. of International Symposium on Distributed Computing, pages 63-76, 2007. Google Scholar
  13. Amanda Belleville, David Doty, and David Soloveichik. Hardness of computing and approximating predicates and functions with leaderless population protocols. In Proc. of 44th International Colloquium on Automata, Languages, and Programming, pages 141:1-141:14, 2017. Google Scholar
  14. Olivier Bournez, Jérémie Chalopin, Johanne Cohen, and Xavier Koegler. Playing with population protocols. In Proc. of the International Workshop on the Complexity of Simple Programs, pages 3-15, 2008. Google Scholar
  15. Shukai Cai, Taisuke Izumi, and Koichi Wada. How to prove impossibility under global fairness: On space complexity of self-stabilizing leader election on a population protocol model. Theory of Computing Systems, 50(3):433-445, 2012. Google Scholar
  16. Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Eric Ruppert. When birds die: Making population protocols fault-tolerant. Distributed Computing in Sensor Systems, pages 51-66, 2006. Google Scholar
  17. David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. In Proc. of International Symposium on Distributed Computing, pages 602-616, 2015. Google Scholar
  18. Leszek Gasieniec, David Hamilton, Russell Martin, Paul G Spirakis, and Grzegorz Stachowiak. Deterministic population protocols for exact majority and plurality. In Proc. of International Conference on Principles of Distributed Systems, pages 14:1-14:14, 2016. Google Scholar
  19. Taisuke Izumi. On space and time complexity of loosely-stabilizing leader election. In Proc. of International Colloquium on Structural Information and Communication Complexity, pages 299-312, 2015. Google Scholar
  20. Tomoko Izumi, Keigo Kinpara, Taisuke Izumi, and Koichi Wada. Space-efficient self-stabilizing counting population protocols on mobile sensor networks. Theoretical Computer Science, 552:99-108, 2014. Google Scholar
  21. Anissa Lamani and Masafumi Yamashita. Realization of periodic functions by self-stabilizing population protocols with synchronous handshakes. In Proc. of International Conference on Theory and Practice of Natural Computing, pages 21-33, 2016. Google Scholar
  22. Satoshi Murata, Akihiko Konagaya, Satoshi Kobayashi, Hirohide Saito, and Masami Hagiya. Molecular robotics: A new paradigm for artifacts. New Generation Computing, 31(1):27-45, 2013. Google Scholar
  23. Yuichi Sudo, Toshimitsu Masuzawa, Ajoy K Datta, and Lawrence L Larmore. The same speed timer in population protocols. In Proc. of International Conference on Distributed Computing Systems, pages 252-261, 2016. Google Scholar
  24. Yuichi Sudo, Junya Nakamura, Yukiko Yamauchi, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely-stabilizing leader election in a population protocol model. Theoretical Computer Science, 444:100-112, 2012. Google Scholar
  25. Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely-stabilizing leader election on arbitrary graphs in population protocols without identifiers nor random numbers. In Proc. of International Conference on Principles of Distributed Systems, pages 14:1-14:16, 2015. Google Scholar
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 About DROPS Imprint Privacy Contact