Document Open Access Logo

Population Protocols for Graph Class Identification Problems

Authors Hiroto Yasumi, Fukuhito Ooshita, Michiko Inoue

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2021.13.pdf
  • Filesize: 0.7 MB
  • 19 pages

Document Identifiers

Author Details

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

Funding

This work was supported by JSPS KAKENHI Grant Numbers 18K11167, 20H04140, 20J21849, and JST SICORP Grant Number JPMJSC1806.

Cite As Get BibTex

Hiroto Yasumi, Fukuhito Ooshita, and Michiko Inoue. Population Protocols for Graph Class Identification Problems. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.OPODIS.2021.13

Abstract

In this paper, we focus on graph class identification problems in the population protocol model. A graph class identification problem aims to decide whether a given communication graph is in the desired class (e.g. whether the given communication graph is a ring graph). Angluin et al. proposed graph class identification protocols with directed graphs and designated initial states under global fairness [Angluin et al., DCOSS2005]. We consider graph class identification problems for undirected graphs on various assumptions such as initial states of agents, fairness of the execution, and initial knowledge of agents. In particular, we focus on lines, rings, k-regular graphs, stars, trees, and bipartite graphs. With designated initial states, we propose graph class identification protocols for k-regular graphs and trees under global fairness, and propose a graph class identification protocol for stars under weak fairness. Moreover, we show that, even if agents know the number of agents n, there is no graph class identification protocol for lines, rings, k-regular graphs, trees, or bipartite graphs under weak fairness, and no graph class identification for lines, rings, k-regular graphs, stars, trees, or bipartite graphs with arbitrary initial states.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Concurrent algorithms
Keywords
  • population protocol
  • graph class identification
  • distributed protocol

Metrics

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

Related Versions

References

  1. Dan Alistarh and Rati Gelashvili. Polylogarithmic-time leader election in population protocols. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, pages 479-491, 2015. Google Scholar
  2. Dan Alistarh, Rati Gelashvili, and Joel Rybicki. Fast graphical population protocols. arXiv preprint, 2021. URL: http://arxiv.org/abs/2102.08808.
  3. Dana Angluin, James Aspnes, Melody Chan, Michael J Fischer, Hong Jiang, and René Peralta. Stably computable properties of network graphs. In Proceedings of International Conference on Distributed Computing in Sensor Systems, pages 63-74, 2005. 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. A simple population protocol for fast robust approximate majority. Distributed Computing, 21(2):87-102, 2008. Google Scholar
  6. Dana Angluin, James Aspnes, Michael J Fischer, and Hong Jiang. Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems (TAAS), 3(4):13, 2008. Google Scholar
  7. James Aspnes, Joffroy Beauquier, Janna Burman, and Devan Sohier. Time and space optimal counting in population protocols. In Proceedings of International Conference on Principles of Distributed Systems, pages 13:1-13:17, 2016. Google Scholar
  8. Joffroy Beauquier, Janna Burman, Simon Claviere, and Devan Sohier. Space-optimal counting in population protocols. In Proceedings of International Symposium on Distributed Computing, pages 631-646, 2015. Google Scholar
  9. Joffroy Beauquier, Julien Clement, Stephane Messika, Laurent Rosaz, and Brigitte Rozoy. Self-stabilizing counting in mobile sensor networks with a base station. In Proceedings of International Symposium on Distributed Computing, pages 63-76, 2007. Google Scholar
  10. Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. Time-space trade-offs in population protocols for the majority problem. Distributed Computing, pages 1-21, 2020. Google Scholar
  11. Petra Berenbrink, George Giakkoupis, and Peter Kling. Optimal time and space leader election in population protocols. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 119-129, 2020. Google Scholar
  12. Petra Berenbrink, Dominik Kaaser, and Tomasz Radzik. On counting the population size. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 43-52, 2019. Google Scholar
  13. Olivier Bournez, Jérémie Chalopin, Johanne Cohen, Xavier Koegler, and Mikael Rabie. Population protocols that correspond to symmetric games. International Journal of Unconventional Computing, 9, 2013. Google Scholar
  14. 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
  15. Ioannis Chatzigiannakis, Othon Michail, and Paul G. Spirakis. Stably decidable graph languages by mediated population protocols. In Stabilization, Safety, and Security of Distributed Systems - 12th International Symposium, SSS, volume 6366 of Lecture Notes in Computer Science, pages 252-266. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-16023-3_21.
  16. Hsueh-Ping Chen and Ho-Lin Chen. Self-stabilizing leader election. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 53-59, 2019. Google Scholar
  17. Hsueh-Ping Chen and Ho-Lin Chen. Self-stabilizing leader election in regular graphs. In Proceedings of the 39th Symposium on Principles of Distributed Computing, pages 210-217, 2020. Google Scholar
  18. David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. Distributed Computing, 31(4):257-271, 2018. Google Scholar
  19. Michael Fischer and Hong Jiang. Self-stabilizing leader election in networks of finite-state anonymous agents. In International Conference On Principles Of Distributed Systems, pages 395-409. Springer, 2006. Google Scholar
  20. Leszek Gąsieniec, David Hamilton, Russell Martin, Paul G Spirakis, and Grzegorz Stachowiak. Deterministic population protocols for exact majority and plurality. In Proceedings of International Conference on Principles of Distributed Systems, pages 14:1-14:14, 2016. Google Scholar
  21. Leszek Gąsieniec, Grzegorz Stachowiak, and Przemyslaw Uznanski. Almost logarithmic-time space optimal leader election in population protocols. In The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, pages 93-102. ACM, 2019. Google Scholar
  22. 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
  23. Othon Michail and Paul G Spirakis. Simple and efficient local codes for distributed stable network construction. Distributed Computing, 29(3):207-237, 2016. Google Scholar
  24. 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
  25. Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, and Toshimitsu Masuzawa. Self-stabilizing population protocols with global knowledge. IEEE Transactions on Parallel and Distributed Systems, 2021. Google Scholar
  26. Hiroto Yasumi, Fukuhito Ooshita, and Michiko Inoue. Population protocols for graph class identification problems, 2021. URL: http://arxiv.org/abs/2111.05111.
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