Abelian networks IV. Dynamics of nonhalting networks

Swee Hong Chan, Lionel LevinearXiv 2018 · arXiv

Introduction

Abelian networks represent a class of communicating automata where the final state of the system is independent of the order in which individual components are updated. This property, known as confluence, makes them highly valuable in both theoretical computer science and statistical physics. Historically, the study of these networks has been confined to systems that eventually halt. In "Abelian Networks IV," the authors extend this theoretical framework to nonhalting networks—systems that run indefinitely—revealing that key dynamical features remain "atemporal" and independent of the specific execution path.

Atemporal Dynamics and Firing Rates

In a halting network, the primary object of study is the final configuration. In a nonhalting network, where no final state exists, the focus shifts to the long-term behavior of the system. The authors demonstrate that the firing rate—the frequency with which a specific node fires over an infinite execution—is an intrinsic property of the network.

This "update independence" implies that whether nodes are updated sequentially, in parallel, or via any other legal schedule, the relative speeds of the nodes remain constant. This finding allows for the study of atemporal dynamics, where the evolution of the system can be analyzed without reference to a specific global clock or update rule.

The Torsion Group

A central contribution of the paper is the introduction of the Torsion Group. In the context of halting sandpile models, the "sandpile group" (or critical group) is a well-known algebraic invariant. The authors show that this group is a specific instance of a more general Torsion Group that applies to any irreducible Abelian network, including those that never reach equilibrium.

By utilizing commutative monoid actions and the Grothendieck group of the "shift monoid," the authors prove that the Torsion Group acts freely on the recurrent components of the network. This provides a rigorous algebraic foundation for understanding the steady-state behavior of infinite processes.

Methodology: Trajectory Digraphs and the Removal Lemma

To analyze these systems, the authors move beyond single execution paths to examine trajectory digraphs—infinite directed graphs representing all possible configurations and transitions. They introduce several novel tools:

  • The Removal Lemma: This lemma allows researchers to "shorten" legal executions, proving that periodic behaviors can be reduced to their minimal, intrinsic cycles.
  • Thief Networks: To study "critical" networks (those at the threshold of halting), the authors design "thief networks" that simulate the loss of information or "chips." This mapping allows complex nonhalting dynamics to be analyzed using established halting network theory.

Key Results and Mathematical Models

The paper validates its framework against several canonical models, including sinkless rotor-routing, sinkless sandpiles, and Abelian mobile agents. Two major theorems stand out:

  1. Theorem 1.1: Establishes the isomorphism between the Torsion Group and the Grothendieck group of the shift monoid and its free action on invertible recurrent components.
  2. Theorem 1.4 (The Determinant Formula): For agent-based networks, the authors derive a generating function for the number of recurrent configurations ($r_n$) with $n$ agents: $$\sum_{n \ge 1} r_n z^n = \det\left( \frac{1}{1-z} D - A \right)$$ where $D$ is the outdegree matrix and $A$ is the adjacency matrix.

Furthermore, the authors establish a spectral connection, showing that the sequence of recurrent configurations $(r_n)$ is sufficient to determine the spectrum of a simple random walk on the underlying network graph.

Discussion and Future Directions

The paper categorizes networks based on their growth rates: subcritical ($\lambda < 1$), critical ($\lambda = 1$), and supercritical ($\lambda > 1$). While the dynamics of critical networks are now well-defined through the Torsion Group and the generalized "burning test" (an extension of Dhar’s algorithm), supercritical networks remain a frontier. In these systems, the number of active agents or messages grows exponentially, presenting challenges for current algebraic methods.

The authors conclude by highlighting the need for a unified theory of recurrence that seamlessly bridges the gap between halting and nonhalting systems, posing significant questions for the future of algebraic combinatorics and automata theory.

Summary updated

Abstract

An abelian network is a collection of communicating automata whose state transitions and message passing each satisfy a local commutativity condition. This paper is a continuation of the abelian networks series of Bond and Levine (2016), for which we extend the theory of abelian networks that halt on all inputs to networks that can run forever. A nonhalting abelian network can be realized as a discrete dynamical system in many different ways, depending on the update order. We show that certain features of the dynamics, such as minimal period length, have intrinsic definitions that do not require specifying an update order. We give an intrinsic definition of the \emph{torsion group} of a finite irreducible (halting or nonhalting) abelian network, and show that it coincides with the critical group of Bond and Levine (2016) if the network is halting. We show that the torsion group acts freely on the set of invertible recurrent components of the trajectory digraph, and identify when this action is transitive. This perspective leads to new results even in the classical case of sinkless rotor networks (deterministic analogues of random walks). In Holroyd et. al (2008) it was shown that the recurrent configurations of a sinkless rotor network with just one chip are precisely the unicycles (spanning subgraphs with a unique oriented cycle, with the chip on the cycle). We generalize this result to abelian mobile agent networks with any number of chips. We give formulas for generating series such as \[ \sum_{n \geq 1} r_n z^n = \det (\frac{1}{1-z}D - A ) \] where $r_n$ is the number of recurrent chip-and-rotor configurations with $n$ chips; $D$ is the diagonal matrix of outdegrees, and $A$ is the adjacency matrix. A consequence is that the sequence $(r_n)_{n \geq 1}$ completely determines the spectrum of the simple random walk on the network.
BibTeX
@misc{chan2018abelian,
  author = {Swee Hong Chan and Lionel Levine},
  title = {{Abelian networks IV. Dynamics of nonhalting networks}},
  year = {2018},
  eprint = {1804.03322},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1804.03322},
}
Figure