2. Locality

Our goal is to make everything about the update rule as local as we can. We will now make this more concrete by expressing what it is that should be minimized. In a discrete model, a site interacts with others that are connected to it, and when it updates its state, its new state is a function $f({\bf x}, {\bf x}_1..{\bf x}_n)$ of its own state and that of these other sites. We introduce the notion of a ``box'' that encapsulates everything that changes during an update, so that an update event is truly independent from all other updates. A box encompasses sites that update together, during the instant that they update. It is defined by the requirement that a change in the state of any site occurs completely within some box, and the update rule f can depend solely on the states of the sites within the same box. Our task thus becomes to make this box as small as possible. (Fig. 2)

Space is considered to be a graph, with sites being nodes and the possibility that two sites can interact being represented by an edge. Each site s has a state Q(s) associated with it. For simplicity, we will assume that there is a fixed set of locally-connected clusters of sites, and that any box that occurs encloses one of these clusters. A cluster S is a subset {s₁...s_n} of all sites which has the property that for any s_i,$s_j \in S$, there is a path from s_i to s_j that stays completely in S. The clusters must, of course, overlap if the sites are to interact with each other. A box is thus the event of a cluster changing its state: Q(S) is replaced with f(Q(S)).

The dynamics can be viewed as an update rule f combined with a schedule of boxes. For simplicity, updates can be considered instantaneous, since boxes are all self-contained. However, there are many cases where it is undefined whether one box occurs before or after another. Therefore, this schedule only needs to be partially ordered. It is a preorder, a partial ordering that allows multiple distinct events to be simultaneous. Not all possible schedules are allowed, however. At least two conditions are necessary for two boxes to be independent of each other rather than be part of the same box:

$\bullet$

Nondeterministic in time. The occurrence of one may not be deterministically related to the occurrence of another in the schedule. For example, if we have two clusters A and B, we may not do things like specify that B must update immediately after A; for this to happen, the sites in $A \cup B$ would all be considered enclosed by a single box.

$\bullet$

Homogeneous update. Likewise, we require the update function f to be homogeneous in time, a function only of the states of the sites in the cluster: the same update function must be applied on each transaction. We do not allow a cluster to do a ``no-op'' (the identity function), for example, waiting until some other cluster has updated.

We do allow the specification of statistical properties - for example that the average time between transactions is the same for all sites, or that the average number of neighbors has some variance. The idea is to constrain the geometry and time in the model to be ``spacelike'' or ``timelike'', while ensuring that the ordering of the boxes remains fundamentally nondeterministic and allowing the geometry to be irregular, so that synchronization and detailed knowledge of the geometry are not relied on.

2.1 Implications

An update potentially makes use of the state of every site in a cluster, and these depend on previous updates that involved those sites. Each site can be a member of several clusters, so for any set of clusters that overlap, the boxes that enclose them must be fully ordered in the schedule; they cannot be simultaneous.

We could imagine a site ``remembering'' the states of its neighbors by incorporating them into its own state. These states could then be used later without being enclosed by a box. However, as the schedule is nondeterministic, between the time a neighbor's state is remembered and the time it is used, that neighbor may have undergone other updates and changed its state. The remembered state would be out of date. Remembering states is therefore unreliable.

Note that models with global synchrony require that all sites have updated once before any one site updates again, and f is a function of the states from the previous time step, before any of the updates of the current time step have happened. So in synchronous models, the update rule itself may be local in space, but by this more stringent requirement that also takes time into account, the box is infinite in size to encompass all the sites during an update.