{'fraction_non_alphanumeric': 0.047437376157099344, 'fraction_numerical': 0.010114453021027415, 'mean_word_length': 3.981437831467295, 'pattern_counts': {'":': 1, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Abelian networks I. Foundations and examples

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 non-unary examples of abelian networks:"oil and water"and"abelian mobile agents".


Introduction
In recent years, it has become clear that certain interacting particle systems studied in combinatorics and statistical physics have a common underlying structure. These systems are characterized by an abelian property which says changing the order of certain interactions has no effect on the final state of the system. Up to this point, the tools used to study these systems -least action principle, local-toglobal principles, burning algorithm, transition monoids and critical groups -have been developed piecemeal for each particular system. Following Dhar [Dha99a], we aim to identify explicitly what these various systems have in common and exhibit them as special cases of what we call an abelian network.
Intuition suggests that noncommutativity is a major source of dynamical richness and complexity. Yet abelian networks produce surprisingly rich and intricate large-scale patterns from local rules [Ost03,DSC09,DD13]. Just as in physics one infers from macroscopic observations the properties of microscopic particles, we would like to be able to infer from the large-scale behavior of a cellular automaton something about the local rules that generate that behavior. In particular, are there certain large-scale features that can only be produced by noncommutative local interactions? By now a lot is known about the computational complexity of the abelian sandpile model [GM97,MN99]; see [MM11] for a recent compilation. The requirement that a distributed network produce the same output regardless of the order in which processors act would seem to place a severe restriction on the kinds of tasks it can perform. Yet abelian networks can perform some highly nontrivial tasks, such as solving certain linear and nonlinear integer programs (see §4.4). Are there other computational tasks that require noncommutativity?
In this paper and its sequels, by defining abelian networks and exploring their fundamental properties, we hope to take a step toward making these questions precise and eventually answering them. After giving the formal definition of an abelian network in §2, we survey a number of examples in §3. These include the well-studied sandpile and rotor networks as well as two non-unary examples: oil and water, and abelian mobile agents. In §4 we prove a least action principle for abelian networks and explore some of its consequences. One consequence is that "local abelianness implies global abelianness" (Lemma 4.7). Another is that abelian networks solve optimization problems of the following form: given a nondecreasing function F : N k → N k , find the coordinatewise smallest vector u ∈ N k such that F (u) ≤ u (if it exists).
This paper is the first in a series of three. In the sequel [BL14a] we give conditions for a finite abelian network to halt on all inputs. Such a network has a natural invariant attached to it, the critical group, whose structure we investigate in [BL14b].

Definition of an abelian network
This section begins with the formal definition of an abelian network, which is based on Deepak Dhar's model of abelian distributed processors [Dha99a,Dha99b,Dha06]. The term "abelian network" is convenient when one wants to refer to a collection of communicating processors as a single entity. Some readers may wish to look at the examples in §3 before reading this section in detail.
Let G = (V, E) be a directed graph, which may have self-loops and multiple edges. Associated to each vertex v ∈ V is a processor P v , which is an automaton with a single input feed and multiple output feeds, one for each edge (v, u) ∈ E. Each processor reads the letters in its input feed in first-in-first-out order.
The processor P v has an input alphabet A v and state space Q v . Its behavior is governed by a transition function T v and message passing functions T (v,u) associated to each edge (v, u) ∈ E. Formally, these are maps where A * u denotes the free monoid of all finite words in the alphabet A u . We interpret these functions as follows. If the processor P v is in state q and processes input a, then two things happen: (1) Processor P v transitions to state T v (a, q); and (2) For each edge (v, u) ∈ E, processor P u receives input T (v,u) (a, q).
If more than one P v has inputs to process, then changing the order in which processors act may change the order of messages arriving at other processors. Concerning this issue, Dhar writes that "In many applications, especially in computer science, one considers such networks where the speed of the individual processors is unknown, and where the final state and outputs generated should not depend on these speeds. Then it is essential to construct protocols for processing such that the final result does not depend on the order at which messages arrive at a processor." [Dha06] Therefore we ask that the following aspects of the computation do not depend on the order in which individual processors act: (a) The halting status (i.e., whether or not processing eventually stops).
(b) The final output (final states of the processors).
(c) The run time (total number of letters processed by all P v ).
(d) The local run times (number of letters processed by a given P v ).
(e) The specific local run times (number of times a given P v processes a given letter a ∈ A v ). A priori it is not obvious that these goals are actually achievable by any nontrivial network. In §4 we will see, however, that a simple local commutativity condition ensures all five goals are achieved. To state this condition, we extend the domain of where the product denotes concatenation of words.
Let N A be the free commutative monoid generated by A, and write w → |w| for the natural map A * → N A , so that |w| a for a ∈ A denotes the number of letters a in the word w.
Definition 2.1. (Abelian Processor) The processor P v is called abelian if for any words w, w ∈ A * v such that |w| = |w |, we have for all q ∈ Q v and all edges and That is, permuting the letters input to P v does not change the resulting state of the processor P v , and may change each output word sent to P u only by permuting its letters.
Definition 2.2. (Abelian Network) An abelian network on a directed graph G = (V, E) is a collection of automata N = (P v ) v∈V indexed by the vertices of G, such that each P v is abelian.
We make a few remarks about the definition: 1. The definition of an abelian network is local in the sense that it involves checking a condition on each processor individually. As we will see, these local conditions imply a "global" abelian property (Lemma 4.7).
2. A processor P v is called unary if its alphabet A v has cardinality 1. A unary processor is trivially abelian, and any network of unary processors is an abelian network. Most of the examples of abelian networks studied so far are actually unary networks (an exception is the block-renormalized sandpile defined in [Dha99a]). Non-unary networks represent an interesting realm for future study.
The "oil and water model" defined in §3.8 is an example of an abelian network that is not a block-renormalized unary network.
2.1. Comparison with cellular automata. Cellular automata are traditionally studied on the grid Z d or on other lattices, but they may be defined on any directed graph G. Indeed, we would like to suggest that the study of cellular automata on G could be a fruitful means of revealing interesting graph-theoretic properties of G.
Abelian networks may be viewed as cellular automata enjoying the following two properties.
1. Abelian networks can update asynchronously. Traditional cellular automata update in parallel: at each time step, all cells simultaneously update their states based on the states of their neighbors. Since perfect simultaneity is hard to achieve in practice, the physical significance of parallel updating cellular automata is open to debate. Abelian networks do not require the kind of central control over timing needed to enforce simultaneous parallel updates, because they reach the same final state no matter in what order the updates occur.
2. Abelian networks do not rely on shared memory. Implicit in the update rule of cellular automata is an unspecified mechanism by which each cell is kept informed of the states of its neighbors. The lower-level interactions needed to facilitate this exchange of information in a physical implementation are absent from the model. Abelian networks include these interactions by operating in a "message passing" framework instead of the "shared memory" framework of cellular automata: An individual processor in an abelian network cannot access the states of neighboring processors, it can only read the messages they send.

Examples
3.1. Sandpile networks. Figure 1 shows increasingly general classes of abelian networks. The oldest and most studied is the abelian sandpile model [BTW87,Dha90], also called chip-firing [BLS91,Big99]. Given a directed graph G = (V, E), the processor at each vertex v ∈ V has input alphabet A v = {v} and state space (Formally we should write T v (v, q), but when #A v = 1 we omit the redundant first argument.) The message passing functions are Here ∈ A * denotes the empty word. Thus each time the processor at vertex v transitions from state r v − 1 to state 0, it sends one letter to each of its out-neighbors ( Figure 2). When this happens we say that vertex v topples (or "fires"). 3.2. Toppling networks. These have the same transition and message passing functions as the sandpile networks above, but we allow the number of states r v (called the threshold of vertex v) to be different from the outdegree of v. These networks can be concretely realized in terms of "chips": If a vertex in state q has k letters in its input feed, then we say that there are q + k chips at that vertex.
When v has at least r v chips, it can topple, losing r v chips and sending one chip along each outgoing edge. In a sandpile network the total number of chips is conserved, but in a toppling network, chips may be created (if r v is less than the outdegree of v, as in the last diagram of Figure 2) or destroyed (if r v is larger than the outdegree of v). Note that some chips are "latent" in the sense that they are encoded by the internal states of the processors. For example if a vertex v with r v = 2 is in state 0, receives one chip and processes it, then the letter representing that chip is gone, but the internal state increases to 1 representing a latent chip at v. If v receives another chip and processes it, then its state returns to 0 and it topples by sending one letter to each out-neighbor.
It is convenient to specify a toppling network by its Laplacian, which is the Here d uv is the number of edges from v to u in the graph G.
Sometimes it is useful to consider toppling networks where the number of chips at a vertex may become negative [Lev14]. We can model this by enlarging the state space of each processor to include −N; these additional states have transition function T v (q) = q+1 and send no messages. In §4.4 we will see that these enlarged toppling networks solve certain integer programs.  3.3. Sinks and counters. It is common to consider the sandpile network Sand(G, s) with a sink s, a vertex whose processor has only one state and never sends any messages. If every vertex of G has a directed path to the sink, then any finite input to Sand(G, s) will produce only finitely many topplings. The set of recurrent states of a sandpile network with sink is in bijection with objects of interest in combinatorics such as oriented spanning trees and G-parking functions [PS04]. Recurrent states of more general abelian networks are defined and studied in the sequel paper [BL14b].
A counter is a unary processor with state space N and transition T (q) = q + 1, which never sends any messages. It behaves like a sink, but keeps track of how many letters it has received.
3.4. Bootstrap percolation. In this simple model of crack formation, each vertex v has a threshold b v . Vertex v becomes "infected" as soon as at least b v of its in-neighbors are infected. Infected vertices remain infected forever. A question that has received a lot of attention [Ent87,Hol03] due to its subtle scaling behavior is: What is the probability the entire graph becomes infected, if each vertex independently starts infected with probability p? To realize bootstrap percolation as an abelian network, we take The internal state q of the processor P v keeps track of how many in-neighbors of v are infected. When this count reaches the threshold, P v sends a letter to each out-neighbor of v informing them that v is now infected.
3.5. Rotor networks. A rotor is a unary processor P v that outputs exactly one letter for each letter input. That is, for Inputting a single letter into a network of rotors yields an infinite walk (v n ) n≥0 , where vertex v n is the location of the single letter present after n processings. This rotor walk has been studied under various names: In computer science it was introduced as a model of autonomous agents exploring a territory ("ant walk," [WLB96]) and later studied as a means of broadcasting information through a network [DFS08]. In statistical physics it was proposed as a model of self-organized criticality ("Eulerian walkers," [PDDK96]  Most commonly studied are the simple rotor networks on a directed graph G, in which the out-neighbors of vertex v are served repeatedly in a fixed order u 1 , . . . , u dv (Figure 3). Formally, we set and message passing functions Rotor aggregation. Enlarge each state space Q v of a simple rotor network to include a transient state −1, which transitions to state 0 but passes no message. Starting with all processors in state −1, the effect is that each vertex "absorbs" the first letter it receives, and behaves like a rotor thereafter. If we input n letters to one vertex v 0 , then each letter performs a rotor walk starting from v 0 until reaching a site that has not yet been visited by any previous walk, where it gets absorbed. Propp [Pro03] proposed this model as a way of derandomizing a certain random growth process (internal DLA). When the underlying graph is the square grid Z 2 , the resulting set of n visited sites is very close to circular [LP09], and the final states of the processors display intricate patterns that are still not well understood. Next we discuss two non-unary examples.
3.7. Abelian mobile agents. In the spirit of [WLB96], one could replace the messages in our definition of abelian networks by mobile agents each of which is an automaton. As a function of its own internal state a and the state q of the vertex v it currently occupies, an agent acts by doing three things: (1) it changes its own state to S v (a, q); and (2) it changes the state of v to T v (a, q); and (3) it moves to a neighboring vertex U v (a, q). Two or more agents may occupy the same vertex, in which case we require that the outcome of their actions is the same regardless of the order in which they act. For purposes of deciding whether two outcomes are the same, we regard agents with the same internal state and location as indistinguishable.
This model may appear to lie outside our framework of abelian networks, because the computation is located in the moving agents (who carry their internal states with them) instead of in the static processors. However, a moment's thought Figure 5. Abelian mobile agents: Example state diagram for a processor P v in a network whose underlying graph is a path or a cycle. When an agent arrives at vertex v, she transitions the state of v (upward if her own state is red, rightward if blue); updates her own state to red or blue according to the color of the line crossed; and moves to v − 1 or v + 1 according to whether the line is solid or dashed. In this example #Q v = 12, and the boxes indicate periodicity in the diagram.
shows that it has identical behavior to the abelian network with transition function T v and message passing function Abelian mobile agents generalize the rotor networks ( §3.5) by dropping the requirement that processors be unary. The defining property of abelian mobile agents is that each processor sends exactly one letter for each letter received. In Figure 5 this property is apparent from the fact that each segment of the square grid lies on exactly one message line.
3.8. Oil and water model. This is a non-unary generalization of sandpiles, inspired by Paul Tseng's asynchronous algorithm for solving certain linear programs [Tse90]. Each edge of G is marked either as an oil edge or a water edge. When a vertex topples, it sends out one oil chip along each outgoing oil edge and also one water chip along each outgoing water edge. The interaction between oil and water is that a vertex is permitted to topple if and only if sufficiently many chips of both types are present at that vertex.
Unlike most of the preceding examples, oil and water can not be realized with a finite state space Q v , because an arbitrary number of oil chips could accumulate at v and be unable to topple if no water chips are present. We set The internal state of the processor at v is a vector q = (q oil , q water ) keeping track of the total number chips of each type it has received ( Figure 6). Stochastic versions of the oil and water model are studied in [APR09,CGHL14].  (1, 2), resulting in transition to state (2, 2)).
3.9. Stochastic abelian networks. In a stochastic abelian network, we allow the transition functions to depend on a probability space Ω: A variety of models in statistical mechanics -including classical Markov chains and branching processes, branching random walk, certain directed edge-reinforced walks, internal DLA [DF91], the Oslo model [Fre93], the abelian Manna model [Dha99c], excited walk [BW03], the Kesten-Sidoravicius infection model [KS05,KS08], two-component sandpiles and related models derived from abelian algebras [AR08, APR09], activated random walkers [DRS10], stochastic sandpiles [RS12,CMS13], and low-discrepancy random stack [FL13] -can all be realized as stochastic abelian networks. In at least one case [RS12] the abelian nature of the model enabled a major breakthrough in proving the existence of a phase transition. Stochastic abelian networks are beyond the scope of the present paper and will be treated in a sequel.

Least action principle
Our first aim is to prove a least action principle for abelian networks, Lemma 4.3. This principle says -in a sense to be made precise -that each processor in an abelian network performs the minimum amount of work possible to remove all messages from the network. Various special cases of the least action principle to particular abelian networks have enabled a flurry of recent progress: bounds on the growth rate of sandpiles [FLP10], exact shape theorems for rotor aggregation [KL10,HS11], proof of a phase transition for activated random walkers [RS12], and a fast simulation algorithm for growth models [FL13]. The least action principle was also the starting point for the recent breakthrough by Pegden and Smart [PS13] showing existence of the abelian sandpile scaling limit.
The proof of the least action principle follows Diaconis and Fulton [DF91, Theorem 4.1]. Our observation is that their proof actually shows something more general: it applies to any abelian network. Moreover, as noted in [Gab94,FLP10,RS12], the proof applies even to executions that are complete but not legal. To explain the last point requires a few definitions.
Let N be an abelian network with underlying graph G = (V, E), total state space Q = Q v and total alphabet A = A v . In this section we do not place any finiteness restrictions on N: the underlying graph may be finite or infinite, and the state space Q v and alphabet A v of each processor may be finite or infinite.
We may view the entire network N as a single automaton with alphabet A and state space Z A × Q. For its states we will use the notation x.q, where x ∈ Z A and q ∈ Q. If x ∈ N A the state x.q corresponds to the configuration of the network N such that • For each a ∈ A, there are x a letters of type a present; and • For each v ∈ V , the processor at vertex v is in state q v . Allowing x to have negative coordinates is a useful device that enables the least action principle (Lemma 4.3 below). Formally, x.q is just an alternative notation for the ordered pair (x, q). The decimal point in x.q is intended to evoke the intuition that the internal states q of the processors represent latent "fractional" messages.
Note that x.q indicates only the states of the processors and the number of letters present of each type. It gives no information about the order in which letters are to be processed. Indeed, one of our goals is to show that the order does not matter (Theorem 4.6).
For v ∈ V and a ∈ A v , denote by t a : Q → Q the map §2). We define the state transition π a : where 1 ab is 1 if a = b and 0 otherwise; and N(a, q v ) b is the number of b's produced when processor P v in state q v processes the letter a. In other words, where T e is the message passing function of edge e, and the sum is over all outgoing edges e from v (both sides are vectors in Z A ).
Having defined π a for letters a, we define π w for a word w = w 1 · · · w r ∈ A * as the composition π wr • · · · • π w 1 . To generalize equation (2), we extend the domain of N to A * × Q as follows. Let q i−1 = (t w i−1 • · · · • t w 1 )q and let where v(i) is the unique vertex such that w i ∈ A v(i) . Note that if a ∈ A v and b ∈ A u for v = u, then since t a acts by identity on Q u and t b acts by identity on Q v . Recall that |w| ∈ N A and |w| a is the number of occurrences of letter a in the word w. From the definition of π a we have by induction on r π w (x.q) = (x − |w| + N(w, q)).t w (q) where t w := t wr • · · · • t w 1 . In the next lemma and throughout this paper, inequalities on vectors are coordinatewise.
Proof. For a vertex v ∈ V let p v : A * → A * v be the projection defined by p v (a) = a for a ∈ A v and p v (a) = (the empty word) for a / ∈ A v . Equation (3) implies that so it suffices to prove the lemma for w, w ∈ A * v for each v ∈ V .
Fix v ∈ V and w, w ∈ A * v with |w| ≤ |w |. Then there is a word w such that |ww | = |w |. Given a letter a ∈ A u , if (v, u) / ∈ E then N(w, q) a = N(w , q) a = 0. If (v, u) ∈ E, then since P v is an abelian processor, The first term on the right side equals N(w, q) a , and the remaining term is nonnegative, completing the proof.
Proof. Suppose |w| = |w |. Then for any q ∈ Q we have N(w, q) = N(w , q) by Lemma 4.1. Since t a and t b commute for all a, b ∈ A, we have t w (q) = t w (q). Hence the right side of (4) is unchanged by substituting w for w.

Legal and complete executions.
An execution is a word w ∈ A * . It prescribes an order in which letters in the network are to be processed. For simplicity, we consider only finite executions in the present paper, but we remark that infinite executions (and non-sequential execution procedures) are also of interest [FMR09].
Fix an initial state x.q and an execution w = w 1 · · · w r , where each w i ∈ A. Set x 0 .q 0 = x.q and The result of executing w is π w (x.q) = x r .q r . Our goal is to compare the results of different executions. The letter a ∈ A is called a legal move from x.q if x a ≥ 1. An execution w 1 · · · w r is called legal for x.q if w i+1 is a legal move from x i .q i for each i = 0, . . . , r − 1. An execution w 1 · · · w r is called complete for x.q if x r a ≤ 0 for all a ∈ A.
Lemma 4.3. (Least Action Principle) If w = w 1 · · · w r is legal for x.q and w = w 1 · · · w s is complete for x.q, then |w| ≤ |w | and r ≤ s.
Proof. Noting that r = a∈A |w| a and s = a∈A |w | a , it suffices to prove |w| ≤ |w |. Supposing for a contradiction that |w| ≤ |w |, let i be the smallest index such that |w 1 · · · w i | ≤ |w |. Let u = w 1 · · · w i−1 and a = w i . Then |u| a = |w | a , and Since a is a legal move from x i−1 .q i−1 , we have by (4) and Lemma 4.1 Since w is complete, the right side is ≤ 0 by (4), which yields the required contradiction.

Halting dichotomy.
Lemma 4.4. (Halting Dichotomy) For a given initial state q and input x to an abelian network N, either (1) There does not exist a finite complete execution for x.q; or (2) Every legal execution for x.q is finite, and any two complete legal executions w, w for x.q satisfy |w| = |w |.
Proof. If there exists a finite complete execution, say of length s, then every legal execution has length ≤ s by Lemma 4.3. If w and w are complete legal executions, then |w| ≤ |w | ≤ |w| by Lemma 4.3.
Note that in case (1) any finite legal execution w can be extended by a legal move: since w is not complete, there is some letter a ∈ A such that wa is legal. So in this case there is an infinite word a 1 a 2 · · · such that a 1 · · · a n is a legal execution for all n ≥ 1. The halting problem for abelian networks asks, given N, x and q, whether (1) or (2) of Lemma 4.4 is the case. In case (2) we say that N halts on input x.q. In the sequel [BL14a] we characterize the finite abelian networks that halt on all inputs. No messages remain at the end of a complete legal execution w, so the network ends in state π w (x.q) = 0.t w (q). Hence by (4), the odometer can be written as [x.q] = |w| = x + N(w, q) which simply says that the total number of letters processed (of each type a ∈ A) is the sum of the letters input and the letters produced by message passing. The coordinates of the odometer are the "specific local run times" from §2. We can summarize our progress so far in the following theorem.
Proof. By Lemma 4.4 the halting status does not depend on the execution, which verifies item (a). Moreover for a given N, x, q any two complete legal executions have the same odometer, which verifies items (c)-(e). The odometer and initial state q determine the final state t w (q), which verifies (b).
The next lemma illustrates a general theme of local-to-global principles in abelian networks. Suppose we are given a partition V = I O of the vertex set into "interior" and "output" nodes, and that the output nodes never send messages (for example, the processor at each output node could be a counter, §3.3). We allow the possibility that O is empty. If N halts on all inputs, then we can regard the induced subnetwork (P v ) v∈I of interior nodes as a single processor P I with input alphabet A I := v∈I A v , state space Q I := v∈I Q v , and an output feed for each edge (v, u) ∈ I × O.
Lemma 4.7. (Local Abelianness Implies Global Abelianness) If N halts on all inputs and P v is an abelian processor for each v ∈ I, then P I is an abelian processor.
Proof. Given an input ι ∈ A * I and an initial state q ∈ Q I , we can process one letter at a time to obtain a complete legal execution for |ι|.q. Now suppose we are given inputs ι, ι such that |ι| = |ι |. By Lemma 4.4, any two complete legal executions w, w for |ι|.q satisfy |w| = |w |. In particular, t w (q) = t w (q), so the final state of P I does not depend on the order of input. Now given v ∈ I, let w v be the word obtained from w by deleting all letters not | so for each a ∈ A u the number of letters a sent along (v, u) does not depend on the order of input.
For another example of a local-to-global principle, see [BL14b, Lemma 2.6]. Further local-to-global principles in the case of rotor networks are explored in [GLPZ12]. 4.4. Monotone integer programming. In this section we describe a class of optimization problems that abelian networks can solve. Let A be a finite set and F : N A → N A a nondecreasing function: F (u) ≤ F (v) whenever u ≤ v (inequalities are coordinatewise). Let c ∈ R A be a vector with all coordinates positive, and consider the following problem.

Minimize
c T u subject to u ∈ N A and F (u) ≤ u.
Let us call a vector u ∈ N A feasible if F (u) ≤ u. If u 1 and u 2 are both feasible, then their coordinatewise minimum is feasible: Therefore if a feasible vector exists then the minimizer is unique and independent of the positive vector c: it is simply the coordinatewise minimum of all feasible vectors. Let N be an abelian network with finite alphabet A and finite or infinite state space Q. Fix x ∈ N A and q ∈ Q, and let F : N A → N A be given by where N(u, q) is defined as N(w, q) for any word w such that |w| = u. The function F is well-defined and nondecreasing by Lemma 4.1.
Recall the odometer [x.q] is the vector of specific local runtimes (Definition 4.5).
(ii) If N does not halt on input x.q, then (5) has no feasible vector u.
Proof. By (4), any complete execution w for x.q satisfies F (|w|) ≤ |w|; and conversely, if F (u) ≤ u then any w ∈ A * such that |w| = u is a complete execution for x.q.
If N halts on input x.q then the odometer [x.q] is defined as |w| for a complete legal execution w. By the least action principle (Lemma 4.3), for each a ∈ A we have [x.q] a = min{|w| a : w is a complete execution for x.q} so [x.q] is the coordinatewise minimum of all feasible vectors.
If N does not halt on input x.q, then there does not exist a complete execution for x.q, so there is no feasible vector.
For any nondecreasing F : N A → N A , there is an abelian network N F that solves the corresponding optimization problem (5). Its underlying graph is a single vertex v with a loop e = (v, v). It has state space Q = N A , transition function T v (a, q) = q + 1 a and message passing function satisfying for all a ∈ A and q ∈ Q. For the input we take x = F (0) and q = 0.
Remark 4.9. In general the problem (5) is nonlinear, but in the special case of a toppling network it is equivalent to a linear integer program of the following form. Minimize Here c ∈ R A has all coordinates positive; L is the Laplacian matrix ( §3.2); and b = x − r + 1 where x a is the number of chips input at a and r a is the threshold of a. The coordinate v a of the minimizer is the number of times a topples. To see the equivalence of (5) and (6) for toppling networks, note that F takes the following form for a toppling network: where D is the diagonal matrix with diagonal entries r a , and · denotes the coordinatewise greatest integer function. Using that D−L is a nonnegative matrix, one checks that u = x + (D − L)v is feasible for (5) if and only if v is feasible for (6).

Concluding Remarks
We indicate here a few directions for further research on abelian networks. Other directions are indicated in the sequels [BL14a,BL14b].
Asynchronous graph algorithms. What does an abelian network "know" about its underlying graph? For instance, Chan, Church and Grochow [CCG14] have shown that a rotor network can detect whether its underlying graph is planar (with edge orderings respecting the planar embedding). Theorem 4.6 shows that abelian networks can compute asynchronously, and Theorem 4.8 gives an example of something they can compute. It would be interesting to explore whether abelian networks can perform computational tasks like shortest path, pagerank, image restoration and belief propagation.
Abelian networks with shared memory. In §2.1 we have emphasized that abelian networks do not rely on shared memory. Yet there are quite a few examples of processes with a global abelian property that do. Perhaps the simplest is sorting by adjacent transpositions: suppose G is the path of length n and each vertex v has state space Q v = Z. The processors now live on the edges: for each edge e = (v, v + 1) the processor P e acts by swapping the states q(v) and q(v + 1) if q(v) > q(v + 1). This example does not fit our definition of abelian network because the processors of edges (v − 1, v) and (v, v + 1) share access to the state q(v). Indeed, from our list of five goals in §2 this example satisfies items (a)-(c) only: The final output is always sorted, and the run time does not depend on the execution, but the local run times do depend on the execution.
What is the right definition of an abelian network with shared memory? Examples could include the numbers game of Mozes [Moz90], k-cores of graphs and hypergraphs, Wilson cycle popping [Wil96] and its extension by Gorodezky and Pak [GP13], source reversal [GP00] and cluster firing [H + 08, Bac12, CPS12].
Nonabelian networks. The work of Krohn and Rhodes [KR65,KR68] led to a detailed study of how the algebraic structure of monoids relates to the computational strength of corresponding classes of automata. It would be highly desirable to develop such a dictionary for classes of automata networks. Thus one would like to weaken the abelian property and study networks of solvable automata, nilpotent automata, etc. Such networks are nondeterministic -the output depends on the order of execution -so their theory promises to be rather different from that of abelian networks. It could be fruitful to look for networks that exhibit only limited nondeterminism. A concrete example is a sandpile network with annihilating particles and antiparticles, studied by Robert Cori (unpublished) and in [CPS12] under the term "inverse toppling."