Document

**Published in:** LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

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.

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)

Copy BibTex To Clipboard

@InProceedings{yasumi_et_al:LIPIcs.OPODIS.2021.13, author = {Yasumi, Hiroto and Ooshita, Fukuhito and Inoue, Michiko}, title = {{Population Protocols for Graph Class Identification Problems}}, booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)}, pages = {13:1--13:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-219-8}, ISSN = {1868-8969}, year = {2022}, volume = {217}, editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.13}, URN = {urn:nbn:de:0030-drops-157885}, doi = {10.4230/LIPIcs.OPODIS.2021.13}, annote = {Keywords: population protocol, graph class identification, distributed protocol} }

Document

**Published in:** LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

In this paper, we focus on the uniform bipartition problem in the population protocol model. This problem aims to divide a population into two groups of equal size. In particular, we consider the problem in the context of arbitrary communication graphs. As a result, we investigate the solvability of the uniform bipartition problem with arbitrary communication graphs when agents in the population have designated initial states, under various assumptions such as the existence of a base station, symmetry of the protocol, and fairness of the execution. When the problem is solvable, we present protocols for uniform bipartition. When global fairness is assumed, the space complexity of our solutions is tight.

Hiroto Yasumi, Fukuhito Ooshita, Michiko Inoue, and Sébastien Tixeuil. Uniform Bipartition in the Population Protocol Model with Arbitrary Communication Graphs. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{yasumi_et_al:LIPIcs.OPODIS.2020.33, author = {Yasumi, Hiroto and Ooshita, Fukuhito and Inoue, Michiko and Tixeuil, S\'{e}bastien}, title = {{Uniform Bipartition in the Population Protocol Model with Arbitrary Communication Graphs}}, booktitle = {24th International Conference on Principles of Distributed Systems (OPODIS 2020)}, pages = {33:1--33:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-176-4}, ISSN = {1868-8969}, year = {2021}, volume = {184}, editor = {Bramas, Quentin and Oshman, Rotem and Romano, Paolo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.33}, URN = {urn:nbn:de:0030-drops-135182}, doi = {10.4230/LIPIcs.OPODIS.2020.33}, annote = {Keywords: population protocol, uniform bipartition, distributed protocol} }

Document

**Published in:** LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

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).

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)

Copy BibTex To Clipboard

@InProceedings{yasumi_et_al:LIPIcs.OPODIS.2019.8, author = {Yasumi, Hiroto and Ooshita, Fukuhito and Inoue, Michiko}, title = {{Uniform Partition in Population Protocol Model Under Weak Fairness}}, booktitle = {23rd International Conference on Principles of Distributed Systems (OPODIS 2019)}, pages = {8:1--8:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-133-7}, ISSN = {1868-8969}, year = {2020}, volume = {153}, editor = {Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.8}, URN = {urn:nbn:de:0030-drops-117947}, doi = {10.4230/LIPIcs.OPODIS.2019.8}, annote = {Keywords: population protocol, uniform k-partition, distributed protocol} }

Document

**Published in:** LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

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.

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)

Copy BibTex To Clipboard

@InProceedings{yasumi_et_al:LIPIcs.OPODIS.2017.19, author = {Yasumi, Hiroto and Ooshita, Fukuhito and Yamaguchi, Ken'ichi and Inoue, Michiko}, title = {{Constant-Space Population Protocols for Uniform Bipartition}}, booktitle = {21st International Conference on Principles of Distributed Systems (OPODIS 2017)}, pages = {19:1--19:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-061-3}, ISSN = {1868-8969}, year = {2018}, volume = {95}, editor = {Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.19}, URN = {urn:nbn:de:0030-drops-86482}, doi = {10.4230/LIPIcs.OPODIS.2017.19}, annote = {Keywords: population protocol, uniform bipartition, distributed protocol} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail