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.2019.8
URN: urn:nbn:de:0030-drops-117947
URL: https://drops.dagstuhl.de/opus/volltexte/2020/11794/
Go to the corresponding LIPIcs Volume Portal


Yasumi, Hiroto ; Ooshita, Fukuhito ; Inoue, Michiko

Uniform Partition in Population Protocol Model Under Weak Fairness

pdf-format:
LIPIcs-OPODIS-2019-8.pdf (0.4 MB)


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

BibTeX - Entry

@InProceedings{yasumi_et_al:LIPIcs:2020:11794,
  author =	{Hiroto Yasumi and Fukuhito Ooshita and Michiko Inoue},
  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 =	{Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11794},
  URN =		{urn:nbn:de:0030-drops-117947},
  doi =		{10.4230/LIPIcs.OPODIS.2019.8},
  annote =	{Keywords: population protocol, uniform k-partition, distributed protocol}
}

Keywords: population protocol, uniform k-partition, distributed protocol
Collection: 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
Issue Date: 2020
Date of publication: 11.02.2020


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