ABELIAN NETWORKS I. FOUNDATIONS AND EXAMPLES

作者：Bond Benjamin; Levine Lionel

来源：SIAM Journal on Discrete Mathematics, 2016, 30(2): 856-874.

DOI：10.1137/15M1030984

• abelian distributed processors
• asynchronous computation
• chip-firing
• finite automata
• least action principle
• local-to-global principle
• monotone integer program
• rotor walk

In Deepak Dhar's model of abelian distributed processors, automata occupy the vertices of a graph and communicate via the edges. We show that two simple axioms ensure that the final output does not depend on the order in which the automata process their inputs. A collection of automata obeying these axioms is called an abelian network. We prove a least action principle for abelian networks. As an application, we show how abelian networks can solve certain linear and nonlinear integer programs asynchronously. In most previously studied abelian networks, the input alphabet of each automaton consists of a single letter; in contrast, we propose two nonunary examples of abelian networks: oil and water, and abelian mobile agents.

• 出版日期2016