Space-Optimal Population Protocols for Uniform Bipartition Under Global Fairness
Space-Optimal Population Protocols for Uniform Bipartition Under Global Fairness
复制标题
全球公平下均匀二分的空间最优种群协议
DOI：
10.1587/transinf.2018fcp0009
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. Inoue
中科院分区：
文献类型：
--
作者：
Hiroto Yasumi;Fukuhito Ooshita;K. Yamaguchi;M. Inoue
本文研究一类种群协议模型中的一致二分问题。均匀双划分问题的目标是将一个总体划分为两个大小相同的组。我们在全局公平的假设下研究问题：1)种群有或没有基站，2)对称或非对称协议，3)指定或任意初始状态。结果完全阐明了全局公平条件下一致二分问题的可解性，如果可解，则给出了状态数的紧上界和下界。
SUMMARY 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.
群体协议中的时间和空间优化计数
影响因子：
--
作者：
Aspnes, James;Beauquier, Joffroy;Burman, Janna;Sohier, Devan
通讯作者：
Sohier, Devan
DOI：
10.1137/1.9781611974782.169
发表时间：
2016-02
期刊：
ArXiv
影响因子：
--
作者：
Dan Alistarh;J. Aspnes;David Eisenstat;Rati Gelashvili;R. Rivest
通讯作者：
Dan Alistarh;J. Aspnes;David Eisenstat;Rati Gelashvili;R. Rivest