It's free to join Gamasutra!|Have a question? Want to know who runs this site? Here you go.|Targeting the game development market with your product or service? Get info on advertising here.||For altering your contact information or changing email subscription preferences.
Registered members can log in here.Back to the home page.

Search articles, jobs, buyers guide, and more.

By Crosbie Fitch
Gamasutra
[Author's Bio]
December 26, 2001

Introduction

Moving towrds Open Source middleware based platforms

Heuristics

Fault Tolerance

Printer Friendly Version
   
Letters to the Editor:
Write a letter
View all letters


Features

Cyberspace in the 21st Century:
Stability Before Security

Heuristics
There are many decision-making processes likely to be going on in the system, but as I've already identified, the key ones are parent selection, peer selection, object owner selection, and resource utilization. Each of these decisions will be governed by a heuristic in the form of a weighted sum of various measurements that we consider should affect the decision. Perhaps a genetic algorithm could let us arrive at an optimal heuristic, but we'll make do with an intelligent guess for the time being — there's always empiricism to look forward to (a wet finger in the wind).

  • Changing parent. In table nine I list the kind of measurements I expect should influence the selection of a parent, or more precisely, the decision as to whether to change the parent, and if so, to which of the available candidates. Parent candidates can be collected from one's list of current and past relationships, as well as any recommendations that a node may have provided in response to an interest subscription, e.g. "From the interest you've expressed to me, and my knowledge of my current interest subscriptions, I recommend you talk to node X." Parents and peers may thus provide node recommendations as well as object updates in response to interests.
 
 
Table 9 - Decision to change parent.
  • Selecting Peers. While parents provide a node with advantageous opportunities for responsibility, peers provide it with alternative, fresher sources of information concerning its interests. Peer nodes are how you bypass the intermediate-server or word-of-mouth problem, i.e. if there are five avatars in a room; it's likely that many of the respective nodes will get in touch with each other. Of course, peers come at a cost and this must be weighed against the benefits of receiving news from the horse's mouth. Table ten lists the pros and cons.
 
 
Table 10 - Decision to select a new peer or deselect a current peer.
  • Ownership selection. Object ownership, as I've said before, is how arbitration is distributed around the system, and determines who gets to arbitrate via a hierarchical organization of responsibility relationships. Just as ownership tends to be allocated to the nodes most interested, so the decision as to who gets ownership should also be relatively close to those most interested in responsibility for the object, i.e. the complete lineage of current owners. Some factors that might influence the decision are summarized in table 1. Any node that is responsible for an object is able to relinquish responsibility to its parent, delegate responsibility to a child, cease delegation, and reclaiming responsibility.

    Children are implicitly competing for ownership of objects that they're interested in. The parent node that owns an object is constantly evaluating the cost/benefit of retaining responsibility vs. relinquishing it, whether responsibility was better served if ownership was delegated to a child, and if so, which child and the transition cost vs. benefit of change.

It is important to appreciate that ownership need not change rapidly. Ownership is not vital to any node, but it is advantageous for interesting objects.

Ownership decisions are being constantly evaluated all the way up the lineage from the current owner to the root. Thus, if ownership is changed fairly high up the lineage, notifications of change of ownership will filter down the lineage to the previous owner. It's likely that sometimes a decision to change ownership may occur at the same time at different nodes in the lineage. This doesn't really matter because a parent is always able to pull the rug from under the feet of its children — so to speak.

 
 
Table 11 - Decision to change object owner.
  • Resource usage policies. In addition to balancing the load across the nodes in the system, there's also the finer grained issue of balancing the utilization of local resources, i.e. storage, processing and communication.

    The answer is to prioritize everything. This can be based on how important something is to the operation of the system, the operation of the game and the node's current interests.

    Therefore, it involves the system designer, along with the game developer, player and any interested child nodes.

 
 
Table 12 - Communication Utilization Policy

Tables 12 to 14 list a variety of factors that are likely to determine how resource utilization is prioritized.

 
 
Tables 13 and 14: Storage Utilization Policy, Processing Utilization Policy (NB A non-mutating thread is one that is unable to cause a persistent effect, e.g. adjust object properties, register interests or events).

Equitability
In order for the load to be balanced throughout the system, there is an implicit acceptance by each participating node of an equitable contract, i.e. 'to each according to their need (interest and capacity), and from each according to their ability (knowledge and resources).' This doesn't necessarily mean that each node has to be equal; it just means that each node is only permitted to make unlimited requests to any other node on the understanding that it places no limit on the requests it serves, which it will do to the best of its ability. NB this is just a node thing, it doesn't mean that a player can't throttle bandwidth, or limit the CPU and

RAM Available to the System.
This reciprocity is something that I have been assuming is self-evident; that the system only works because it grows in power with each new node. If nodes join that are unwilling to be anything but consumers (even if no other node would tend to select them as peer or parent) then this defeats the distributed nature of the system, especially its ability to balance the load.

Of course, I have been assuming that each node runs the same software and cannot be selfishly configured, but I expect it is still necessary to state this assumption and its basis of equitability just in case it's not as obvious a requirement as I'd thought.
The system works by harnessing each node's self-interest. In turn, each node is obligated to service peer interests, and adopts interests of child nodes (considering it a worthy parent) as though they were its own.

Guarantees
The system should only support the basest of motivations, and just one at that, i.e. the best modeled experience possible. That's another reason why this is a best effort modeling system and not a best effort storage, processing or communications system. Therefore, you may see a tendency for good storage, processing and communications; however, none of these are actually the system's primary concern. Moreover, being best effort by nature means that there are no guarantees. Indeed, it's the lightest burden for both the system and each node, if neither requires guarantees (doesn't crash in their absence) nor is obliged to provide them.
In this way, we arrive at a system that no one will pay for (it's only the money minded that faint at this point). Its software is developed by the Open Source community (probably), with the players providing the resources that it uses. Neither developer nor player pursues to guarantee any level of service to each other, but there is a gentleman's agreement that participation is on an equitable basis.

Anything beyond this basic, although not guaranteed system, is obviously where money comes into play. Alternatively, put more succinctly: guarantees cost money.

  • Persistence. If a player wants guaranteed persistence, they'll have to provide the resources and connectivity themselves or pay someone else for the long-term storage of their long-term interest (all the virtual real-estate they've ever developed). Of course, there will be a tendency for all the most interesting parts of the virtual world to remain persistent in any case, but this isn't a guarantee. It might be that a bit of graffiti spray painted on a pebble thrown into the lake one day, could eventually fade from every node's object store, and when scuba diving there a few months or years later the player might be disappointed to find that same stone, but without the graffiti. If it's generally uninteresting, but somehow the player would be upset at its loss, then the solution is for the player to buy the storage, i.e. to buy the persistence guarantee.
  • Quality of service. Players are already used to spending money to buy more CPU or more RAM, even more bandwidth. If they want any system features to be guaranteed or improved, say perfect stability, greater integrity, higher fidelity or improved connectivity, they'll have to get their wallets out. And this is obviously where the commercial opportunities lie.

    To some extent, this also applies with respect to security, privacy, authenticity, etc. These things can be tendencies of the system, but guarantees need only be provided by commercially oriented third parties or implementers of variants of the system that do have these properties.

    Maybe this helps clarify my stance of separating system design from add-on features necessary for commercial viability of a particular business model.

______________________________________________________

Fault Tolerance


join | contact us | advertise | write | my profile
news | features | companies | jobs | resumes | education | product guide | projects | store



Copyright © 2003 CMP Media LLC

privacy policy
| terms of service