For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2019/03/01
Online ISSN: 1745-1361
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>>
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.