期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2019
卷号：9
期号：1
页码：97-110
出版社：International Journal of Networking and Computing
摘要：In this paper, we consider a uniform k-partition problem in a population protocol model.
The uniform k-partition problem divides a population into k groups of the same size. For this
problem, we give a symmetric protocol with designated initial states under global fairness. The
proposed protocol requires 3k − 2 states for each agent. Since any protocol for the uniform kpartition
problem requires Ω(k) states to indicate a group, the space complexity of the proposed
protocol is asymptotically optimal.
其他摘要：In this paper, we consider a uniform k-partition problem in a population protocol model. The uniform k-partition problem divides a population into k groups of the same size. For this problem, we give a symmetric protocol with designated initial states under global fairness. The proposed protocol requires 3k-2 states for each agent. Since any protocol for the uniform k-partition problem requires ?(k) states to indicate a group, the space complexity of the proposed protocol is asymptotically optimal.
