In this paper we consider a variant of population protocols in which agents are allowed to be connected by edges, known as the constructors model. During an interaction between two agents the relevant connecting edge can be formed, maintained or eliminated by the transition function. The contributions of this paper are manifold. -- We propose and analyse a novel type of phase clocks allowing to count parallel time $\Theta(n\log n)$ in the constructors model. This new type of clocks can be also implemented in the standard population protocol model assuming a unique leader is available. -- The new clock enables a nearly optimal $O(n\log n)$ parallel time spanning line construction which improves dramatically on the best previously known $O(n^2)$ parallel time solution. -- We define a probabilistic version of bubble-sort in which random comparisons are allowed only between adjacent numbers in the sequence being sorted. We show that rather surprisingly this probabilistic bubble-sort requires $O(n^2)$ comparisons in expectation, i.e., on the same level as its deterministic counterpart. -- We propose the first self-replication protocol allowing to reproduce a {\em strand} (line-segment carrying information) of length $k$ in parallel time $O(n(k+\log n)).$ This result is based on the probabilistic bubble-sort argument. This protocol permits also simultaneous replication where $l$ copies of the strand can be obtained in time $O(n(k+\log n)\log l).$ All protocols in this paper operate with high probability.


翻译:在本文中,我们考虑一个人口协议的变体, 允许代理商通过边缘连接, 称为构建者模型。 在两个代理商之间的互动中, 相关的连接边缘可以通过过渡功能形成、 维护或消除。 本文的贡献是多方面的。 -- 我们提议和分析一种新型的阶段钟, 允许在构建者模型中计算平行时间$\ Theta( n\log n) 美元。 这种新型的时钟也可以在标准的人口协议模式中实施, 假设有一个独特的领先者 。 -- 新时钟可以让一个几乎最佳的 $O( n\log n) 平行时间跨线的构建, 从而在最已知的 $O( n\ 2) 的平行时间解决方案中大大改进。 -- 我们定义了一个气泡- 状态的概率化版本, 允许在正在排序的序列中的相邻数字之间进行随机比较。 我们显示, 令人惊讶的是, 这种不稳定的气泡- 质化气旋- sort 模式需要 $ (n2) 比较, 也就是, 和它的确定性对应的 $( rominal n) ral ral ral) ral ral col- passal exal pass passil exil exil ex) 。

0
下载
关闭预览

相关内容

FAST:Conference on File and Storage Technologies。 Explanation:文件和存储技术会议。 Publisher:USENIX。 SIT:http://dblp.uni-trier.de/db/conf/fast/
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
163+阅读 · 2020年3月18日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
Call for Nominations: 2022 Multimedia Prize Paper Award
CCF多媒体专委会
0+阅读 · 2022年2月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium7
中国图象图形学学会CSIG
0+阅读 · 2021年11月15日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2022年7月5日
Arxiv
0+阅读 · 2022年7月4日
Arxiv
1+阅读 · 2022年6月30日
Arxiv
13+阅读 · 2021年3月3日
VIP会员
相关VIP内容
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
Call for Nominations: 2022 Multimedia Prize Paper Award
CCF多媒体专委会
0+阅读 · 2022年2月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium7
中国图象图形学学会CSIG
0+阅读 · 2021年11月15日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
相关基金
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员