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. They also rely on a unique leader which can be precomputed with a negligible impact on our upper bounds. Among other things, we consider silent labeling protocols, where eventually each agent reaches its final state and remains in it forever, as well as safe labeling protocols which can produce a valid agent labeling in a finite number of interactions, and guarantee that at any step of the protocol no two agents have the same label. We first provide a silent and safe protocol which uses only $n+5\sqrt n +4$ states 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 any safe protocol, as well as any silent protocol which provides a valid labeling with probability $>1-\frac 1n$, uses $\ge n+\sqrt n-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. We show also that for any 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}$. Next, we present a fast, silent 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(\log n)$ states and the label range $1,\dots,(1+\epsilon)n.$ Finally, 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.$
翻译:我们考虑在人口协议的概率模型中为代理商指定不同的标签。 我们的协议运行的假设是, 以美元为单位, 以美元为单位, 以美元为单位, 以美元为单位, 以美元为单位。 它们还依赖于一个独特的领导者, 可以预先计算, 对我们上界的影响微不足道。 除其他外, 我们考虑静态标签协议, 最终每个代理商都达到最终状态, 并且永远留在其中, 安全标签协议可以产生一个有效的代理商标签, 在协议的任何步骤中, 以一定数量为单位, 保证两个代理商没有相同的标签。 我们首先提供一个静态和安全协议, 仅使用美元+5\sqrt n+4美元。 当协议的预期数量为单位时, 将任何有效的协议, 以美元为单位, 以美元为单位, 以美元为单位, 以美元为单位, 我们的当前网络协议的预期互动, 以美元为单位, 以美元为单位。