Beeping models are models for networks of weak devices, such as sensor networks or biological networks. In these networks, nodes are allowed to communicate only via emitting beeps: unary pulses of energy. Listening nodes only the capability of {\it carrier sensing}: they can only distinguish between the presence or absence of a beep, but receive no other information. The noisy beeping model further assumes listening nodes may be disrupted by random noise. Despite this extremely restrictive communication model, it transpires that complex distributed tasks can still be performed by such networks. In this paper we provide an optimal procedure for simulating general message passing in the beeping and noisy beeping models. We show that a round of \textsf{Broadcast CONGEST} can be simulated in $O(\Delta\log n)$ round of the noisy (or noiseless) beeping model, and a round of \textsf{CONGEST} can be simulated in $O(\Delta^2\log n)$ rounds (where $\Delta$ is the maximum degree of the network). We also prove lower bounds demonstrating that no simulation can use asymptotically fewer rounds. This allows a host of graph algorithms to be efficiently implemented in beeping models. As an example, we present an $O(\log n)$-round \textsf{Broadcast CONGEST} algorithm for maximal matching, which, when simulated using our method, immediately implies a near-optimal $O(\Delta \log^2 n)$-round maximal matching algorithm in the noisy beeping model.


翻译:脉冲信号模型是针对弱设备网络,例如传感器网络或生物网络的网络模型。在这些网络中,节点只能通过发射脉冲信号进行通信:一种一元脉冲能量信号。接收节点只有一项「载波感知」的能力:只能区分脉冲信号的存在或不存在,但不能获得其他信息。嘈杂的脉冲信号模型还假定受到随机噪声的干扰。尽管具有极其严格的通信模型,但这些网络仍然可以执行复杂的分布式任务。在本文中,我们提供了一种在脉冲和嘈杂脉冲模型中模拟普遍信息传递的最优过程。我们展示出,可以在嘈杂(或非噪声性)脉冲模型的$O(\Delta\log n)$ 轮内模拟 \textsf{Broadcast CONGEST}。而在该模型中,在 $O(\Delta^2\log n)$ 轮内模拟\textsf{CONGEST}。这里的 $\Delta$ 是网络的最大度数。我们还证明了没有模拟可以使用渐近更少的轮数。这允许许多图算法在脉冲信号模型中高效实现。例如,我们提出了一个 $O(\log n)$- 轮 \textsf{Broadcast CONGEST}算法来查找最大匹配。当使用我们的方法进行模拟时,它立即意味着在噪声脉冲模型中可以获得近乎最优的 $O(\Delta \log^2 n)$-轮最大匹配算法。

0
下载
关闭预览

相关内容

因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
神经网络的拓扑结构,TOPOLOGY OF DEEP NEURAL NETWORKS
专知会员服务
31+阅读 · 2020年4月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年5月16日
Arxiv
0+阅读 · 2023年5月13日
Arxiv
0+阅读 · 2023年5月13日
Arxiv
0+阅读 · 2023年5月11日
VIP会员
相关资讯
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员