The Rotor Router Model (Propp Machine)

The rotor router model is a non-random random walk. Instead of hopping to a random neighbor, here is what you do in the rotor router model. Each vertex is equipped with an arrow pointing to a neighbor. Each step, you follow the arrow. Whenever you leave a vertex (following the arrow), the arrow is up-dated to `the next' neighbor (according to some pre-specified order, but think of `clock-wise', if you prefer).
Through this mechanism, in the the rotor router model each vertex serves its neighbors highly equitable (in fact, better than in the random walk model).

In the lecture, I will make this description precise and compare the rotor router and the random walk model in a number of different aspects. Partially, I will use slides from a talk I will give in Kiel next Friday.