License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2020.33
URN: urn:nbn:de:0030-drops-135182
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13518/
Go to the corresponding LIPIcs Volume Portal

Yasumi, Hiroto ; Ooshita, Fukuhito ; Inoue, Michiko ; Tixeuil, Sébastien

Uniform Bipartition in the Population Protocol Model with Arbitrary Communication Graphs

pdf-format:
LIPIcs-OPODIS-2020-33.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{yasumi_et_al:LIPIcs:2021:13518,
  author =	{Hiroto Yasumi and Fukuhito Ooshita and Michiko Inoue and S{\'e}bastien Tixeuil},
  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 =	{Quentin Bramas and Rotem Oshman and Paolo Romano},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13518},
  URN =		{urn:nbn:de:0030-drops-135182},
  doi =		{10.4230/LIPIcs.OPODIS.2020.33},
  annote =	{Keywords: population protocol, uniform bipartition, distributed protocol}
}

Keywords: population protocol, uniform bipartition, distributed protocol
Collection: 24th International Conference on Principles of Distributed Systems (OPODIS 2020)
Issue Date: 2021
Date of publication: 25.01.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI