A Population Protocol for Uniform $k$-partition under Global Fairness

Hiroto Yasumi, Naoki Kitamura, Fukuhito Ooshita, Taisuke Izumi, Michiko Inoue


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.


population protocol; uniform k-partition; distributed protocol

Full Text:



  • There are currently no refbacks.