Ein zellulärer Automat ist ein Kristall aus Zellen, deren diskrete Zustände sich zeitlich verändern. Der Zustand im nächsten Zeitschritt ergibt sich durch eine deterministische Regel aus dem alten Zustand und dem Zustand der nächsten (evtl. auch übernächsten) Nachbarzellen. Eine Zelle verkörpert einen mesoskopischen Bereich eines physikalischen Gebietes. Alle Zellen sind gleich, evtl. mit Ausnahme von Randzellen.
Als Gittergeometrie verwendet man im allgemeinen quadratische oder hexagonale Gitter. Für das zweidimensionale, quadratische Gitter gibt es zwei gebräuchliche Nachbarschaftsdefinitionen: Die von Neumann-Nachbarschaft besteht nur aus den 4 nächsten Nachbarn, während die Moore-Nachbarschaft auch die 4 diagonalen Nachbarn miteinbezieht.
Mathematisch schreibt sich ein von Neumann-Zellularautomat wie folgt:
Dabei sind die 
diskrete Zeitpunkte. Die Indizes j und k
bezeichnen den Ort der Zelle.
Bei der Simulation auf einem Rechner können nicht alle Zellen gleichzeitig berechnet werden. Vielmehr gliedert sich der gesamte Berechnungsprozeß in einen
Durch diese Trennung wird sichergerstellt, daß sich ein Zellenzustand nicht während der Auswertung durch eine Nachbarzelle verändert. Die Reihenfolge der Berechnung ist beliebig, solange sie konstant bleibt. Dieses sequentielle Arbeiten kann man mit einem Warteschlangenmodell verdeutlichen:
Eine dosierte Asynchronität ergibt sich durch die Einführung eines Vordrängelbereiches (vgl. Abb. 3.1). Eine Zelle, die gerade abgearbeitet wurde, stellt sich nicht hinten an, sondern drängelt sich etwas vor. Die Zahl der Zellen, die sie überspringt, wird zufällig aus einem bestimmten Bereich ausgewählt. Die Zelle, deren Stelle durch die Vordrängelaktion besetzt wurde, muß sich hinten anstellen. Eine Definition einer dosierten Asynchronität ergibt sich direkt aus dem Verhältnis der Länge des Vordrängelbereiches zur Gesamtlänge der Schlange:
Für einen kompletten Zyklus muß jede Zelle zweimal bearbeitet werden,
einmal für den Berechnungs- und einmal für den Aktualisierungsschritt.
Unter einem Durchlauf soll im folgenden eine Sequenz von 
Schritten verstanden werden. Dies ist genau die Zahl, die im synchronen Fall
für einen Zyklus benötigt wird.
Auf Parallelrechnern können asynchrone Verfahren von Vorteil sein, weil die Synchronisation der Einzelrechner Rechenleistung kostet. Die Idee von asynchronen Automaten wurde deshalb auch von anderen Autoren verfolgt (z.B. [IB84]). Diese Autoren stellten auch fest, daß einige der Strukturbildungseffekte bei zellulären Automaten Artefakte der synchronen Steuerung sind, andererseits mit der asynchronen Steuerung Strukturen entstehen, die nicht mit synchronen Automaten zu modellieren waren. Bei den dort untersuchten Asynchronitätskonzepten ist nicht gewährleistet, daß alle Zellen im Mittel gleich oft bearbeitet werden. Dies erscheint jedoch notwendig und sinnvoll, wenn man raum-zeitliche Dynamik auf homogenen Medien simulieren will.
Dieses Problem tritt beim Warteschlangenmodell nicht auf.
Abb. 3.3 zeigt die Aufrufhäufigkeit 
der Zellen nach 500
Durchläufen. Auch bei hohen Asynchronitäten streut die
Zahl der Aufrufe nur in einem kleinen Intervall.
Einen Überblick über die Streuung gibt Abb. 3.2.
. WIRKUNG DER ASYNCHRONITÄT AUF DIE GEOMETRIE
