MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In 2-D lattice random walks by multiple drunks who can't step onto each other, mathematically I would just say the whole cellular automaton updates "at once".

But to simulate this on a computer, I need to perform computations in some order. This presents obvious complications.

Can anyone point me in the right direction with Google or the research literature? I'm sure I'm not the first person to stumble across this issue, but I don't know what vocabulary others have used to talk about it.

share|cite|improve this question
I think the keyword you want is concurrency: – Qiaochu Yuan Aug 13 '12 at 22:30

(1) You might look at simulations of the Game of Life, e.g., at the Wikipedia article:

There is also a method, applicable to other cellular automata too, for implementation of the Game of Life using arbitrary asynchronous updates whilst still exactly emulating the behaviour of the synchronous game.

(2) Following Qiaochu's suggestion, you might look at the literature on "concurrent writes," e.g., the CRCW parallel processing model. Here, for example, is a 1977 paper by Lamport (the L in LaTeX), "Concurrent reading and writing" (ACM link).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.