[MUD-Dev] cellular automata as universe models

[James Wilson]

Hi all, I've been thinking about how one might use cellular 
automata to model a universe. By 'cellular automata', I mean a
set of nodes where a given node's state changes are completely 
determined by a set of neighboring nodes. (The research community 
uses the term a little more carefully than I do. Purists, please forgive 
my insolence.)

The application to a virtual universe might look like this:

	nodes represent spatial locations.

	state changes of any objects within those locations are changes 
		in node state.

	nodes are neighbors of spatially proximate nodes.

the CA constraint that state changes are determined entirely
by a node's current state and the states of its neighbors means 
that a node may not directly alter the state of a non-neighbor node.
For instance, if the world graph is

	node A <--> node B <--> node C

then events in node A cannot directly impact node C. (They can,
however, propagate into B and thence into C.)

Note that this constraint is orthogonal to one's execution model, i.e.
one can implement an event-based or a polling model inside each
node to determine state changes. In this post I am writing about
event-based examples, but all can be adapted to polling systems
as well.

The advantage of this system is that synchronization *might* become 
trivial; since each node's state changes only depend on neighboring 
nodes, one must only synchronize overlapping sets of nodes. The system 
as a whole may remain mostly parallel. One might be thus able to rule out 
deadlocks entirely by synchronizing inter-node access properly. 

For instance, off the top of my head, suppose you have some set of worker
threads operating upon your node graph. As threads become available,
they scan the graph for nodes with pending events. (Alternatively, events 
in a queue can be associated with a node, which the thread then tries to 
lock as follows.) If a node, A, has a pending event and is not currently
locked, the thread then checks to see if all of A's neighbors are unlocked; if
any are, the thread gives up on A (and its event) and tries another node.
Otherwise, if all of A's neighbors can be locked, the thread then proceeds to
execute whatever needs to be executed within the scope of node A. (The 
issue of event duration, which I harp upon so much, is of course still with
us.) The thread then unlocks the nodes and tries again. In this system,
deadlocks are (I think) impossible; threads do not block waiting for locked
nodes, but move on to other pending events under the assumption that the events
which require the locked nodes will be serviced promptly by some other thread
when they come free. (This is analogous to something I suggested a while back
in the latest lockless-db exchange: if one can know beforehand the set
of objects an event will operate upon, one can lock them all before the
start of the event and free them at its end. The CA constraint guarantees 
this knowledge.)

The CA constraint does introduce some obstacles to user scripting. First,
objects cannot simply save references to one another,  as the objects might
then migrate into remote nodes, in which case  access would violate the CA
constraint (and thus break any synchronization model that relies on it). Also,
inspection of objects must be  confined to the node which is the site of the
inspecting event, and its direct neighbors.

For instance, this would rule out a script which accessed every player
object in turn (assuming the players are not all in the same node). Also
illegal would be a (naive) implementation of a homing device which is
connected by a reference to a remote tracking object. However, both of
these can be implemented in a CA model by propagating events through
the node graph (assuming the graph is connected). Possibly there are effects
which cannot be emulated by propagation, and there is an efficiency
consideration - direct references are much more efficient than broadcasting
messages to lots and lots of nodes. Another problem would be handling
objects so large they span multiple nodes - does a gigantic warship move
atomically from node to node, or does its prow come in first, then its 
foredeck, etc? (The solution to this might have some interesting ramifications -
perhaps fog in one area would then envelop different portions of the ship
at different times as it moves into the foggy area.)

As a 'realism' constraint, there is a real-world parallel; namely, information
and thus causality cannot propagate faster than the speed of light, so there 
is no instantaneous causality across remote areas of space. (Quantum
correspondences don't let you out of this either, unfortunately, but that's
highly OT. *heh*) Perhaps one could loosen the correspondence between
spatial locations and nodes - allowing mobile nodes, wormholes, dynamic 
changes to the node graph, and the like - without breaking the underlying
synchronization model. 

To be perverse: at one extreme, each object could be a single mobile node, 
but this would obviate any gains realized by serializing groups of spatially
local objects, and seriously complicate the process by which events inspect
their environment.. At the other extreme, nodes could be so large that
serialization of their state changes would be tantamount to serializing the
whole db, which of course is an option but one I am interested in avoiding. 
The useful case is where nodes are large enough to conveniently serialize
db state changes while not terribly inconveniencing script writers.

The node and its neighbors would have to be understood as the 'environment'
available to an event, and script writers would need to work under the
assumption that information from outside this local environment is unavailable. 
This is essentially the same constraint that human users of VR environments
(and real world systems) operate under; that is, one's responses are determined
by one's internal logic (mind, instincts, physical laws, etc) and one's
immediate environment (through sensory data or physical interactions). I'm not
sure how this constraint could translate into a scripting system, however. One
would need to remove direct references and proxy all object accesses through
the environment; how could this be done efficiently?

James