Cyberspace in the 21st Century: Part Six, Scalability with a Big 'S'

Interesting Times

Well, a fair bit's changed throughout the year 2000. We've seen the rise and plateau of Napster. We've seen the advent of viral marketing as a viable technique. People are beginning to recognize that being open isn't such an unsound business practice as it might at first have appeared - Open Source is now a creditable development strategy. Microsoft is getting worried, I mean interested in Linux. Intel is getting worried, I mean interested in peer-to-peer computing and distributed processing. Meanwhile Cisco is rubbing its hands together in glee - though I understand that we may yet see a revolution in the use of domestic wireless routing devices. Perhaps Cisco is interested in that area? Power seems to be returning to the people…

Interesting times eh?

Why is all this happening? It's the Internet. The Internet with the Web as its visible face makes the world a small place. Traditional business models may have been the first to be applied online, but more suitable models are beginning to arise. With a small world, with the miniscule amounts of friction present, competitive strategies that rely on having enough time for an inertia burdened business to adjust to a change, simply can't cope against lightweight individuals and co-operatives. Cut out the middle man. Deal direct. Co-operate. Do your business in full view of your traditional competitors, because it doesn't matter what they see, they haven't a hope of catching up in any case.

This applies to the games industry too. The music industry is in crisis, the movie industry may be next. The software industry as a whole is undergoing its own revolution. Digital content is simply too mobile to remain protected. Information really does want to be free. Games are no different. The players want them for nothing. That's not to say that players won't pay if they have to, in fact most players are in perfect accord with the idea of the games developer getting a fair reward for their labor, it's simply that games developers, just as musicians, should keep an eye on the writing on the wall. Things are going to change. If you want to be prepared: learn Linux, buy an Indrema, set up a website, join an Open Source team.

In the not too distant future, the player will be paying your wages direct.

Games and P2P

How does this industrial revolution relate to cyberspace?

Cyberspace is simply the logical evolution of peer to peer systems such as Napster, Gnutella, FreeNet, MojoNation, FreeHaven, etc. While the latter and others will be concerned with distribution of static content (music, images, movies, software, etc.), sharing of storage and sharing of processing resources, cyberspace will be the system that combines elements of all these together to distribute dynamic and interactive content. It's the low friction way of delivering digital content: anyone can put something in one end and it's instantly available to anyone else. Instead of treating digital content like a tangible commodity that can't be readily duplicated, and one that requires a one-to-one exchange mechanism, we instead replace it with a system that treats all content as inherently manifest. It's a bit like the Borg in Star Trek - any thought that occurs in one mind is available to all.

Ready for Success

So in terms of games, cyberspace is a platform that supports many games, but for each game there is no concept that the number of players is limited. Each game is a persistent environment that expands in proportion to the number of players playing within it. If it's fun for one, it's fun for one thousand. If it's fun for a thousand, it's fun for a million. It's a shared environment, a virtual space, a sandpit in which any number of people can have fun. The games designer figures out the rules, creates the style, sets the theme, provides some suggestions for objectives, but largely the players make their own fun.

This is where the peer-to-peer paradigm makes its entrance; the distributed systems technology, that comes into its own by ensuring that whatever one player does is visible to all the other players in the vicinity. Not only are we distributing content, we are also distributing change in that content. This is what all multiplayer games are doing. It's just that the current approaches in the form of client/server and crude peer-to-peer systems aren't sufficiently scalable for billion player games. Truly scalable systems design is what I'm trying to get across to you in this series of articles. Whether your game attracts a million players or only a hundred, if your design is scalable at least you can cope with a success. Imagine if you had a good idea for a multiplayer game and it was so popular it ground to a halt at a hundred thousand players. What a bummer eh? Instead of driving away in a Ferrari you end up with a major administrative headache. No problem you say, we just create parallel instances of the game in order to balance the load.

I'm wondering if this is really a matter of convenience rather than evidence of sound design. What would have happened if the web ground to a halt at 10 million users? Oh, no problem we'll just create multiple webs. We'll have MSN, AOL, Compuserve, Reuters, FreeServe, Yahoo, IBM, etc. A hundred different webs each slightly different, but with a heck of a lot of overlap. It wouldn't just be "Oh shall we get the .net as well as the .com domain name?", it would be "Should we have a presence on MSN as well as AOL?"

Here we have a potential success story, a game that's so good 40 million players want to join in. That's 40 million Pentiums beavering away. If we can produce a system that copes with 10,000 players why not 10 million? Let's not be so lazy that we allow a design limit that creates a ceiling on our success? It is better to get a dollar from 10 million punters for a little extra design effort, than it is to charge ten dollars to 100,000 players with all the admin costs of spreading players across different shards. Why do we ever produce a piece of software with the knowledge that human intervention will be required if it's too successful?

