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美元。 当协议的预期数量为单位时, 将任何有效的协议, 以美元为单位, 以美元为单位, 以美元为单位, 以美元为单位, 我们的当前网络协议的预期互动, 以美元为单位, 以美元为单位。

0
下载
关闭预览

相关内容

IFIP TC13 Conference on Human-Computer Interaction是人机交互领域的研究者和实践者展示其工作的重要平台。多年来,这些会议吸引了来自几个国家和文化的研究人员。官网链接:http://interact2019.org/
专知会员服务
14+阅读 · 2021年5月21日
【2020新书】金融机器学习和数据科学,400页pdf
专知会员服务
291+阅读 · 2020年12月13日
专知会员服务
163+阅读 · 2020年7月27日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年7月18日
Arxiv
0+阅读 · 2021年7月15日
Arxiv
0+阅读 · 2021年7月15日
VIP会员
相关VIP内容
专知会员服务
14+阅读 · 2021年5月21日
【2020新书】金融机器学习和数据科学,400页pdf
专知会员服务
291+阅读 · 2020年12月13日
专知会员服务
163+阅读 · 2020年7月27日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员