[ About ] [ Mission ] [ Services ] [ Funding ] [ Opportunities ] [ Open Tools ] [ Crosbie's Stuff ]

Cyberspace Engineers

Engineering Cyberspace!

On Arbitration

Introduction

If you're at all concerned by removing a central server then you'll be interested in a proposition that you don't even need to distribute the arbitration that the server provided, but that the distributed state can converge without strict co-ordination.

The following e-mail exchange (with permission) discusses this proposition of Christian Schladetsch (christian.schladetsch@gmail.com ) to Crosbie Fitch:

Hey Crosbie,

Your articles on 'cyberspace' are well thought out and eloquently written.

I have been involved with MMORPG server design and implementation for a number of years. The result of all this ongoing work and thinking: Every node owns every object. That is, there is NO notion of ownership.

Your model 'distributes the server'. Instead of one node 'owning' everything, in your model things are owned by various nodes about the system. If you hadn't noticed, the remainder of your design work largely revolves around the issue of ownership (and the related ideas of responsibility and interest). In reality, your model is better described as "server to peer" rather than "peer to peer" - peers serve other peers.

Ownership is bad. Distributing ownership doesn't remove the problem - it just distributes the problem! Ownership is a bottleneck. Ownership results in load balancing issues, and you end up writing a whole bunch of code that handles persistence, discovery, relegation, delegation, and the inherent problems associated with doing all those things in the noisy, messy real-world internet.

I know - I helped design and implement a system that resembles yours (see www.bigworldgames.com). In that case, the 'server' was a p2p network of Linux boxes. I left because I saw no reason to have a 'server of peers' - why not just cut out the rubbish and have a p2p game? The answer, as you know, is money - the publishers have no model for the type of game I wanted to, and am, making (i.e. a 'real' distributed one).

Anyway, back to the tech. So, what about arbitration? Who arbitrates if there is no ownership? You don't, of course - all nodes tend to reach a common opinion on their common objects. If one node thinks a given value is 2, and another 3, they both tend to 2.5. Too simplistic? Sure, but there's more to it, of course :). It is modelled as an 'organic' / 'knowingly inaccurate' / 'fuzzy' / 'blending' network that always tends towards a 'low energy' (highly consistent) distributed state. Think of a flock of boids: nodes are boids that 'fly around' a constantly changing 'centre of gravity'. I also needed 4D 'time frames', which are your garden variety frame-of-reference, but defined over time. I use events (which are effectively compressed state), but continuously push prioritised state as a 'background' process. Using events reduce latency, and the constant trickle (or gush) of pure state maintains cohesion. The system works with or without RPC's (events), but is more responsive with them.

The complete design is quite large, and includes a distributed RPN scripting language, hierarchical namespaces (including 'mount points' for remote nodes, a la NFS), and automatic replication via a hierarchy of 'agents' that serve the perceptions of entities. Current prototypes are looking good, but I don't want to say too much too early.

The main reason for this mail was to express the opinion that ownership is bad, be it on a single server, or on many 'servers'. When you remove ownership, really interesting things start happening.

Regards, Christian.

Thanks Christian,

Your points are very interesting.

It would certainly be nice to dispense with ownership handling.

However, I'm not quite that confident that the system would converge so quickly to some steady state (on a purely 'gossip' basis). Either one distributes arbitration/ownership, or one has to have a very good means of making duplicates keep in touch with one another (that scales).

Remember, it's a hard enough battle to convince the games industry that a distributed system can work, let alone a truly peer-to-peer one. Trying to wean people off the idea that 100% consistency is vital, is very difficult, and at least ownership tips its hat, whereas without it, credibility hits the floor.

I would agree with you that a peer-to-peer system without ownership can still provide an environment with entertainment potential, however, I think we'll have to slip that idea in via the back door. Even so, I do respect what you say seriously enough that in any designs I make for a cyberspace infrastructure, I will not hardwire-in the idea of ownership.

Another reason that sways me in favour of ownership, is that the drawbacks you mention don't impinge on bandwidth, whereas reconciliation/convergence without ownership seems to me to have a bandwidth overhead. If there's one thing in the future that will grow the least it's bandwidth. As I said in an earlier article, load up the CPU, RAM, and Hard disk all you like, if it saves bandwidth do it!

