Symmetry Breaking with Noisy Processes
Symmetry Breaking with Noisy Processes
复制标题
噪声过程导致对称性破缺
DOI：
10.1145/3087801.3087814
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Newport, Calvin
中科院分区：
文献类型：
--
作者：
Gilbert, Seth;Newport, Calvin
生物学和计算机科学在对称性破缺问题上有交叉，这在两个领域都是相关的。因此，近年来，分布式算法理论家研究了受生物学启发的模型中的对称性破缺问题，以帮助深入了解这一自然过程的能力和约束。然而，这些模型的一个潜在缺点是，它们精确地执行指定的分布式算法。在自然界中，计算通常是由混乱的模拟系统实现的，这种精度不一定能得到保证。出于这一观察，在本文中，我们提出了一个通用的方法，将计算噪声注入到任何分布式系统模型，描述过程的相互作用的状态机。我们的方法将噪声捕获为可能导致状态机转换到错误状态的力。我们结合联合收割机的形式化的噪音与蜂鸣声模型，一直是一个受欢迎的目标，最近的工作生物启发的对称性破缺。我们提出了新的上界和下界的单跳和多跳模型-研究领导选举在前者和最大独立集问题在后者。这些界限介绍了新的技术，实现鲁棒性噪声，并确定在这方面的一些基本限制。我们认为，我们的一般方法和具体的结果可以帮助推进生物学和算法理论之间的生产关系。
Biology and computer science intersect at the problem of symmetry breaking, which is relevant in both fields. Accordingly, in recent years, distributed algorithm theorists have studied symmetry breaking problems in models inspired by biology to help provide insight into the capabilities and constraints of this natural process. A potential shortcoming of these models, however, is that they execute distributed algorithms precisely as specified. In nature, where computation is often implemented by messy analog systems, this precision cannot necessarily be guaranteed. Motivated by this observation, in this paper we present a general method for injecting computational noise into any distributed system model that describes processes as interacting state machines. Our method captures noise as a force that can cause state machines to transition to the wrong state. We combine this formalization of noise with the beeping models that have been a popular target of recent work on bio-inspired symmetry breaking. We produce new upper and lower bounds for both single hop and multihop models---studying leader election in the former and the maximal independent set problem in the latter. These bounds introduce new techniques for achieving robustness to noise, and identify some fundamental limits in this pursuit. We argue that both our general approach and specific results can help advance the productive relationship between biology and algorithm theory.
登录
查看更多内容
无名稿号（编辑将插入）An Optimal Maximal Independent Set Algorithm for Bounded-Independence Graphs
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
M. Naor
通讯作者：
M. Naor
来自自然的反馈：最大独立集选择的最优分布式算法
DOI：
10.1145/2484239.2484247
发表时间：
2012
期刊：
ArXiv
影响因子：
--
作者：
A. Scott;P. Jeavons;Lei Xu
通讯作者：
Lei Xu
来自大自然的反馈：用于最大独立集选择和贪婪着色的简单随机分布式算法
影响因子：
1.3
作者：
P. Jeavons;A. Scott;Lei Xu
通讯作者：
Lei Xu
来自自然的模式：具有简单消息和最少图形知识的分布式贪婪着色
DOI：
10.1016/j.ins.2014.06.035
发表时间：
2015
期刊：
Inf. Sci.
影响因子：
--
作者：
Lei Xu;P. Jeavons
通讯作者：
P. Jeavons
多跳蜂鸣网络中的确定性领导者选举 -（扩展摘要）
DOI：
10.1007/978-3-662-45174-8_15
发表时间：
2014
期刊：
The Journal of Maternal-Fetal & Neonatal Medicine
影响因子：
--
作者：
Klaus;J. Seidel;Roger Wattenhofer
通讯作者：
Roger Wattenhofer