Cyberspace
in the 21st Century
Foundations II
Ownership
Another
way of looking at distributed arbitration is to think about it in terms
of ownership (of state), i.e. if a computer is the owner of an item
of state, then it is the one that arbitrates over the true state of
that item. All we need to do is keep track of the current owner, and
determine who should own what.
By allocating ownership we are determining which computer should have
the right to determine the definitive version of the owned state. For
any item of state, which computer should hold authority? The principles
discussed earlier can be a guide. We want to minimize communication
and communication distance. Therefore, we want to keep distributed state
closest to those computers that are using it most, or those to which
it is of greater importance -- I'll term this 'Interest'. For example,
a computer modeling its player's avatar sitting in a vehicle is going
to be most interested in the state of the avatar and the vehicle they're
in. Computers whose players' avatars are in the vicinity and likely
to be affected, will be the next most interested. And so on.
We have to continuously determine which computer is most interested
in each item of state, and transfer ownership accordingly. Of course,
we have to stop this process from thrashing, so the benefits of ownership
have to be balanced against the cost of transferring ownership.
Expressing
Interest
As with other kinds of property, those most concerned with its upkeep
tend to be the best ones to own it -- or, at least, determine its maintenance.
Interest is a measure of relevance of an item of state to the player.
Things are more relevant the more they improve the quality of the player's
experience, i.e. for good modeling of their avatar's local scenery and
its denizens, presenting good images of the avatar's senses, and conveying
the player's influence over their avatar.
The player will have most interest in controlling the avatar and seeing
through its eyes. And the avatar in turn will have an interest in the
scenery, in fact anything that is in range of its senses. It will also
have a lesser interest in scenery that it might see shortly on its present
heading (if any), and lesser still, scenery that it might see if it
took any possible course of action available to it.
A computer will express interest in state according to the needs of
the player. How do you express interest? It could simply be a matter
of saying "let me know all objects in your database whose bounds
intersect with the supplied bounds", or perhaps "all objects
that may be visible from this viewing area". Or it could be "let
me know all objects where property 'type' equals 'avatar'. An interest
is a set of criteria designed to match a set of interesting objects
as opposed to uninteresting objects.
And to whom is this interest expressed? Well, you could express it to
the current owner of the state. Once you'd located the current owner,
you could set up a direct communications link and get updates to the
definitive state direct from the owner. Furthermore, if you're more
interested in the state than the current owner, you might well transfer
ownership.
However, if ownership is continually changing left, right, and center,
it's going to be a bit difficult for millions of computers to keep track
of who owns what. Plus, one may inadvertently create bottlenecks if
a popular item of state ends up in a computer with poor connectivity.
There may also be a fair bit of thrashing, if not squabbling, between
computers over ownership if several computers share a similar interest
in the same item. And what happens if a computer which owns something
goes offline? Bit of a problem eh?
There's evidently a need for some discipline and organization here.
In Essence,
That's It!
We now have the essence of a scalable networked games engine. Each computer
expresses interest in its player's avatar, and to this the avatar in
turn adds its own interests. The computer thus amasses all state of
interest, and when it processes the behaviors within that state, it
will be producing as good an estimate of that portion of the world as
every other computer in the same area. For all the state that it owns,
it will be computing the definitive state, and of that which it does
not own, it will both be computing estimates and receiving overriding,
intermittent updates (originating from the owning computers). Everything
else is just about fine tuning and making the system stable.
At this point we can make a conjecture as to the kind of result we're
going to be ending up with. With a very poor connection things will
be a bit jerky, as incoming state overrides are likely to have diverged
from local estimates. But, then, it would be difficult to do any better
with any other system. The better the connection gets, the less divergent
the incoming overrides will be -- given that they can be more frequent
and of greater fidelity.
Some will argue that you can't just allow state to be overridden, they'll
demand that you must perform some kind of smooth convergence to prevent
unsightly discontinuities. Well, there's always scope for tweaking,
but I'd say the sooner a computer accepts the 'truth', the less potential
there is for escalating divergence between computers. Anyway, the objective
here is to be simple and scalable -- we can work on 'complex and scalable'
another day. Hey! Some people would be delighted to explore a vast virtual
world even if over their 28k modem there was a bit of pop-up or impromptu
teleporting. Even so, apart from telling people to get an ADSL adaptor,
there are variety of techniques for coping with latency by addressing
these within the game's design.
Organizing a Distributed System
How
do we get a fairly egalitarian network of millions of computers to organize
itself so that each computer always has a fair share of the workload,
appropriate to the needs of the players it supports, and that it always
has the optimum set of communications relationships with its peers so
that it is assured of the most up to date information?
Well, I don't know about you, but whenever I see a system that is organized
I see a hierarchically organized system. Yes, perhaps all I have is
a hammer and everything I see is a nail -- you may well berate me for
my lack of lateral thinking. However, if there is a really neat non-hierarchical
way of organizing the distributed system we're ending up with, you'll
have to figure it out yourself or read a book to find it. Please, let
me know if you do. Until that time, I'll describe the hierarchical way
of doing things.
Changing Interests and Responsibility
Because
players' avatars will be mobile in the virtual world, their interests
in scenery will be continually changing. Hence each computer will be
changing its interests, changing the portion of the world that it holds,
and forming new relationships with computers that share those interests.
We end up with a dynamic or virtual network, one that is not necessarily
related to the shape of the physical network. Furthermore, computers
will be blinking in and out of this virtual network as players come
and go or their little brothers jealously pull the plug.
It's time to introduce another concept. This time it's 'responsibility'.
Every computer has a responsibility to do its best in modeling its portion
of the virtual world, along with keeping track of what it owns and doesn't
own. This is because ownership is a precious commodity granted to a
computer to improve its modeling of the things most important to it.
It's precious because there can only be one owner out of millions, and
ownership is effectively something that is competed for. Furthermore,
by being the key mechanism by which world state is arbitrated, ownership
is a vital aspect of the system, so we can't afford to lose track of
it (continuous broadcasting of ownership details isn't a solution either).
We must introduce a rule that if a computer is given ownership of something
that it is responsible for this privilege - it has some duties to be
performed in maintaining the security of this ownership.
The nature of responsibility is that responsibility is delegated. Ah
ha! Here we get to the hierarchical bit, and of course, in any hierarchy
there is always someone (or something, a committee, say) ultimately
responsible -- someone at the top.
This is how you can think of the transformation from a client/server
organization -- with the server owning all of its authoritative model
which is being replicated by the clients -- into a distributed organization
with the server delegating ownership to clients. So, in a way we still
have a client/server system. It's just that now, the server is no longer
a bottleneck, because it is highly likely that it will have delegated
all ownership until few other computers ever have cause to refer to
the server.
Let's just run through this again. The founding computer (perhaps more
than one) is the one that starts off owning everything. Then a new computer
will connect to this one and perhaps obtain ownership of parts of the
world that it's interested in. A subsequent computer will connect to
either of these two, perhaps obtaining some ownership. And so it goes
on. However, whilst ownership is freely passed on, responsibility is
usually just delegated. If delegated, responsibility can only be surrendered
back to the computer that delegated it. If responsibility is held at
the highest level then it can be transferred.
Perhaps a better analogy would be with freehold and leasehold of property.
We'll say that the people enjoying the use of the property are the current
'owners', who have leased the property from the freeholder. The current
'owners' could in turn sub-let the property to others who would become
the new 'owners'. However, whilst the lease can be sub-let ad infinitum,
ultimately ownership will always revert to the freeholder, i.e. the
guy at the top. And only the freeholder can transfer the freehold.
In the case of distributed state, an initial, small group of computers
are given freehold over various portions of the state. They will also
be the owners initially, but joining computers will lease ownership
of state from them. Any time a computer disappears, its leasehold reverts
up the chain, until it reaches the freeholder. Of course, if the freeholder
disappears, then the highest leaseholder can claim the freehold (until
or unless the original freeholder re-appears).
So, it is possible that a founding, root computer can be removed from
the system. As long as the root has given up all its ownership to its
delegates, then it can abdicate, leaving its delegates to become new
roots.
Keeping Track of Responsibility
Now
we could allow any computer to be responsible to multiple computers,
or we could say that a computer's responsibilities must always be obtained
via a single superior. The choice is between a single hierarchy where
computers are always inferior or superior to each other for everything,
or a multitudinous hierarchy where the relationship is dependent upon
the particular item of state concerned. In the latter case it would
be like working for many different companies simultaneously, and depending
upon the matter at hand, Fred could be Jim's boss on one thing, and
Jim could be Fred's boss on another.
I suspect that it may be simpler and easier to administrate if we adopt
the single hierarchy. In other words, the relationship between computers
as far as responsibility is concerned is absolute: either you are inferior
or superior. Of course, you can have peer relationships, but responsibility
is not conveyed by those.
Now the advantage in doing this is that it's simple to keep track of
who granted you responsibility for anything. If you're responsible,
then you know that there's only a single superior that you obtained
it from. This means less storage is used to record such details. It
also tends to make it fairly important that a superior is chosen carefully,
and must be selected such that it has a good match in terms of the objects
it is responsible for and how well they match the inferior's interests.
I would not rule the multitudinous hierarchy as unsound out of hand,
indeed it may be well worth future research, but I have a hunch things
will be simpler if we have the computer as our nodal, hierarchical unit,
as opposed to the item of state. I think I'm inclined this way because
it is computers that are the nodes that appear on the network, or disappear
from it.
________________________________________________________
Who's
God?
|
|
|
|
Features
