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
Dans cet article, nous considérons un problème de bipartition uniforme dans un modèle de protocole de population. Le but du problème de la bipartition uniforme est de diviser une population en deux groupes de même taille. Nous étudions le problème sous l'angle de l'équité globale avec diverses hypothèses : 1) une population avec ou sans station de base, 2) des protocoles symétriques ou asymétriques, et 3) des états initiaux désignés ou arbitraires. En conséquence, nous clarifions complètement la résolvabilité du problème de la bipartition uniforme dans le cadre de l’équité mondiale et, s’il est résolu, nous montrons les limites supérieure et inférieure strictes du nombre d’États.
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.
Copier
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
Copier
@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},}
Copier
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 -