What I hope to do soon is start work on designing a 'standard' set of interfaces for a plug & play distributed/p2p games system. In other words, I don't intend to actually develop a MMOG engine (at least not in the near future), but to develop a relatively flexible way of bolting all the typical parts together. The very early stages (not much) can be seen at cyberspaceengineers.org.

Cheers,

Crosbie.

Hi Crosbie,

I'd just like to make some comments on your graceful reply:

> It would certainly be nice to dispense with ownership handling.

Not only nice, it is inevitable. Further, the first true p2p system will devastate the server-oriented systems. Don't get me wrong, I think there is scope for relatively small (and regulated and expensive), C/S systems, but most ppl (by defn!) will be in the 'wild west' of the massive (cheap/free/self-regulated) p2p systems.

I think a massively multiplayer game is like a large, distributed neural net. The comparison will make more sense shortly. The point here is that there is no notion of object or singleton (hence nothing to be owned) in a nn - instead, there are multiple levels of abstraction, with massive inter-connectedness, being processed simultaneously on a common set of nodes.

> However, I'm not quite that confident that the system would > converge so > quickly to some steady state (on a purely 'gossip' basis).

How fast is fast enough? This is cart before horse - convergence rate is a function of bandwidth. But that works both ways - we can use less BW, still maintain local cohesion, and remain further away from the general consensus. Or, we have fat pipes and can hover around closer to the consensus point.

I use boids to conceptualise this. Bandwidth can be considered a measure of the 'tightness' of the flock. More BW, more cohesion, less BW, less cohesion. Key point here is that the flock 'centre' is irrespective of the flock density. Furthermore, there will me 'flocks within flocks' - groups of agents will form mini-flocks within the larger flock, hierarchically.

This sounds like blather without saying something about the object model used. It is the object model that allows us to produce an 'in-between' representation of two arbitrary instances of a given object. More specifically, the object model allows us to produce a 'weighted sum' of a number of different representations of the 'same' object, and have the resultant object be coherent and meaningful.

With what framework can we start to talk about such 'blendable' objects? Clearly, scalars such as floats work, and conglomerates and n-tuples of scalars work piecewise. Issues only arise with enumerated types and references. How do we 'blend' between two distinct types? The other problem is topological - how do we 'blend' between two different connectivities? The answers are both simple and complex, and relate to the global nature of the system, including namespaces, entity-mind representation (hint: neural nets and fuzzy controllers), and the scripting system.

Hey, I never said it was simple. However, the overall architecture is.

Either one > distributes arbitration/ownership, or one has to have a very > good means of > making duplicates keep in touch with one another (that scales).

I have a means for maintaining cohesion. The model is simple enough I think.

Some objects have 'perceptions' and are called entities. Other objects, called Agents, exist to service the perception requirements for entities. Each perception (sight, sound, or abstract perceptions like boundary crossing or switches) has an associated geometry - lets use sight as an example, which has a cone. The agent needs to know about the salient features in a sphere centred on the entity it is servicing in order to efficiently service the cone of sight required by the entity (given that the entity can rapidly look around). The agent uses its knowledge of the 'perception bubble' around the entity to provide that entity with its cone of vision.

Now, another agent is introduced. They use their 'bubbles' to determine overlap, and negotiate the state of commonly perceived objects. Note that in this model, where only one agent has an opinion, that opinion is effectively absolute. Conversely, where there are no agents (that is, in regions outside the perception bubbles of entities), there is no opinion. This answers the question of the tree falling in the wood. At least in my model, the correct answer is "I have no opinion on whether it made a noise or not".

Given two agents, and their associated bubbles, we can form a 'super-agent' that has a bubble that at least contains the bubbles of child agents. We thus form a hierarchy of agents, which I collectively call the 'agency'. The agency has some interesting properties - the root agent (of a local node) represents the entirety of the perception space (of that node). It defines the 'event horizon' for a group of entities. It can also be used to rapidly answer queries like 'what is in this area?', and moreover does so in logarithmic time (this is guaranteed only if the agency is balanced in a tree sense). The point here is that the agency combines spatial organisation (hierarchy of bubbles) with the semantics of entities and nodes (the bubbles represent the perception limits of entities).