I don't know about you, but I'm into the idea of 'fire and forget' software. I want to produce a single package of software capable of supporting a billion players that will never encounter problems with support costs, additional infrastructure, software updates, maintenance, telephone help lines, etc. One game - a billion players - zero admin. What could be simpler?

So Many Players - So Little Time

I know there are people out there who have incredible difficulty understanding why on earth a game would benefit from even a million players, when surely a thousand is plenty? Check out the Star Wars Galaxies discussion boards for a discussion where prospective players of the Star Wars online game are even now questioning the wisdom of having multiple Star Wars galaxies, i.e. several instances of the same game each with tens of thousands of players. Instead of admitting it as a technical limitation, the excuse is that there's not enough content to support a greater number of players in a single game. Blimey, a whole galaxy, and they can't squeeze a few million players into it?

Space is mind-bogglingly big as Douglas Adams once wrote, and that's Big with a big 'b'. What I'm going to spend the rest of this article talking about, is how to engineer scalability into a distributed modeling system. And that means Scalable with a big 'S' - making sure that no part of the design grinds to a halt as the numbers start getting big with a big 'B'.

Threats to Scalability

How do we know a threat to scalability when we see it? It's any part of a design that exhibits an assumption concerning a 'reasonable use' and that is embodied as some kind of absolute limitation. Any time you see people storing years in a single byte, filenames in 16 bytes, directories in 256 bytes, any kind of fixed limit like that is an obvious candidate.

However, scalability limits can manifest themselves in more subtle ways. For example if you are imagining a system that is likely to be used for applications with numbers of simultaneous users on the order of hundreds, then an operation that takes an amount of time that has a squared relationship with the number of users is a big problem. It might be 100ms in the case of a hundred users, but 400ms for two hundred - not too bad. However, if you go up to ten thousand users it takes a quarter of an hour, and for a hundred thousand users you have to wait longer than a day.

Even a linear relationship can be a problem. Say a system, in some reconciliation process, consumes a certain amount of bandwidth from every connection of every connected player. It might be just one bit per second, but the system will grind to a halt at around 56,000 players (probably much sooner). This is the main reason why client/server is inherently non-scalable. If you require high bandwidth from each player to a single server then at certain number of players (about 5,000 say) you begin to start warping the network infrastructure - even if you do have a server that's powerful enough to cope with the workload. Sure, ask for half a dozen T3 connections to be piped into your server room, you might end up waiting a few months while the network warps into shape to accommodate you - unless of course, you just happen to site your server room near a decent backbone…

The only relationship we can really even countenance is a logarithmic one, i.e. linear growth in overhead in proportion to exponential growth in players. For example, if you need one more bit in a particular data word for every doubling in user players, a 32 bit word allows you to cope with 4 billion players. But even then, nothing's that straightforward in the real world - you have to watch out for noise, spurious anomalies, and nefarious phenomena. Sod's law puts paid to back-of-the-envelope calculations that should work in theory. And where Sod's law finds the job too hard, there's plenty of hackers to fill the breach.

So if you honestly think that "We'll never get more than about a hundred players congregating in the same place" - hah!

Of course, you can make assumptions about what should happen in practice, but you still need to cater for what shouldn't, because it will happen. The trick is in ensuring that the system degrades gracefully and appropriate to the situation. If there simply isn't enough bandwidth to support a riot, then only those participating in the riot should notice any reduction in fidelity. Ideally players would still see the behavior of their closest opponents, but those further away in the crowd would simply be modeled from infrequent samples. This brings me back to the idea of prioritization as one of the solutions brought to us by the 'best effort' philosophy. When perfection is impossible, the best is good enough, and certainly better than failure.

Things Change

Hand in hand with scalability goes adaptability. Players are pretty unpredictable blighters and they can change in behavior from day to day or even second to second. Players are human beings (well most of them) and as we all know, human beings are pretty clever when it comes to understanding their environment - their lives have depended on it - probably why intelligence evolved in the first place. Any system has to be almost as intelligent in adapting to its users as its users are in adapting to it. One thing that the architects didn't figure when the designed the millennium bridge over the Thames in London was that its users aren't all independent entities. Even subtle behavioral cues can be enough to get people to act in concert (causing a bridge to oscillate wildly in this case). With multiplayer games it's much worse: we tend to have to presume we're dealing with players deliberately setting out to stress the game to breaking point.

But, there's more to change than just the players. We also have computers winking in and out of the network, coming back with bigger hard disks, CPUs, and ADSL connections. Considerate ISPs might realize they can attract more subscribers if they donate some spare capacity by making nodes out of some of their Linux boxes.

