Algebra, dynamics and computation in abelian networks

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

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.