Now, you may be concerned about nodes having to maintain a coherent agency. Well, the truth is that the agency is used for replication and discovery - it itself doesn't need to be distributed! The agency is a function of the arrangements of objects, and is used to distribute objects. But since the agency is dependant upon the local datastore, it doesn't need to be distributed itself.

In order to include discovery of non-entities (that is, objects with no perception requirements), the agency is generated as a tree of bounding spheres. Some of these spheres are simple geometrical bounding spheres of a physical model (for rocks), other spheres are perception bubbles (for agents). Both types of spheres are used in the generation of the 'bounding sphere tree', and the agency is 'embedded' within this. Yes, there are a few orthogonal things going on at once here, which is why the design is a little abstruse at first, but is also why it will work ;) I have 'folded' a number of different design issues into one data structure, the bounding sphere tree (which is also used by physics for collision detection). After all, perceptions can be modelled as the physical interaction of geometry (Reinman was right - everything is geometry ;).

There are many more issues of course, but the agency and the sphere tree were the ideas I wanted to express here. They are the concepts that are used to drive replication and discovery (and a few other things besides).

An aside: what happens in those areas outside /any/ agency? By definition, 'anything and nothing' - no-one has any opinion about the contents of those regions (otherwise it would be within the bounds of the collective agency). So, what happens when an entity moves into such 'uncharted' territory? Undefined. What happens when an entity moves into uncharted territory, hence defining it (somehow), then moves out, leaving that area uncared again, then later itself or some other entity moves back into it? This is the persistency problem. I haven't fully addressed it yet, other than indirectly via the fact that all objects are reference counted, with a copy-on-write variation available to allow the concept of constness (useful to optimise RPC).

The issue here is that my model is 'perception-driven' - there is no 'objective reality' and no one 'correct view', hence no obvious place to store information about regions outside any agency. We would need an omnipresent entity (with infinite perception in all domains). The closest thing to this in my model is the conception of an 'agency of agencies', the hierarchy of all agencies on all nodes. Such a thing only implicitly exists, since the agency for a node is not required to be distributed.

On a philosophical note, this is similar to the real-world issues related to quantum mechanics and superimposed wave equations. Such equations only 'resolve' into a single state after being 'perceived'. The question then is 'who perceived the universe before sentience arose' (avoiding the question of 'what' perceives and how it does so). So, who is 'watching' the Universe? Or, what happens when no-one is around to see it? I haven't answered these questions yet (nor have the philosophical physicists), but they are not necessary to address before implementation.

For now, we assume that the root of the (local) agency defines the domain of the game-space, and worry about the horizon of the root later. Everything within the (implicit, distributed) 'global root' agent's bounds will be well-defined (at least, as well defined as anything else).

Some details on the actual distribution process are in order, although I realise this is far much more information than you want. Each node has a 'namespace', which is just like UNIX's network filesystem (NFS). All addressable objects reside somewhere in this namespace, and the scene graph itself lives in /scene. Each node 'mounts' other nodes into its local namespace, i.e. /nodes/123.23.67.78/scene is the local mount point for the scene graph perceived by the node at ip address 123.23.67.78. We maintain a list of such mount points for each 'relevant' node (relevance determined by agents). We then have a list of scene graphs that represent the perceptions of surrounding nodes. We combine all of these rep's with our own to produce our new rep, and tell those around us about the changes made (prioritised by perceived relevance).

Clearly, our representation of the opinions of those around us will be stale and mutually inconsistent. That's ok - each of those will in turn have local stores of our opinion, which is also stale and inconsistent with their local opinion. But by using a boatload of local cpu, we continuously produce a weighted average of all opinions (weighted by relevance, staleness, etc), and continuously stream our entire scene graph (prioritised by relevance, staleness etc) to surrounding nodes.