Even the network itself is in a continuous state of flux, in terms of effective topology as well as traffic, with consequent unpredictable fluctuations in bandwidth and latency. Sometimes a network might undergo a serious problem when an earthquake strikes a key set of points. A satellite might be zapped by aliens.

In general, anything could happen to pull the rug out from under the system. However, it must adapt. We can't allow a game to go on for two years that builds up to a 100 million players many of whom may have made a considerable investment of effort in building towns, cities, empires, relationships with other players, spent a wodge of money on certain weapons or resources, only for it to fail when someone accidentally pulls a plug. "No worries everyone - we'll restart it on Monday!" The outcry might trigger a civil war!

Hopefully you'll notice where scalability and adaptability come into play in designing for a billion players.

A Self-Organizing System

Each player interacts with the system via a user interface running on a piece of software I call the front-end. This front-end interacts with a back-end service operating as a node in the distributed system. It is the back-end that performs the modeling of the virtual world and does its best to communicate the modeling it does with any other nodes that may be interested and to receive their communication of the modeling that they are doing. The process of managing the relationships and responsibilities also falls to the back-end.

Each node can be considered to correspond to a player's computer. However, this is not necessarily the case. It is possible that multiple front-ends may exist on the same computer - a split screen on a console for example. Alternatively, multiple front-ends may be running on different computers (mobile, handheld devices) and they could all be talking to the same back-end. Multiple back-ends may also exist on the same computer, e.g. one node acting in a fully interactive capacity and operating from a fast hard disk, one node acting in a back-up capacity operating from relatively slow near-line storage, and one node might even be operating in a read-only capacity from a DVD-ROM jukebox. But, there might be plenty of CPU capacity for them to all operate on the same computer.

Anyway, for the time being we'll consider that we're operating on a basis of 'a computer is a node'.

Let's assume we know all about how to uniquely identify computers/nodes, objects, players, and anything else. We don't have a problem utilizing locally available storage (hard disk) to store as many objects as may interest us now or in the near future. We don't have a problem utilizing locally available processing (CPU) to execute as many object methods and modeling services as we can. We don't have a problem sharing the CPU between the player's visualization application (3D renderer) and the modeling back-end. We don't have a problem exploiting all available communication channels to get in touch with other nodes, nor do we have much difficulty with the idea of how a new node goes about discovering a fairly good node to initiate contact with.

The key problems we're left with are these:

There is of course the issue of security, and although at first glance there may seem to be an insurmountable security flaw in any system that utilizes client-side resources, let's remember that we're dealing with two related, and very difficult problems here: a scalable distributed modeling system, and a secure one. Let's not give up on one, just because we can't see how to solve the other. Putting it metaphorically: if we're trying to build an airplane, let's not give up just because no one's invented parachutes yet. And you never know, once flight becomes popular, the unthinkable idea of flying without a parachute might just end up being quietly forgotten.

If we first understand how a system can be scalable, then we can qualify ourselves to be in the position of understanding how it can be secure.

Reviewing the Object

Before we go any further let's discuss what we're distributing.

If you want to have a comparable idea of the sort of thing I'm describing then JavaSpaces would be a good term to plug into your search engine. It's an evolution from Linda - based on David Gelernter's tuple-space idea.

What the games programmer sees in terms of objects described in a programming language and what goes on under the hood of the distributed system that supports it can be somewhat different. Imagine a language much like Java for the time being. However, common to many virtual machines, one isn't necessarily tied to a particular language. Even if the virtual machine is object oriented, one can develop languages appropriate to particular types of application - games for instance. I'm envisaging such a language tailored to games, but to keep things simple for the time being, we only need to appreciate that the storage of our objects can be managed irrespective of the programming language and virtual machine that manipulates them.

The Object Store

In our object store we keep a record of the class inheritance hierarchy and the details concerning the definitions of each classes' methods (or properties). The class is an object as well as a template that governs the form of instances of objects of the class. Each class defines methods which either execute code or manipulate corresponding state variables. All objects (including class objects) contain details of their ownership, e.g. last known owner (lease-holding end-user), last known freeholder.

All we need to distribute then are objects and the classes that define them. The objects consist of one or more values (Figure 2). These values are held within method slots, and a value represents either an operation or a property. Each operation consists of a string of byte codes and each property consists of a value. However, as operations are the same for each object these only appear in the class object - that special object that defines the class operations and default values for each property. In this way objects will only contain values that differ from the defaults.

