ASYNCHRONOUS AUTOMATA NETWORKS CAN EMULATE ANY SYNCHRONOUS AUTOMATA NETWORK
Abstract
We show that any locally finite automata network 
with global synchronous updates can be emulated by another one 
, whose structure derives from that of 
by a simple construction, but whose updates are made asynchronously at its various component automata (e.g. possibly randomly or sequentially, with or without possible simultaneous updates at different nodes). By "emulation", we refer to the existence of a spatial-temporal covering 'local time', allowing one to project the behavior of 
continuously onto that of 
. We also show the existence of a spatial-temporal section of the asynchronous automata network's behavior which completely determines the synchronous global state of 
at every time step.
We give the construction of the asynchronous automata network, establish its freedom from deadlocks, and construct local time functions and spatial-temporal sections relating any posssible behavior of 
to the single corresponding behavior of 
on a given input sequence starting from a given initial global state.
This establishes that the behavior of any locally finite synchronous automata network actually can be emulated without the restriction of synchronous update, freeing us from the need of a global clock signal. Local information is sufficient to guarantee that the synchronous behavior of 
is completely determined by any asynchronous behavior of 
starting from a corresponding global state and given the same input sequence as 
. Moreover, the relative passage of corresponding local time at any two nodes in 
is bounded in a simple way by approximately one-third of the distance between them.
As corollaries, any synchronous generalized cellular automaton or synchronous cellular automaton can be emulated by an asynchronous one of the same type.
Implementation aspects of these asynchronous automata are also discussed, and open problems and research directions are indicated.