That's the general framework. The Devil is in the details of course, and in this design it is how to model NPC's. Since no-one owns anything, we need to distribute the processing of NPC's. You model the rabbit, and I model the rabbit. We need to produce and rationally talk about the 'average' rabbit. But rabbits are not scalar - they have mind. We need to produce and use 'average minds'. You model the rabbit as deciding to move left, I model him as deciding to move right. Oops, now what? Convergence helps somewhat, but we can't have NPC's having 'brittle' rationalisations - deciding to attack or not in one moment according to a small number of variables would be problematic. This is where nn's and fuzzy controllers are used in the design for two reasons: firstly, to avoid 'brittle' entity reactions (so they can be modelled within different contexts but remain somewhat cohesive), and for simple practicality - nn/fuzzy systems are a practicable way of modelling complex behaviour. There are implications of this, such as having to distribute the 'minds' of entities (hint: the nodes in each nn are objects).

I realise I have probably turned you back onto ownership, but be strong. I realise you may think I am crazy for proposing to have to share entire nn's with thousands, millions of neurodes (and all that just for one entity!). Nn's may evolve, but we can use systems similar to progressive meshes to stream them. This is my current research area.

Systems such as this will be made. How are you going to model your avatar when you log off? Best effort is to use a nn-like system that learns from 'watching' your behaviour, then trying to emulate it when left to its own devices (there is precedence for this, witness the creature in Black and White). There are some important (and, to some, scary) implications of this that I will not go into here. Suffice to say that I predict a system such as this will start self-organising in ways that we can't imagine, and it will be interesting to be able to change avatars and have a chat with yourself ;)

The point I'm trying to make here is that we need some form of nn/nn+fuzzy/nn+fuzzy+genetic system for AI, especially when ppl start realising that all entities, including ones that are occasionally guided by 'real' people, are effectively NPC's. Once you accept that, it becomes clear that entities' minds will need to be duplicated on each relevant node (so each node can run its own simulation). It all gets a little scary when we start talking about entities running their own, local, 'virtual realities' to test and compare plans and outcomes, but lets keep it simple at first.

> Remember, it's a hard enough battle to convince the games > industry that a > distributed system can work, let alone a truly peer-to-peer > one. Trying to > wean people off the idea that 100% consistency is vital, is > very difficult, > and at least ownership tips its hat, whereas without it, > credibility hits > the floor.

Tell me about it. I have vivid memories of heated discussions in front of the whiteboard: Them: "Huh? I don't get it - things will be all over the place! It's too unstructured. You can't have two nodes operating authoritatively on the same objects using different data! What about consistency? What about cheating!?". Me: "What stops you from shooting someone in the street? Anyway, the system is /organic/ - we recognise and embrace the inherent inconsistency, work it into the design and /use/ it - we make the 'problem' work in our favour". Them: "Uh-huh. But what about cheating? And who controls everything? It just wont work". Me: "Huh, OK. I resign"

All new ideas face incredulity and ridicule.

> Another reason that sways me in favour of ownership, is that > the drawbacks > you mention don't impinge on bandwidth, whereas > reconciliation/convergence > without ownership seems to me to have a bandwidth overhead.

Bandwidth defines the 'amount' of coherency, or the 'rate of convergence' (the 'togetherness of the flock'). Of course, there is a base level, below which the game is literally too incoherent to play (this is not strictly true). In any case, we can throttle the bandwidth as we like. At least all the information sent is useful and practical in-and-of itself. There is little overhead required to search for or flood 'owners', no 'overhead for delegating responsibility', etc. There is little 'noise', or overhead required, as is not the case when you have ownership.

> What I hope to do soon is start work on designing a 'standard' set of > interfaces for a plug & play distributed/p2p games system. In > other words, I > don't intend to actually develop a MMOG engine (at least not > in the near > future), but to develop a relatively flexible way of bolting > all the typical > parts together. The very early stages (not much) can be seen at > cyberspaceengineers.org.

I too am not developing a 'game system' as such, instead the framework for a distributed virtual environment. I have some very useful ideas that are completely general, such as the NFS-like object namespace, the object model, and the scripting system, that you may be interested in at least linking to on your site. They are all implemented and tested and well-documented. In fact, they serve as the basis framework for the Diploma of IT (Game Development) that I currently teach here in Brisbane, Australia.

I have taken up enough of your time if you have bothered reading this far, and I thank you for doing so. Sorry for writing such a long and unheralded reply - it may be clear that I am starved for peer review (pun intended) in my new academic position. Anyway, NRN, although anyone enjoys healthy discussion.

Regards, Christian.