As you can see (Figure 1) a class object may inherit from another class object. In this case, the derived class object only contains operations or properties that differ from those in the base class. All methods are implicitly virtual. Note though that only single inheritance is supported in this scheme (it'll do for starters).

Object Layout

When we come to implementing our object database, we're probably going to end up with something like Figure 3. I won't say it's going to look exactly like that, but there will be some similarity.

Each object will need to contain information sufficient to track down its class definition (inheritance, class methods, property defaults, etc.), i.e. both the details of the class and a good idea of which node to talk to in order to obtain those details. We also need some information to give us an idea of how up to date we are in order to specify what updates we're interested in. We can use a system of revision information which may be as simple as a revision serial number, or it may involve a timestamp of some sort, or even both. Note that time on the Internet is a problem all by itself.

The properties of an object may be able to be updated independently of other properties, or they may need to be marked as coherent with other properties. Some may even be marked as not needing updating at all, e.g. properties which are always the result of computations alone.
It's likely that we'll need to record both the locally computed (predicted) value of a property as well as the latest news (received indirectly from the owner) of its arbitrated value. This allows us to pass on this news. We'll also need to know if we own the object or not, and otherwise, who does (or the last known owner).

Note that the local storage requirement of an object will be larger than the amount of data required to transmit some of its details. There are many ways of optimizing the communication overhead. For example, if the receiver communicates the extent to which it is up to date, then the sender only needs to send more recent information.

In case you're concerned about the local storage requirement, recall that one of our guiding objectives is to prioritize the reduction of communication overheads over and above any reduction of storage or processing overheads.

Values

Values are either immediate values or references to larger data elements that are held in an appropriate repository adjoining the object store. Note though that all values are immutable (constant), the object (including the class object) is the only mutable entity that the system deals with. Series of values may be created, but once created they remain constant (until they get destroyed upon a zero reference count).

This allows us to easily refer to large amounts of constant data that many players already have. For example, it is likely that someone could produce a DVD-ROM of a snap-shot common textures and geometry that exist in the system. All objects that use these only need to transmit the references to such constant data. Of course, if the node doesn't have the data available then they must download it, but this can be done at a relatively low priority (a lesser level of detail object is likely to be sufficient in the interim).

Note that large values may only be deliberately destroyed if they have never been communicated outside the node. A similar policy exists with respect to IDs for objects, series, etc. Local IDs can be used for greater convenience until something is communicated outside the node, in which case globally unique IDs must be used. NB they can still be tokenized in cases where they are mentioned several times in a message. Of course, intermediate values that arise within a computation do not need to be stored. It is only when persistence is required that values need to be written to persistent storage.

Operations

Some operations of an object may be marked as to be executed upon a particular standard event, e.g. when a new object instance is generated, or when the containing object arrives at a node. I doubt it would be prudent to allow an operation to execute upon being flushed from the cache, however, as the object is implicitly of least interest, and any further behavior on its part is unlikely to be useful.

Aspects of Distribution

To permit the game code to be aware to some extent of the distributed nature of the underlying system, there may be a need to mark some operations as operable only if the object is owned, or not owned. In addition, some operations could be marked as auto-forwarded, i.e. the call is forwarded to the owner of the object and executed on that object, with the result returned. These could be blocking (wait for return), or non-blocking (result ignored). Such things may require different underlying communications strategies, but as long as the game developer understands what they're doing, such low-level controls may come in handy sometimes, e.g. in achieving synchronization where it's critical.

Persistence

Remember that the persistent storage system is a limited resource. A policy similar to 'least recently used' will remove objects or values when space runs out. In this case it will be an 'of least current interest' policy. When a property value is missing the class default for that property is used, and null is used for missing values resulting from a computation (rare). When an object is missing, a default instance of the same class is used. When a class method is missing the base class' method is used. Ultimately a null value is used. Generally, the best default is used in the event of missing information. Whilst one could create diagnostic tools to catch such events, there really isn't any point in alerting the user or trying to do any recovery, because these are likely events and there's no remedy available in any case. You can't restart the system or perform a roll-back. You simply have to assume that such missing data only occurs in relation to particularly uninteresting objects. For example, the lush mahogany texture map may be missing, but then the default wood texture may be used instead. Naturally, it is up to the games programmer to utilize the inheritance facility to create a cascade ofever more sophisticated detail, i.e. define how a simple object property of wooden, is part of a hierarchy that at some point may be flat-shaded brown, but at another point is highly polished mahogany. Given objects could have their base properties implicitly prioritized for distribution over and above their more derived properties, this can help reduce distractions caused by degradation in simulation fidelity of objects at the periphery of ones area of interest (it's better for a distant animal to appear of the correct color, than an arbitrary one, if it's fur details were too big to download fast enough). Similarly, it's better for a distant vehicle to have its general vehicular properties downloaded before its specific properties (behavior, damage record, cargo, current operating parameters, etc.).

Ownership

All nodes that own objects get to own them because heuristics determined them as the most suitable nodes to own them, and these heuristics obviously have to be contrived to encourage ownership by nodes that are interested in the objects and have enough resources to do a good job in modeling them. In other words, all the glitched modeling that occurs is very likely to be related to uninteresting objects, and thus unowned objects. Therefore, we can expect that such erroneously modeled objects will be overridden by incoming updates of the objects' state from the owner.

Communication

Remember, whilst most systems have a hardwired distinction between properties necessary for the visualization of an object (position, orientation), and those necessary for the behavioral modeling of an object, communicating the former (with dead-reckoning), and not communicating the latter. In our case this distinction is not hardwired, but determined by the game's designer, moreover, it is done on a priority basis. This means that if the behavioral properties are distributed on a lower priority than the salient properties (position, orientation), then at least these salient details will be communicated. When the behavioral properties get to us (as the object becomes more interesting) we obtain effective dead-reckoning. Perhaps not that kind of dead-reckoning where the server is aware of the client's prediction algorithm (and duplicates it) and then only needs to advise the client when its estimation diverges too much. Nevertheless, as both parties in our case are expected to perform the same modeling there is still some potential for prioritizing communication according to the computed value's distance from the arbitrated value, though the game designer would have to determine the precise relationship if any. Perhaps this would best be left as an empirical research exercise.

Perhaps I should note here that when you have a huge virtual world, it gets so big that the client software cannot be forewarned of all the content that is likely to come its way. A player can't be required to upgrade their software just because someone elsewhere has invented a new vehicle type. We have to design the system such that the client can obtain information about how to model a new object of which it was previously unaware. Not only will there be more objects than a single computer can store, but there will be more classes of objects than a single computer can store the modeling details of.

Like the Web, the system has to cope with live and continuous development of the underlying software, the game design, the game content, and the game state. It cannot be shut down, reset, or suspended.

A Dynamic Hierarchy

Keeping Track

The distributed system is organized in a hierarchy for two key reasons: keeping track of the participating nodes, and keeping track of responsibility for all the objects distributed between the participants. The system needs to enable one node to find any other node, and for a node to understand its place in the grand scheme of things. The system also needs to store an unlimited number of objects and keep track of these, even as they get distributed around the system.

Participation

Why does a node participate? Because it has an attendant player that has an interest in playing, or more precisely, observing and influencing the virtual world currently being modeled (consisting as a set of objects).

A node needs firstly to make contact with any other participating node. It may be that some nodes are well known (probably roots or relatively senior nodes), or there may be some channel upon which participating nodes are advertised. There may even be multiple virtual worlds available from which the player can select.

Once a node has made contact, it is ready to find a close node with which to use as an initial parent (having good a connection, but with broad coverage of the virtual world appropriate to the topological network position of the player). Possibly unaware of the rapidly improving connection, the player selects the area of the virtual world, or the virtual character, that interests them most in terms of wishing to observe and influence (Princess Leia, Robin Hood, or Julius Caesar - if he's free). The game may construct mechanisms for allocating particular areas or characters of the virtual world to particular players or teams of players. Either way, when the player next connects, the nodes they made contact with last time are likely to be a good initial guess.

Once the area or object in the virtual world that the player is interested in has been determined, then this interest will be expressed to the system and adjust the selection of the player's node's parent in due course.

Naturally, the player and the object (avatar) that they're influencing will affect and experience continuous change in the set of objects of interest to the node. This, together with the changing conditions of the network, the changing relationships of other nodes (players joining, leaving), and any other changes, will cause occasional changes in parent.

A Hierarchy of Responsibility?

We start from a single node, but instead of making the default relationship a peer one, we make it a hierarchical one. This is because we are not trying to partition or divide the system, we're just trying to spread the workload. Responsibility ultimately remains with a single computer, or in some sense we always have a single server, it's just distributed over several computers.

Now one of the things about a hierarchy that may cause concern is if there is still some kind of client/server communications bottleneck effect. If there is any kind of aggregation performed by nodes, then it would appear that the root node would get a tad overloaded. A hierarchy would seem to act as much as a concentrator as the single server of a client/server arrangement, i.e. we would look forward to the same bottlenecks.

Well, I think a hierarchy has the effect of releasing that focus to dissipate throughout the system. It also allows nodes to organize themselves according the role that best suits them. Server-like computers end up serving and not much clienting, and client-like computers do a lot of clienting and little serving. Computers in between do a bit of both.

Think of it like a living tree, the closer you get to the root or the heartwood, the stronger and more stable things are. Conversely, at the periphery, there is more life and less stability. The players' computers are at the periphery, and the more reliable and capacious computers reside at the center. The most recent communications are gossiped around via peer connections, whereas the state updates to parents gradually migrate to the persistent core.

There are a variety of configurations which can support a networked game. If we have a truly adaptable distributed system then we'd expect it to assume a similar communications configuration if the connectivity and participants were the same. It all depends on the way the variety of heuristics are tuned, but if they're tuned well, we'd expect them to make the system adopt a fairly optimal configuration.

16 Player Peer-to-peer

Say we have 16 players, but they all have the same capacity computer. Well, the first player to start will become the root node. As it has all the responsibility it will initially appear the best node for all other nodes to child onto. At some point the root may realize that it has insufficient capacity to maintain the persistence of its state and may delegate this to children (according to their interest). Node relationships will also organize according to bandwidth costs. It may be that the eighth node finds it more appropriate to child to one of the non-root nodes than the root, simply because of the better bandwidth.Ultimately, what is likely to happen will be for persistence responsibility to be distributed around the nodes as necessary (if the root can't cope). Ownership is likely to follow this distribution.

As is more likely, if all computers can easily maintain all state, then the root node is likely to retain storage responsibility for all state, but each node will express interest in all objects to all other nodes. We'll end up with a fairly balanced hierarchy, with additional peer connections between nodes, until each node communicates its owned object state changes to each other node. The child/parent connection acting as one of these one to many connections.

So while all nodes have equally balanced interests and capabilities, the connections we end up with look very similar to the connections in a peer-to-peer configuration. However, as soon as computers deviate from this, then the nodes will migrate around the hierarchy according to their relative interests and capabilities.

For short-session based games, it would be overkill to use such a scalable system, but we'd still expect it to adopt an appropriate configuration.

Client/Server

If we had a supercomputer with great reliability, availability, connectivity, capacity, etc. and umpteen player computers, much poorer in every respect, then the hierarchy is likely to adopt a client/server configuration. The supercomputer would be the root, and each player's computer a child node to it. It's unlikely that any player's computer would get to own any objects at all (perhaps their avatar, but that's about it). It may still happen that some nodes will create connections with each other if only to obtain details of player owned avatars, but these would be pretty light-weight.

Overall, we'd end up seeing the parent/child connections becoming the most important.
However, if latency with the server becomes significant, more and more peer connections are likely. You might even end up with mini hierarchies developing between mutually interested groups of players, with ownership migration becoming likely too.

Distributed Server

With several supercomputers dispersed around the network, it's likely that you'd end up with a relatively central root (if that's possible), with object responsibility being portioned out to the dispersed super-nodes. It's expected that the game conspires to encourage players to be interested in the content held by their nearest super-node, and so players are likely to child off this one. They'll peer of any other node on a need-to-know basis.

Of course, if you really like this kind of flexibility, but prefer the intrinsic security of siting super-servers at ISP's premises, then you could decide to prevent object ownership migrating beyond these nodes. In this way, you end up with a system fairly comparable to a 'distributed server' system.

Scalable Peer-to-peer

If you have an unknown mix of an unlimited number of computers, then this adaptive system is ideal. If any philanthropist donates a super-computer to the cause it's likely to quickly migrate towards the root of the hierarchy. ISPs that donate some of their as yet unused rack-mounted Linux boxes are likely to reduce the bandwidth used by their subscribers, saving them money at the same time as adding value to their service. Even some players that leave their computers on whilst they're not using them (ADSL) can add some useful resources to the pool.

So in this case we maximize the use of all computers, we don't make any particular assumptions about how resources are distributed, but the more resources that are available the better the system's overall performance becomes.

Responsibility

Responsibility means being answerable about objects. One node is always responsible for all objects. This doesn't necessarily require that it be a supercomputer, but it would be nice.

Responsibility entails the following duties:

Now, in terms of analogues, registration is equivalent to the land registry of a property (the state ultimately controls everything), persistence is equivalent to the freehold of a property (the freeholder is nominally in control of the property), arbitration is equivalent to the use of a property (practical ownership), and estimation is perhaps (at a stretch) equivalent to visiting the property. There are no particular terms used to describe the delegation of registration or storage, but the act of delegating arbitration (or ownership) is equivalent to leasing and sub-leasing, etc.

New objects can only be created by the root or owned objects. In the case of an owning node, it then becomes responsible for the new object, however, it is obliged to pass this responsibility up toward the root. It's parent is similarly obliged.

At the Limit

The root node is responsible for all objects, but it is possible that it can run out of capacity to perform other duties. When the root no longer has capacity to register all objects it delegates that duty to the child that attempted to pass responsibility up to it. Thus when it runs out of storage capacity, it knows that some objects are only registered by a child. This doesn't just apply to the root, one of its children could also run out of space. In general, if such a node gets a request for an object it doesn't know about, it also checks with its child in addition to referring to its parent.

A node is more likely to run out of space for maintaining persistent storage of all the objects created underneath it. In this case (assuming no parent has the capacity), it delegates the duty for persistence to the child that passed the object up (the child gets the freehold). This means that if a node only has space for registration, it can at least know that it can service a request for the state of that node by passing it to the child to which it delegated persistence.
If an object is created for which no node has the capacity to maintain its persistence (even the creating node), then the object never gets any state (only defaults). If an object is created for which no node even has the capacity to register it, then it can't have been created, or in other words, the creation of an object requires its registration at least on the creating node.

Given this limiting behavior you can see that even in the case where objects have expanded in number to fill the space that's available, they end up overflowing from the root back out toward the branches. Ultimately in this way, such overflow objects become more and more remote. It then becomes less reliable to get hold of them and more prone to delay given limited bandwidth and the number of hops involved. Of course, once made, peer connections will obtain their details fine, but the objects won't be as persistent. When nodes that have responsibility for persistence of certain objects go offline, then it may be that some of the node's children stuck around and can assume responsibility instead. Otherwise, those objects' state becomes inaccessible (unless a peer node coincidentally had cached copies).

The system could then eventually run out of capacity, and no new objects could be created. That's a heck of a lot of objects if you imagine the collective capacity of a few million computers in a few years' time. The game design could do a lot to avoid this getting consumed too rapidly, but it may be that we'd need a policy that purged registration of the least frequently accessed objects. Bear in mind we're looking at something comparable to the situation where web sites would be growing in size faster than ISPs could plug in extra hard disk drives. It's a race between exponential growth in demand and capacity. I have a hunch that demand only increases in response to capacity, so perhaps we'll always just have enough. Hmmmn, is addressing space for only 2^64 objects enough for a few years - what do you think?

Interest

Let's look a bit more at how objects get distributed around the hierarchy of nodes - especially when the system is operating within its capacity.
All objects have a responsibility to express interest in the objects that may affect their behavior. Naturally, there are plenty of passive objects that can rely on being of interest to others (rocks, say).

An 'Interest' is a set of criteria and acts as a measure of relevance to which any number of other objects may be compared.

Interests are essentially constant entities, but they have a key feature: it is straightforward to tell if any object meets the Interest or not (partial match is classed as non-matching). An Interest could take the form of a template object with the criteria being 'all objects of this class that have the same property values'. This would be an equivalence operation, but in some cases it may be useful to perform a distance operation between a 3D position property, e.g. 'all objects of this class that have a 3D position less than L away from the 3D position specified'.

However, more than the ability to determine whether an object meets an Interest, it may be useful to see how interesting or uninteresting it is. This may be useful, but perhaps for the time being we can make do with an Interest obtaining a logical response as opposed to a fuzzy one. Remember we're already allowing objects to express an Interest as a prioritized demand for details all objects that meet particular criteria (whichever node they may reside on), it may be going a bit to far to allow the goodness at meeting the Interest to further moderate the priority of individual objects.

Given Interests deal with matching objects it's likely that an Interest may end up being laid out in a manner very similar to the objects. An Interest is therefore also likely to observe the same class hierarchy as objects. Interests may also have a variable lifetime, dependent upon the behavior of the object that's expressing them. Static objects may have long term interests in a relatively fixed sphere, whereas dynamic objects may have repeated short term interests in a conical region in front of them. Though I've used spatial examples here, there's no reason to hard-code interests in terms of spatial properties. A mercenary NPC may be interested in all country stats objects containing at least 1 battle in progress.

Note that Interests only get communicated if their lifetime is sufficiently long enough to warrant it. Their lifetimes however, must be designed carefully to ensure useful results. There's no point getting tons of objects downloaded if it's highly likely that they'll not be interesting once they've arrived. It's also worth pointing out here, that Interests are not intended to be used for modeling purposes, e.g. collision detection. There are separate services provided by each node that can monitor objects (that have caused themselves to be registered to the proximity analysis service) and then raise events as appropriate upon collision.

If you're worried about performance issues in satisfying all these interests, note that although Interests don't need to be based on spatial distance this doesn't stop us providing a low level service that does allow objects to be spatially indexed (octree, whatever). We can use this in order that spatial interests can be satisfied promptly.

The Domino Effect of Interest

An object is interested in all other objects that are relevant to its behavior. Ultimately (as Douglas Adams might phrase it) a single piece of fairy cake can be influenced by every other atom in the universe. However, for our purposes we can get by with a decent proportion of the local environment. Though players with big enough hard disks, might well end up caching nearly the entire virtual world, even if the player was just interested in a piece of fairy cake (it would have to be non-passive in this case).

If a farmer is interested in foxes and rabbits, but there is a rabbit that is too distant from the farmer's measure of interest to get downloaded, it may happen that a fox will be interested in the rabbit, and raise the importance of the rabbit sufficient for it to be brought in to the node and thus available to the farmer's perception.

The only way objects usually become able to be aware of one another in the modeling sense is if they reside on the same node. An Interest implicitly represents the 'best effort' set of all objects that meet the Interest's criteria. This set of objects will naturally change as and when objects are downloaded or get pushed from the node's cache.

Each node's Interest Manager accumulates all the resident objects' interests, and does its best to obtain objects that meet these interests. It will do this by communicating with the parent (possibly children too) and the parent can do its best to satisfy one or more of the interests, but it in turn may pass an Interest on as appropriate. The Interest in effect represents a seeking tendril that feels around neighboring nodes until it find a good source to satisfy that interest, in which case the tendril plugs in and forms a semi-permanent peer subscription to that node. These peer relationships are chosen according to the advantages outweighing the cost (of bandwidth).

For example some distant rocks might be passive objects, but another player's weapon might blast them to bits. The weapon may be out of range of the node's interest, and thus the weapon will not be modeled. However, in due course, there will be incoming state updates to the distant rocks that results in a 'destroyed rocks' situation.

If they were distant bunny rabbits that tended to run away from farmers with shotguns, then there's a good chance the bunnies would express interest in farmers (unlike rocks). A farmer appearing on the horizon might just get downloaded (even if it was the barest of state info). This might be enough to get the bunnies to run away in a fluid motion, rather than occasional updates make them move in jerky fashion. There's still a good chance the bunnies run and get discontinuously relocated to the remotely arbitrated position, as opposed to the local estimate, but it's better than nothing.

An object with behavior that is affected by some aspect of its environment, expresses interest accordingly. If that results in other objects turning up, that have behavior and a consequent interest in their environment, then we end up with a set of objects prioritized according to their relevance for modeling the experience of the observing avatar.

Two different avatars thus have a perception of 'reality' from two different perspectives.

The greater the degree of commonality in the interests of two avatars, the closer the modeling of their experience will be. This is because they are likely to have the same set of objects (though one node may have less resources than the other).

Thus the closer two avatars are, the more their perceptions will agree. And at the end of the day, that's all we need to worry about. As long as interacting players have a consensual version of reality then they'll make sufficiently similar interpretations of their situation that each player will be able to believe all players are in the same 'reality'.

Note though, that it's up to the games designer to determine where the priorities lie in contriving the best-effort modeling for an avatar. It may be more important to model enemy helicopters than weather vanes on church steeples. Only the games designer will understand the player enough to be able to have some idea of what is most likely to be important to their experience.

Caveat Emptor

The system I'm gradually providing more and more clues about is one that attempts to address issues of scalability. It's not one that makes minimal use of CPU or storage. It certainly doesn't attempt to provide any integrity or consistency guarantees.

People are already developing systems which address particular configurations, particular player counts, particular bandwidth and latency constraints, and because of this, such systems can achieve some degree of integrity and consistency, and can be performance optimized in many areas.

Do not mistake these articles as guidelines for developing the systems underlying contemporary multiplayer games. There are many techniques and algorithms that I haven't covered, many of which are critical to systems in use today. You'd need to get very familiar with them before embarking on such development.

So, I'm not talking about how to design a system that is going to support umpteen thousands of subscribing players and meet their demands for a glitch-free, 100% uptime, quality experience, that is profanity free, and above all fair.

For that matter, if you built a system that observed the principles I'm suggesting you'd probably end up with something that you couldn't charge for. Not only would there be no security, but by the time a million or more people participated, there'd be loads of people exchanging offensive material, and a few vandalizing the system wholesale.

It is difficult to imagine anyone who'd be 'brave' enough to invest in the development of such a system.

However, if we're going to have cyberspace, a system as large as the web that exploits the connected computers, then it doesn't matter how unsound a business prospect it is. As technologists, as games developers looking to tomorrow, the sooner we understand the issues, the sooner we'll create the entertainment system of the future.

Resilience and Security

It's one thing getting a plane to fly, it's another to stop it falling to pieces (or getting shot down).

Next time I'll be discussing methods and strategies for ensuring the system can cope with sudden and unexpected failure of nodes or parts of the network. These I'm pretty confident about. It's less certain how to obtain security in the face of concerted attacks. However, I'll have a go.

Until then, check out Dig It Network Multimedia Inc. for an example of a possible solution to security in P2P games.