Space-Optimal Population Protocols for Uniform Bipartition Under Global Fairness

Hiroto YASUMI  Fukuhito OOSHITA  Ken'ichi YAMAGUCHI  Michiko INOUE  

IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.3   pp.454-463
Publication Date: 2019/03/01
Publicized: 2018/10/30
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018FCP0009
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
population protocol,  uniform bipartition,  distributed protocol,  

Full Text: PDF(480.2KB)>>
Buy this Article

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.