the Model
The model discussed
in nearly all of this web site consists of a finite set I of identical
finite state automata
X = (Q,…) -- where Q
is the set of [local] states. Each automaton X is linked to an
irregular and unstructured set of neighbors Y by undirected
edges XY. The set of all edges is denoted
G. A function S
: I → Q, which associates a local
state with each automaton, is known as a global
state. The automata neighboring X
form the multiset G(X)
= {Y | XY in G} and their states form a multiset
of states SoG(X)
= S(G(X)) = {S(Y) |
Y in G(X)}. When X changes state,
the transition is defined by a function M
of its current state S(X) and neighboring states SoG(X).
When X is active,
it changes from s = S(X) to s′ = M(S(X),
SoG(X)).
It is assumed
that the graph (I,G) is finite, simple, and connected.
Thus, it is unlikely that (I,G) has a non-trivial automorphism.
This amorphous local structure (i.e., X may have one neighbor or
a dozen, all unnamed) is why the information communicated into X
is so vague. X knows only SoG(X). So X
does not know which neighbor has which state, just that so many neighbors
have a given state.
In some cases
it is convenient to assume that values for SoG are in Q.
In every case SoG has a finite range and infinite domain -- this
is necessary for the vertices to be finite-state automata.
In all cases, it is assumed that X reads SoG(X). Neighbors Y are not sending values to X, so there is no need for buffers at X. Of course, each edge XY represents a line of communication.
Time varies over the non-negative integers. Between times t and t + 1 a random set J (subset of I) of automata is active. Such activity changes the global state S to S′ where, for X in I,
S′(X) = S(X) if X is not in J, and S′(X) = M(S(X), SoG(X)) if X is in J.
This is an extreme
form of asynchronous activity/communication.
Serial activity, in which each J consists of exactly one automaton,
and parallel activity, in which J = I, are special cases
of this notion of asynchronous.
