Thursday, 26 April 2012

reference request - Algorithms for modeling asynchronicity in Asynchronous Cellular Automata

Most cellular automata are defined as being updated synchronously. I am interested in asynchronous automata, where they do not all have to update simultaneously. I am restricting myself to cellular automata on a graph (e.g. lattice) where the cellular automata is a FSM and all of the automata on the graph are identical.



I have seen some representations of asynchronously updated networks as synchronous updating of the automata with probabilistic updating of the cells, i.e. at each time step, each cell has probability $p$ of possibly updating its state.



I have seen asynchronous models where there is a single ordered list of the individual cells with each cell firing one after the other, with the same ordering maintained over multiple cycles, or with a different ordering being generated each time after all of the cells have fired. In this scheme, a cell is guaranteed to fire at most $3$ times in $2*n$ time-steps if there are $n$ total cells or at most $x+1$ times in $x*n$ time-steps ($x$ cycles of $n$ timesteps). (Example, it fires at time $n$ in the first cycle, at any time $n+s, (0 le s le n)$ in the second cycle, and at time $2n+1$ in the third cycle, meaning it fires 3 times during the $n+2$ steps from $t=n$ to $t=2n+1$.



I have also seen sequential firing, where at each time step a single cell is chosen to be updated, with no restrictions on firing all of the cells before starting over. This schema also averages a cell firing once every $n$ time-steps, but does not restrict it from firing more frequently.



Are there other better ways to mathematically model asynchronous cellular automata? What are the pitfalls and benefits of these particular schemes? I also agree at the outset that the type of firing scheme to be used for an asynchronous system depends on the particular system being modeled; I am asking for general answers or references for algorithms to model asynchronicity.

No comments:

Post a Comment