The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Neste artigo, consideramos um problema de bipartição uniforme em um modelo de protocolo populacional. O objetivo do problema da bipartição uniforme é dividir uma população em dois grupos do mesmo tamanho. Estudamos o problema sob justiça global com várias suposições: 1) uma população com ou sem estação base, 2) protocolos simétricos ou assimétricos e 3) estados iniciais designados ou arbitrários. Como resultado, esclarecemos completamente a solubilidade do problema da bipartição uniforme sob justiça global e, se for solucionável, mostramos os limites superiores e inferiores rígidos do número de estados.
Hiroto YASUMI
Nara Institute of Science and Technology
Fukuhito OOSHITA
Nara Institute of Science and Technology
Ken'ichi YAMAGUCHI
National Institute of Technology, Nara College
Michiko INOUE
Nara Institute of Science and Technology
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Hiroto YASUMI, Fukuhito OOSHITA, Ken'ichi YAMAGUCHI, Michiko INOUE, "Space-Optimal Population Protocols for Uniform Bipartition Under Global Fairness" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 3, pp. 454-463, March 2019, doi: 10.1587/transinf.2018FCP0009.
Abstract: 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 global fairness with various assumptions: 1) a population with or without a base station, 2) symmetric or asymmetric protocols, and 3) designated or arbitrary initial states. As a result, we completely clarify solvability of the uniform bipartition problem under global fairness and, if solvable, show the tight upper and lower bounds on the number of states.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018FCP0009/_p
Copiar
@ARTICLE{e102-d_3_454,
author={Hiroto YASUMI, Fukuhito OOSHITA, Ken'ichi YAMAGUCHI, Michiko INOUE, },
journal={IEICE TRANSACTIONS on Information},
title={Space-Optimal Population Protocols for Uniform Bipartition Under Global Fairness},
year={2019},
volume={E102-D},
number={3},
pages={454-463},
abstract={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 global fairness with various assumptions: 1) a population with or without a base station, 2) symmetric or asymmetric protocols, and 3) designated or arbitrary initial states. As a result, we completely clarify solvability of the uniform bipartition problem under global fairness and, if solvable, show the tight upper and lower bounds on the number of states.},
keywords={},
doi={10.1587/transinf.2018FCP0009},
ISSN={1745-1361},
month={March},}
Copiar
TY - JOUR
TI - Space-Optimal Population Protocols for Uniform Bipartition Under Global Fairness
T2 - IEICE TRANSACTIONS on Information
SP - 454
EP - 463
AU - Hiroto YASUMI
AU - Fukuhito OOSHITA
AU - Ken'ichi YAMAGUCHI
AU - Michiko INOUE
PY - 2019
DO - 10.1587/transinf.2018FCP0009
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2019
AB - 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 global fairness with various assumptions: 1) a population with or without a base station, 2) symmetric or asymmetric protocols, and 3) designated or arbitrary initial states. As a result, we completely clarify solvability of the uniform bipartition problem under global fairness and, if solvable, show the tight upper and lower bounds on the number of states.
ER -