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.