Abstract

This paper studies the propagation and crossing of signals in cellular automata whose cells are updated at random times. The signals considered consist of a core part, surrounded by an insulating sheath that is missing at the side of the core that corresponds to the direction into which the signal moves. We study two types of signals: (1) signals by which the sheath at the left and right sides of the core advance first in a propagation step, followed by the core, and (2) signals by which the core advances first, followed by the sheath at its left and right sides. These types naturally arise in, respectively, Moore neighborhood cellular automata with semi-totalistic rules and von Neumann neighborhood cellular automata with symmetric transition rules. The type of a signal has a profound impact on the way signals cross each other, as we show by the construction of one signal of each type. The results we obtained should be of assistance in constructing asynchronous circuits on asynchronous cellular automata.

Movies:
Colors are used to denote the states of the asynchronous cellular automata (rather than the black & white patterns used in the paper):

0 = blank
1 = pink
2 = red
3 = blue (not used in the first cellular automaton)
4 = purple (not used in the first cellular automaton)

Below are simulations of crossing signals on Asynchronous Cellular Automata (ACA). No specialized devices (configurations) are used for crossing.

Signal of type (1) on a 3-state Moore neighborhood semi-totalistic ACA (1.5MB.wmv) (4.5MB .avi). This ACA uses a random sequential updating scheme, meaning that at each time step one cell is randomly selected for update. Two neighboring cells are not allowed to undergo transitions simultaneously. Signals of this type negotiate passage through the crossing by extending and withdrawing their antennae. This always works, without deadlock, since their antenae (at their sides) are extended before their core (in the center) is.
Signal of type (2) on a 5-state von Neumann neighborhood ACA (1.2MB.wmv) (3.8MB.avi). This ACA uses a probabilistic updating scheme, meaning that cells are updated at random times. Two neighboring cells may undergo transitions simultaneously. Simultaneous updating of all the cells (pure synchronicity), however, is not allowed, because it may cause oscillating configurations when two signals are negotiating for passage through the crossing. Signals of this type try to negotiate passage through the crossing by extending and withdrawing their antenae, but this does not work if their cores have already progressed too far, so in that case they fuse on the crossing and split up again.