Uniform Partition in Population Protocol Model Under Weak Fairness

Authors Hiroto Yasumi, Fukuhito Ooshita, Michiko Inoue



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.8.pdf
  • Filesize: 434 kB
  • 16 pages

Document Identifiers

Author Details

Hiroto Yasumi
  • Nara Institute of Science and Technology, Ikoma city, Nara, Japan
Fukuhito Ooshita
  • Nara Institute of Science and Technology, Ikoma city, Nara, Japan
Michiko Inoue
  • Nara Institute of Science and Technology, Ikoma city, Nara, Japan

Cite AsGet BibTex

Hiroto Yasumi, Fukuhito Ooshita, and Michiko Inoue. Uniform Partition in Population Protocol Model Under Weak Fairness. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.8

Abstract

We focus on a uniform partition problem in a population protocol model. The uniform partition problem aims to divide a population into k groups of the same size, where k is a given positive integer. In the case of k=2 (called uniform bipartition), a previous work clarified space complexity under various assumptions: 1) an initialized base station (BS) or no BS, 2) weak or global fairness, 3) designated or arbitrary initial states of agents, and 4) symmetric or asymmetric protocols, except for the setting that agents execute a protocol from arbitrary initial states under weak fairness in the model with an initialized base station. In this paper, we clarify the space complexity for this remaining setting. In this setting, we prove that P states are necessary and sufficient to realize asymmetric protocols, and that P+1 states are necessary and sufficient to realize symmetric protocols, where P is the known upper bound of the number of agents. From these results and the previous work, we have clarified the solvability of the uniform bipartition for each combination of assumptions. Additionally, we newly consider an assumption on a model of a non-initialized BS and clarify solvability and space complexity in the assumption. Moreover, the results in this paper can be applied to the case that k is an arbitrary integer (called uniform k-partition).

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Concurrent algorithms
Keywords
  • population protocol
  • uniform k-partition
  • distributed protocol

Metrics

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

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, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2221-2239. SIAM, 2018. Google Scholar
  3. 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
  4. 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
  5. Dana Angluin, James Aspnes, Melody Chan, Michael J Fischer, Hong Jiang, and René Peralta. Stably computable properties of network graphs. In Proc. of International Conference on Distributed Computing in Sensor Systems, pages 63-74, 2005. Google Scholar
  6. 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
  7. 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
  8. Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, 2007. Google Scholar
  9. 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
  10. 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
  11. James Aspnes and Eric Ruppert. An introduction to population protocols. In Middleware for Network Eccentric and Mobile Applications, pages 97-120, 2009. Google Scholar
  12. 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
  13. 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
  14. Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. Simple and efficient leader election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  15. Andreas Bilke, Colin Cooper, Robert Elsaesser, and Tomasz Radzik. Population protocols for leader election and exact majority with O (log^2 n) states and O (log^2 n) convergence time. arXiv preprint arXiv:1705.01146, 2017. Google Scholar
  16. Janna Burman, Joffroy Beauquier, and Devan Sohier. Brief Announcement: Space-Optimal Naming in Population Protocols. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 479-481. ACM, 2018. Google Scholar
  17. 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
  18. 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
  19. David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. Distributed Computing, 31(4):257-271, 2018. Google Scholar
  20. 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
  21. Leszek Gasieniec, Grzegorz Stachowiak, and Przemyslaw Uznanski. Almost logarithmic-time space optimal leader election in population protocols. arXiv preprint arXiv:1802.06867, 2018. Google Scholar
  22. Leszek Gasieniec and Grzegorz Staehowiak. Fast space optimal leader election in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2653-2667. SIAM, 2018. Google Scholar
  23. 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
  24. 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
  25. 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
  26. 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
  27. Yuichi Sudo, Fukuhito Ooshita, Taisuke Izumi, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Logarithmic Expected-Time Leader Election in Population Protocol Model. arXiv preprint arXiv:1812.11309, 2018. Google Scholar
  28. Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K Datta, and Lawrence L Larmore. Loosely-Stabilizing Leader Election with Polylogarithmic Convergence Time. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  29. Tomoki Umino, Naoki Kitamura, and Taisuke Izumi. Differentiation in Population Protocols. 6th workshop on biological distributed algorithms(BDA), 2018. Google Scholar
  30. Hiroto Yasumi, Naoki Kitamura, Fukuhito Ooshita, Taisuke Izumi, and Michiko Inoue. A Population Protocol for Uniform k-partition under Global Fairness. International Journal of Networking and Computing, 9(1):97-110, 2019. Google Scholar
  31. Hiroto Yasumi, Fukuhito Ooshita, and Michiko Inoue. Uniform Partition in Population Protocol Model under Weak Fairness. arXiv preprint arXiv:1911.04678, 2019. Google Scholar
  32. Hiroto Yasumi, Fukuhito Ooshita, Ken'ichi Yamaguchi, and Michiko Inoue. Constant-space population protocols for uniform bipartition. the 21st International Conference on Principles of Distributed Systems, 2017. Google Scholar
  33. Hiroto Yasumi, Fukuhito Ooshita, Ken'ichi Yamaguchi, and Michiko Inoue. Space-optimal population protocols for uniform bipartition under global fairness. IEICE TRANSACTIONS on Information and Systems, 102(3):454-463, 2019. 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