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}$.


翻译:我们考虑在人口协议的概率模型中为代理商分配不同标签的根本问题 。 我们的协议运行的假设是, 我们的标注协议是静态 w.h.p., 也就是说, 每个代理商最终会到达最终状态, 并且永远保持它的安全, 也就是说, 永远更新分配给任何单一代理商的标签 。 我们首先展示一个快速的, 静态 w. h. p. 和安全的标签协议 。 我们首先展示一个快速的、 静态的 $ 。 我们的协议数量是 安全的, 也就是说, 人口数量是 美元 美元 的 美元 。 我们的标定协议需要的 美元 。

0
下载
关闭预览

相关内容

IFIP TC13 Conference on Human-Computer Interaction是人机交互领域的研究者和实践者展示其工作的重要平台。多年来,这些会议吸引了来自几个国家和文化的研究人员。官网链接:http://interact2019.org/
【2020新书】Kafka实战:Kafka in Action,209页pdf
专知会员服务
67+阅读 · 2020年3月9日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
GCNet:当Non-local遇见SENet
极市平台
11+阅读 · 2019年5月9日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
保序最优传输:Order-preserving Optimal Transport
我爱读PAMI
6+阅读 · 2018年9月16日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2022年2月21日
Arxiv
0+阅读 · 2022年2月20日
Arxiv
0+阅读 · 2022年2月20日
Identity-aware Graph Neural Networks
Arxiv
14+阅读 · 2021年1月25日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
GCNet:当Non-local遇见SENet
极市平台
11+阅读 · 2019年5月9日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
保序最优传输:Order-preserving Optimal Transport
我爱读PAMI
6+阅读 · 2018年9月16日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员