Some random walk model

Problem:
Random walks are initiated on an NxN grid. A walk may leave a trail. Different walks interact with each other on encounter.

Parameters (some of them, there -too- many options):
-Interaction takes place when two walks encounter each other, or even when a walk encounters the trail of another walk.
-The grid may have boundaries or be torus-like.
-The possible types of interaction between random walks are many (e.g. on encounter, alter -temporarily- the probabilities of a walk to move north, west, south or east).

Parallelization:
For n processors, the grid is partitioned in n areas. Every processor is assigned an area and is responsible for all the random walks which take place in it.

Parallelization's main problem:
The main problem with parallelization, is that 'cause of the different load between processors -at a given period in time-, a processor (say A) might get ahead in time, in comparison to a neighbor (say B) of it. Therefore if a random walk (say wB) goes from the area of B to the one of A, we have to remember previous states of the area of A in order to handle the interactions -in the past, as far as it concerns A- of wB with the random walks taking place in A.

------------------------------------------------------------------

The way to go (or, some way to go):
-Math: If it doesn't end up seeming too difficult, I may try to find somewhere, or somehow write down a ~probabilistic analysis of the model (with simple parameters), in order to check the requisites for a speedup -when going from a serial to a parallel implementation-.
Two books I'm ~checking out are these:
Reversible Markov Chains and Random Walks on Graphs (http://www.stat.berkeley.edu/~aldous/RWG/book.html)
Reversibility and Stochastic Networks (http://www.statslab.cam.ac.uk/~frank/rsn.html)
-Programming: an implementation (to be run on a cluster) using MPI, OpenMP or pthreads (or something else, God only knows).