Abelian networks. I: Foundations and examples (Q2804993)

The paper begins with a definition of abelian network, which is a directed graph, vertices represent automata with a single input port (basically, the input alphabet of each automaton consists of a single letter) and multiple output ports, one for each outgoing edge. Each automaton is described by a transition function (which changes the automaton's internal states) and a message-passing function (which produces an output). The term `abelian' is meant to characterize systems for which changing the order of certain interactions has no effect on the final state of the system (roughly, a permutation of inputs has no influence on the output of an automaton). A collection of automata obeying these axioms is called an abelian network. Then a survey of a number of examples is given (these include sandpile and rotor networks as well as two non-unary examples: oil and water, and abelian mobile agents). Then a least-action principle for abelian networks is proved and its consequences are evaluated. As an application, it is shown how abelian networks can solve certain linear and nonlinear integer programs asynchronously.