  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. Our labeling protocols are silent w.h.p., i.e., eventually
each agent reaches its final state and remains in it forever w.h.p., as well as
safe, i.e., never update the label assigned to any single agent. We first
present a fast, silent w.h.p.and safe labeling protocol for which the required
number of interactions is asymptotically optimal, i.e., $O(n \log n/\epsilon)$
w.h.p. It uses $(2+\epsilon)n+O(n^c)$ states, for any $c<1,$ and the label
range $1,\dots,(1+\epsilon)n.$ Furthermore, we consider the so-called pool
labeling protocols that include our fast protocol. We show that the expected
number of interactions required by any pool protocol is $\ge \frac{n^2}{r+1}$,
when the labels range is $1,\dots, n+r<2n.$ Next, we provide a protocol which
is silent and safe once a unique leader is provided, and uses only $n+5\sqrt n
+O(n^c)$ states, for any $c<1,$ and draws labels from the range $1,\dots,n.$
The expected number of interactions required by the protocol is $O(n^3).$ On
the other hand, we show that (even if a unique leader is given in advance) any
silent protocol that produces a valid labeling and is safe with probability
$>1-\frac 1n$, uses $\ge n+\sqrt {n-1} -1$ states. Hence, our protocol is
almost state-optimal. We also present a generalization of the protocol to
include a trade-off between the number of states and the expected number of
interactions. Furthermore, we show that for any silent and safe labeling
protocol utilizing $n+t<2n$ states the expected number of interactions required
to achieve a valid labeling is $\ge \frac{n^2}{t+1}$.
