Algebra, dynamics and computation in abelian networks

阿贝尔网络中的代数、动力学和计算

• 批准号: 1105960
• 负责人: Lionel Levine
• 金额: $ 14万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-15 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1105960&HistoricalAwards=false
• 关键词: Algebra; dynamics; computation; abelian; networks

This research aims to shed light on three fundamental questions: (1) How do small-scale interactions combine to produce complex large-scale structure? (2) What kinds of computational tasks can be performed in a distributed system with no central control over timing? (3) What kinds of algebraic invariants can help distinguish between nonisomorphic graphs? Abelian networks tie these three questions together: From a dynamical point of view, an abelian network is a cellular automaton that produces complex patterns using local rules. From a computational point of view, an abelian network yields the same output regardless of the timing of events at its individual nodes. And from an algebraic point of view, an abelian network associates an invariant, in the form of an abelian group or commutative algebra, to its underlying graph.What can a network of computers reliably accomplish if each computer in the network runs at a different and unpredictable speed? Answering this question would bring us closer to understanding complex networks like the brain, the economy and the internet. A related question asks what kinds of patterns can arise from simple interacting components in a situation where the order of interactions does not matter. A better understanding of pattern formation would aid in engineering desired large-scale outcomes by modifying only small-scale features of a system. This kind of problem arises, for example, in designing a road network to minimize traffic delays and in using nanotechnology to engineer stronger materials.

本研究旨在阐明三个基本问题：（1）小尺度相互作用如何联合收割机产生复杂的大尺度结构？(2)什么样的计算任务可以在没有中央控制的分布式系统中执行？(3)什么样的代数不变量可以帮助区分非同构图？ 阿贝尔网络将这三个问题联系在一起：从动力学的角度来看，阿贝尔网络是一种使用局部规则产生复杂模式的元胞自动机。从计算的角度来看，阿贝尔网络产生相同的输出，而不管其各个节点上的事件发生的时间。从代数的角度来看，阿贝尔网络将一个不变量（以阿贝尔群或交换代数的形式）与其底层图相关联。如果网络中的每台计算机都以不同的、不可预测的速度运行，那么计算机网络能够可靠地完成什么任务呢？ 回答这个问题将使我们更接近于理解大脑、经济和互联网等复杂网络。一个相关的问题是，在交互顺序无关紧要的情况下，什么样的模式可以从简单的交互组件中产生。更好地理解模式形成将有助于通过仅修改系统的小尺度特征来设计期望的大尺度结果。 例如，在设计道路网络以最大限度地减少交通延误以及使用纳米技术来设计更坚固的材料时就会出现这种问题。