Efficient Assignment of Identities in Anonymous Populations
We consider the fundamental problem of assigning distinct labels to agents in the probabilistic model of population protocols. Our protocols operate under the assumption that the size n of the population is embedded in the transition function. Their efficiency is expressed in terms of the number of states utilized by agents, the size of the range from which the labels are drawn, and the expected n
