Effect of Noise on Long-term Memory in Cellular Automata with Asynchronous Delays between the Processors by Reza Gharavi and Venkat Anantharam

Effect of Noise on Long-term Memory in Cellular Automata with Asynchronous Delays between the Processors

Reza Gharavi
Venkat Anantharam
School of Electrical Engineering, Cornell University,
Ithaca, NY 14853, USA

Abstract

We consider monotonic binary cellular automata on the lattice as models of systems capable of long-term memory, that is, capable of admitting multiple invariant configurations. Long-term memory in cellular automata can be robust in the presence of noise, so that in a noisy environment the automaton may admit more than one stationary distribution on configurations. We examine the effects of asynchronous communication delays between the processors on long-term memory in cellular automata and describe when asynchronism can cause the erasure of long-term memory in the presence of noise. Our main result is a simple generalization to the asynchronous computation model of a deep result of Toom characterizing the invariant configurations of monotonic binary cellular automata that are robust to noise. Several qualitative consequences of asynchronism are illustrated through examples.