Stochastic abelian networks and rotor-router walks

This project is devoted to the investigation of two models (random walks and their deterministic counterpart rotor-router walks) on infinite graphs. Namely, we aim at describing the geometric and structural properties of the state spaces (the graphs) which are essential for the behavior of these two models. The methods used within this research are at the confluent of more than one field of specialization (probability, algebra, graph theory, combinatorics). A brief outline of the proposed research problems is given below. Rotor-router walks (RRW). Informally, a rotor-router walk on a graph can be described as follows. Each vertex of the graph is endowed with a rotor which indicates the direction the particle will follow. After a particle is launched from a vertex, the rotor is updated in a fixed deterministic way. The resulting purely deterministic walk shares many properties with the classical random walk, but there are also subtle differences. Within this theme I want to pursue these issues in detail for particular state spaces: Galton-Watson trees, free products of graphs, lamplighter graphs. Stochastic abelian networks (SAN). An abelian network can be defined as a network of automata, similarly to a cellular automata with the additional property that the automata can be updated asynchronously, and the final state does not depend on the order in which the automata processed their data. The previously introduced rotor-router walk is an example of an abelian network. The abstract theory of Abelian networks has been recently developed by BOND and LEVINE. A stochastic abelian network is an abelian network with transition function between automata depending on a probability space. A variety of models in statistical physics can be realised as stochastic abelian networks: Markov chains, branching random walks, internal DLA, activated random walks or stochastic sandpiles. Together with LEVINE, we plan to work out the basic theory of SAN and to tie these models into a common mathematical framework. The starting point here is the analysis of locally Markov walks.

An Abelian network is a theoretical model of distributed computation consisting of a network of processors that communicate with each other by sending messages to their neighbors in the network. An Abelian network differs from the usual models of parallel computation by the property that the order in which the processors consume incoming messages does not change the final state of the network, and hence the result of the computation. This means each processor can process its messages as fast as it can without the need of any synchronization between the processors of the network to ensure the correctness of the computation. This so called Abelian property of the network puts severe restrictions on the type of processors in the network, and while it is known that Abelian networks can for example solve some classes of optimization problems we do not know the full class of problems that can be solved with this kind of computation model.In my research I work mostly on one of the simplest examples of an Abelian network, the so called rotor-router model. In the rotor-router model there is only one type of message that can be exchanged between processors, and for each message it previously received a processor can send exactly one message to one of its neighbors. We think of the messages as particles that are traveling through the network. The processors send each incoming particle to one of their neighbors in a fixed prescribed order. The path of such a particle is then called a rotor-router walk. The Abelian property in this case says that it does not matter if we route one particle after the other through the network, or if all particles move simultaneously. Rotor-router walks exhibit many similarities with random walk, where the direction of the next step of the particles is determined randomly (for example by the flip of a coin). I am mainly interested in the differences of the two types of walk. As it turns out there are drastic differences if one looks at the long time behavior of the two walks on infinite networks, in particular on trees, that is networks that contain no loops.As one of the main results of this project, together with my coauthors Sebastian Müller and Ecaterina Sava-Huss, we showed that on a particular type of random tree, rotor-router walks return to their starting point infinitely often, as long as the average number of neighbors of the vertices is smaller or equal to 3. This is a drastic difference to the behavior of random walk on these trees. As it was already known that the random walk only returns to its starting point a finite number of times. This result will hopefully aide in understanding the long term behavior of rotor-router walks on different infinite networks like the important case of rectangular grids (which one can imagine as higher dimensional and infinite versions of a Manhattan-like network of streets). Whether rotor-router walks return to their starting points in a rectangular grid of dimension 2 or higher is currently unknown. While by a famous Theorem of George Polya from 1921 we know that random walk will not return to its starting point with a positive probability on a grid of dimension 3 or higher.