Citation
Virtual quidditch

Material Information

Title:
Virtual quidditch a case study in distributed processing
Creator:
Lambert, Sherman
Publication Date:
Language:
English
Physical Description:
76 leaves : ; 28 cm

Subjects

Subjects / Keywords:
Electronic data processing -- Distributed processing -- Case studies ( lcsh )
Computer games -- Programming -- Case studies ( lcsh )
Quidditch (Game) ( lcsh )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 74-76).
General Note:
Department of Computer Science and Engineering
Statement of Responsibility:
by Sherman Lambert.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
53368579 ( OCLC )
ocm53368579
Classification:
LD1190.E52 2002m L35 ( lcc )

Full Text
VIRTUAL QUIDDITCH:
A CASE STUDY IN DISTRIBUTED PROCESSING
by
Sherman Lambert
B.S., Colorado State University 1982
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Computer Science
2002


This thesis for the Master of Science
degree by
Sherman Lambert
has been approved
John Clark


Lambert, Sherman (M.S., Computer Science)
Virtual Quidditch: A Case Study in Distributed Processing
Thesis directed by Professor Gita Alaghband
ABSTRACT
In this thesis we address the design and partial implementation of Virtual Quidditch.
Our goal is to design a system with specific goals in mind to explore the feasibility of
a distributed, platform independent system, simulating real time interactions among
processing components.
These design goals are:
The system is to be built using unreliable processing components
The system components are dynamically configured
The system distributes processing as much as possible to produce a flat hierarchy
The system is able to perpetuate itself even when segments fail (at random)
Parallelism is to be used wherever possible
The system is designed to use resources found via the Internet
111


These goals come together to form a very generic network-computing environment.
The goals have been designed such that we are forced to recognize and analyze
design tradeoffs.
Virtual Quidditch is an implementation of J. K. Rowlings fictional game Quidditch,
presented in her Harry Potter book series. In this game there are numerous objects
interacting in three-dimensional space. The players of the game operate many of
these objects; however, many are not player-controlled. We have chosen this game as
a test bed for distributed system of processing elements because of this mixture of
game objects.
In this thesis we elaborate on how the system is designed and implemented to date.
To do this we create two models of distributed development: the Target Market
Model and the System Robustness Model. The Target Market Model concerns itself
with design and usage of the resulting system. The System Robustness Model
explains the interactions of distribution, fault tolerance and synchronization. These
models show the inter-connectivity of their elements making system tradeoffs more
concrete. In applying these models to Virtual Quidditch we show how requirements
restrictions work down into the technical design and force trade-off decisions to be
IV


made. Using these same models we are able to show how our resulting compromises
will affect the softwares usability in its designed market.
This abstract accurately represents the content of the candidates thesis. I recommend
its publication.
Signed
Gita Alaghband
v


CONTENTS
Figures ....................................................................ix
Code Samples ...............................................................x
Chaper
1. Introduction......................................................1
2. Motivations.......................................................4
3. Analysis of the Problem...........................................6
3.1 Analysis Using the Market Driver Model............................6
3.2 Analysis Using the System Robustness Model........................9
3.3 Game Analysis....................................................13
3.3.1 Game Operation...................................................13
3.3.2 Game State.......................................................14
3.3.3 Communications...................................................15
3.4 System Goals.....................................................16
4. Virtual Quidditch as a Case Study................................20
4.1 Short Description of Quidditch...................................20
4.1.1 The Game.........................................................20
4.1.2 Important Elements of the Game in Terms of This Thesis...........22
4.2 The Target Market Model and Virtual Quidditch....................23
4.2.1 Life Cycle Modification Techniques...............................24
vi


25
27
28
29
30
30
31
32
32
33
33
34
34
34
37
41
42
43
44
45
46
Use of Object Oriented Analysis........................
Game Object Design.....................................
Object Oriented Development............................
Benefits of Using Object Oriented Techniques...........
Intended Platform......................................
Independence Achieved by Using Python..................
Effects on Communications..............................
Hardware We Cannot Depend On...........................
Other Possibilities....................................
Robustness.............................................
System Developed Coarse-Grained and Distributed........
Virtual Quidditch as Seen by the System Robustness Model
Distributed Processing.................................
Game Layout............................................
Game Distribution......................................
Other Possibilities....................................
Fault Tolerance........................................
Coarse-Grained Fault Tolerance.........................
Simple Fault Detection and Recovery....................
Token Passing Scheme Used..............................
Roll Forward Technique Used............................
vu


4.3.2.5 Scheme Expanded for Other Distributed Functionality...............47
4.3.2.6 Other Possibilities...............................................51
4.3.3 Synchronization...................................................52
4.3.3.1 Use of Coarse-Grained Synchronization.............................53
4.3.3.2 Synchronization through Message Passing...........................53
4.3.3.3 Effects of Coarse-Grained Synchronization.........................56
5. Limitations and Future Work.......................................58
5.1 Limitations of Current Algorithms.................................58
5.2 Future Work.......................................................60
6. Summary...........................................................62
Appendix
Appendix A. Detailed Game Description.......................................65
Appendix B. Use-Case Analysis...............................................69
References...................................................................74
viii


FIGURES
Figure 3.1. A Target Market Model................................................7
Figure 3.2.A System Robustness Model.............................................10
Figure 4.2.1.1. A System Design..................................................26
Figure 4.2.1.2. A Object Diagram.................................................27
Figure 4.3.1.1.A Physical Game Layout............................................35
Figure 4.3.1.2.A Logical Game Layout.............................................39
IX


CODE SAMPLES
Code Sample 4.3.2.5.A Token Ring Class Definition.....................................50
Code Sample 4.4.3.2. A Sample Message Passing.........................................54
Code Sample 4.4.3.2.B, Queue Handler..................................................55
x


1. Introduction
The thesis concerns itself with the development of a distributed software project by
the name of Virtual Quidditch. It is a game modeled after the fictional game of
Quidditch presented in the Harry Potter book series by J. K.Rowling [Rowling 1997,
1998, 1999, 2001], The system is a case study of distributed processing. We will
spend a great deal of effort explaining how the system perpetuates itself even in the
case of multiple faults.
We begin with a short discussion of the authors motivations for this project. These
motivations will help us focus on what we were hoping to demonstrate with this
project. The motivations are both commercially and educationally based. We feel
these motivations are very pertinent to the field of computer science.
In order to effectively present the alternatives and tradeoffs that go into a distributed
software development project we will present two models of their interactions. Our
goal is not to develop the definitive model, but to have a vehicle for explaining how
all of the elements of a distributed project interplay off each other to form these
tradeoffs. The models also help to explain how non-technical requirements drill
1


down into the technical design, and technical issues rise up to affect the resulting
market for the system.
This thesis will work through the facets presented in the models (described above)
and explain how and why Virtual Quidditch was developed as it was. We will
employ each element of the models using the Virtual Quidditch project as an
example. These relations (Virtual Quidditch to the models) are the bulk of this thesis.
These relations showing the depth of the Virtual Quidditch project.
Many development choices were made in the development of Virtual Quidditch.
After the in-depth explanation of the project we take a short look on the limitations of
V.
these choices. Finally, we discuss areas for future work in Virtual Quidditch.
This paper is organized in the following manner. We begin with a short survey of the
authors motivations for the project. In Chapter three we analyze both the game and
the models we are planning to use to explain the project. The Target Market Model
and the System Robustness Model are explained in this chapter. System goals, which
are the requirements for the system, are also presented here. Chapter four explains
the development of the game using the Target Market Model and the System
Robustness model. In chapter five we explore the limitations of the current system,
2


and the future work that can be made on the system. We close the paper with a
summary presented in Chapter Six.
3


2. Motivations
This thesis started out as an independent study of communications in distributed
processing. This study focused on the technologies of MPI [Gropp 1994], CORBA
[Vinoski 1997] and SOAP [Dix 2001], These three technologies showed the
progression of development of distributed systems. Each evolution of technology is
less tightly bound than the previous one. In particular we found the paper A Wrapper
Generator for Wrapping High Performance Legacy Codes as Java/CORBA
Components [Li 2000] in which the authors were combining MPI, CORBA, and
XML intriguing. It shows how these technologies can be combined because the are
working at different logical layers in the software.
We were also interested in agent technology [Bigus 1998] [McCarthy 1999], This
technology is a catchword for many different types of systems. The particular type
we found most interesting are systems which are self-replicating, and are compared to
an army of ants (many seemingly independent agents working together toward a
common end). It struck us that while this idea was good there was very limited
management (mostly by design) of these systems. In particular there is no guarantee
of a solution (computed result).
4


Finally the authors of this paper have been working in the software development field
for over a decade. In that time frame there has been a very noticeable shift in
technologies. Structured programming [Mills 1986] is not presented as a software
discipline like it has been the past. The emergence of object oriented technologies
have emerged as a dominant development methodology [Nathrop 1997] despite
limited early success. A general move toward interpreted languages is another trend.
Finally new development models [Bohem 1988] [Comer 1991] are radically different
the previous waterfall model used. While each of these items in itself is
understandable, it is puzzling that the trend is away from tight code produced using
well defined methods to less efficient code built using much looser methods.
The Virtual Quidditch project described in the remainder of this paper will address
many of these motivations. In this thesis we present the development of the
distributed game, Virtual Quidditch. The game is particularly well suited to address
many of the technologies and trends mentioned above. In order to present the project
we developed several design models (the Target Market Model and the System
Robustness Model) for this purpose. We feel that these models address many of the
questions that motivated the project.
5


3. Analysis of the Problem
Virtual Quidditch is being developed as a case study of the problem areas in
developing distributed applications. Thus far Virtual Quidditch has proven to be an
excellent choice for doing so. Two models of distributed development: the Target
Market Model and the System Robustness Model are presented in this chapter.
These models have been developed for the purpose of explaining our development of
Virtual Quidditch and are not intended to be a focus of this thesis. The models are
arranged in a two-tier manner. The first tier (the Target Market Model) is directed at
the how the project should fit in the user space. The second tier (the System
Robustness Model) concerns itself in how internal elements of the system interact
with each other to form a level of quality (robustness) in the system.
Later this chapter we will present a number of goals designed to exploit the different
elements of Quidditch for a study in distributed processing.
3.1 Analysis Using the Market Driver Model
The Market Driver Model is presented in Figure 3.1. A below.
6


Figure 3.1.A Target Market Model
The Target Market Model depicts three elements interacting with each other. These
three elements are Intended Platform, Software Life Cycle Enhancement Techniques,
and System Robustness. The diagram shows that each design element mutually
effects any other design element. A well-designed system would have an equilibrium
of the influence each element places upon the others.
The Intended Platform is both the machine and the software environment that we are
developing to meet. In distributed computing it is quite common to develop a
7


software product for a particular set of special hardware available to the intended
user. The software environment can be any defined platform that we can develop to.
The intended platform need not be hardware. More often software is produced to run
on a software platform (I.E. Windows, or the Java Virtual Machine). Whatever the
intended platform is defined to be, this will have ramifications on the other design
elements in this model.
Software Life Cycle Enhancement Techniques are a collection of software
engineering techniques that modify the normal software life cycle. These techniques
are commonly thought of as ways to build better software, however usually they
enhance the software life cycle to do so. Usually they either reduce time to market, or
elongate the maintenance phase to make the software viable for a longer time.
System Robustness is the level of quality in a system. System quality is in fact
variable and is not necessarily needed to be high. It is more of a sliding scale that we
need to determine what level is correct for our application. If our system has a very
short expected life span then it might not need to be very robust. On the other hand if
we are building a guidance system for a jet fighter then the robustness of the system is
a primary concern, and needs to be very high.
8


In the development of this thesis there was much discussion as to whether or not this
model need to be included. Our decision to include this model stemmed from two
points. The first is that software is developed to be used by a defined user-machine
tuple. The second being that we need to understand how decisions about many
seemingly non-technical issues can drive down into our technical design and make
large differences. The Market Driver Model shows how we develop software to be
used. The target machine, the O/S platform, and possibly even the runtime
environment are all elements of the intended market.
3.2 Analysis Using the System Robustness Model
The System Robustness model contains three design elements Distributed Processing,
Fault Tolerance and Synchronization. The model is presented in Figure 3.2. A below.
9


Figure 3.2.A System Robustness Model
Distributed Processing as presented in the model above is a how much the system
distributes processing to the different processing nodes in the system. As the level of
distributed processing increases the interaction with the other two elements also
increases.
10


The System Robustness Model defines how design elements of a distributed system
interact with each other to create a level of robustness. In this thesis we are defining
robustness as efficiency and confidence. Confidence is two-fold, confidence that the
system will complete without failure, and confidence that the system will produce a
correct result. It would seem logical to assume that every system should achieve the
highest level of robustness possible. However, this is simply not true. It is very
costly to create distributed software to this level, while quite often the user simply
does not require this level of quality. Further the System Robustness Model does
nothing to quantify the level of quality created. Our model only helps to explain how
these features interplay with each other to form a level of quality. The robustness to
be defined by this model is passed back up to the Target Market Model. The
encapsulation of System Robustness Model in the Target Market Model shows the
logical connection between the two models. The reader may note that we could have:
expressed this as one single level model, but we felt the separation of user-elements
(Target Market Model) and technical-elements (System Robustness Model) presented
by two separate models gave a better abstraction of the interactions of each models
elements.
In the next chapter we will use these models in describing Virtual Quidditch. We
have found that Virtual Quidditch is a good model for demonstrating many different
12


aspects of distributed development. Our models are an effective method of
demonstrating the interactions of elements that take place in the development of a
distributed system.
3.3 Game Analysis
Early analysis into the requirements of the game yielded some indications as to the
demands that the game will place on the machine.
3.3.1 Game Operation
Each game is rendered to the local users screen in a first person view. That is to say
the screen gives a view as the player can see form their vantagepoint in the game.
Each game will be rendered in simulated real time. To do this the local machine will
need to constantly redraw the players view. From the Alice project [Conway 1997]
we know that animation refreshed ten times a second will seem smooth to the user.
So, our target refresh in Virtual Quidditch is also ten times a second.
To refresh the screen the UI module will need to determine the position of each object
relative to the players point of view (which changes with player movement). It then
needs to calculate how each object will look from the point of view. Remember that
objects appear larger closer to the viewer. The calculated view is then transferred to
the screen buffer and then rendered to the screen.
13


The reason we have elaborated so deeply on the rendering process is to drive home
that we are expecting this to be the dominant calculation within the system. In fact
we are expected this to be several orders of magnitude greater than other functionality
with in the system.
3.3.2 Game State
In order to render the game to the users screen the local machine will need to know
almost the entire state of the game. This required an initial estimate of the state that
each game will need.
1) List of all players currently in the game
2) State of each player
a. Position and speed vectors
b. Health
c. Mass
d. Team
e. Position
f. Broom
g. Net Address
h. Ordinal value- numeric team/ position value
i. Hold list- objects the players is holding onto
3) State of each non-player-controlled object
14


a. Position and speed vectors of non-player-controlled objects
b. mass
4) Time since communication was received from of each player
5) Game score
A quick survey of these state items and you might notice that other than position and
speed vectors for moving objects few state items are updated regularly. In fact other
changes to state will be rather infrequent events.
3.3.3 Communications
The game state analysis showed that player movement is the dominant
communication needed to operate the game. Using the flat hierarchical model that is
our desire we are expecting an all-to-all heartbeat for player movement. So at regular
intervals each player will signal every other player with its current position and speed
vector. In Quidditch there are fourteen players, four balls and the referee, or nineteen
moving objects that need to report position changes. From the Game Operations
analysis above we know that we want our heartbeat to be ten times a second. Each
object sends and receives a movement beat to all other players at each heartbeat. So
we can expect 18x2x10= 360 movement messages a second. This is just an estimate
but will give us a good idea of our needs.
15


3.4 System Goals
Generally stated the target market for Virtual Quidditch is the Internet. The main
idea is that we are trying to use computing resources, which are available to us, and
yet we have very little control over them. The defined goals ofVirtual Quidditch are:
The system is to be built using unreliable processing components
The system components are dynamically configured
The system distributes processing as much as possible to produce a flat
hierarchy
The system is able to perpetuate itself even when segments fail (at random)
Parallelism is to be used where ever possible.
The system is designed to use resources found via the Internet.
A more detailed elaboration of each goal is as follows:
The system is to be built using unreliable components. This is to simulate a
system that is using the resources that are currently available. We are not trying to
build a system that requires special hardware. Further, we desire that the hardware be
platform independent. We define the target machine as loosely as possible. The
hardware should be what is commonly available on a local area network. We do not
want to allocate any system resources before they are needed. We are attempting to
show that a reliable system can be built using commodity grade components. This is
an affirmation of the robustness model.
16


System components are dynamically configured. A system in which we are using
the resources on hand is a very dynamic environment. By requiring that the system
be dynamically configured we are showing how a changing environment can be
managed effectively. This is in effect showing that the software life cycle [Comer
1991] is being altered. Dynamically allocating non-dedicated resources in
conjunction with the previous goal of commodity grade (loosely defined) components
demonstrates that the maintenance phase can be prolonged. A dynamically
configured system can persist in the case of fault if there are mechanisms to request a
replacement. Lastly by making the system dynamically configurable we are
demonstrating that the available resources to the system are only limited to resources
available through the network. In most organizations network resources grow over
time.
System distributes processing as much as possible. Our game is a demonstration
of the power that can be exploited using distributed computing. We are trying to
move from the well-understood hierarchical model to as flat of a model as possible.
At the same time we cannot push management overhead excessively on the
processing components of the system. We are trying to create a system that is
managed effectively with low overhead that is robust and effective without special
hardware.
17


The system is able to perpetuate itself even when segments fail (at random). This
demonstrates that the system is fault tolerant. While this is not exceptional in itself,
when taken conjunction with other previous goals i.e. commodity grade components,
distributing processing as much as possible, and dynamic configuration, this creates a
much more robust system.
Parallelism is used where ever possible. The system should be built to take
advantage of the available resources and to operate various segments in parallel.
Therefore the system can be used for much bigger problems than the game presented
here. Further we would like to show that the system becomes more reliable by using
more computing elements.
The system is designed to use resources found via the Internet. The system
should be designed to use the Internet as its target. This is an unreachable goal. The
Internet contains far too many types of computing equipment for our system to be
able to utilize them. This goal encourages development to be as open as possible.
Further it should be pointed out that resources found via the Internet are inherently
unreliable to us. We have no control over hardware, software, local users, or the
network connectivity. Therefore we have to assume that all Internet resources are
inherently unreliable in nature. Further we cannot make any assumptions to the
communications being used beyond what is commonly used on the Internet (TCP/IP,
18


56k modem). Part of this thesis is to show that we can use these inherently unreliable
components to build a reliable system.
19


4. Virtual Quidditch as a Case Study
Virtual Quidditch has been developed to explore the motivations discussed in chapter
2. To do so it is necessary to give a short description of the game of Quidditch. This
description of the game is followed by an explanation of how this game can be
applied to distributed development. Using the Market Driver Model and the System
Robustness Model presented in chapter 3 we will show how our implementation of
Virtual Quidditch exploits the interaction of design elements of these models.
4.1 Short Description of Quidditch
4.1.1 The Game
Quidditch is a fictional game created by J. K. Rowling in her Harry Potter series of
books [Rowling 1997, 1998, 1999, 2000], In this game there are two teams of seven
players each. They play the game on a field (called a pitch) that has three large hoops
placed at each end of the pitch about fifty feet in the air. All players fly through
three-dimensional space, using broomsticks (classic witch style).
Each team has three players called chasers. The chasers play with a red ball called
a quaffle about the size of a volleyball. This ball is charmed to fall very slowly.
The chasers pass the quaffle to each other as they try to throw the quaffle through one
20


of the opponents hoops. The game is a contact game. The referee (described later)
decides what is and is not a foul.
The keeper is a goalkeeper for the team. The job of the keeper is to keep the
opposing team from throwing the quaffle through one of the hoops. When the quaffle
does pass through the hoop ten points is awarded to the throwing team.
There are two balls called bludgers. These balls are black and are very similar to a
bowling ball. The bludgers are charmed to randomly attack players. Each team has
two players called beaters who are armed with sticks with which they strike the
bludgers. It is their task to keep the bludgers away from their team, while hopefully
sending them chasing the opposing team.
There is a very small and fast ball called a golden snitch. As mentioned this ball is
very fast and extremely erratic. Each team has a final player called a seeker. The
game is over when one of the seekers captures the golden snitch. The team that
captures the golden snitch is awarded one hundred fifty points.
21


Finally, there is a referee. It is unclear if this person stays on the pitch or also flys in
the air. The referee makes all penalty and scoring calls. The referees call is final.
4.1.2 Important Elements of the Game in Terms of This Thesis
While the above description sounds like an exciting game there are other reasons for
the selection of this game. First there are two classes of playing objects; player-
controlled and non-player-controlled (autonomous). The various game players
(users) operate the player-controlled objects. Second the various non-player objects
have varying modes of operation.
In a hierarchical model the server would do all the computations for the non-player-
controlled objects. However one of our goals is to distribute processing as much as
possible. If we push the computation of non-player-controlled objects out to our
distributed processing elements, this causes two problems in the system. First having
a single node (game) process the movements of an additional non-player object
creates a single point of failure. Which is significant in our environment, because we
are using unreliable components. Second the additional processing of a non-player-
controlled object might tax the local machine of resources that the user needs for his
game. In effect making the player less able to compete with other players not having
to additional processing of non-player-controlled elements. As an example, if we had
the Keepers process the bludger movements. We have already stated (section 3.3.1)
22


that the screen rendering of the game will take most of the game processing
calculations. By making the Keepers do additional processing we are stealing from
resources to render to the screen that other players have. This could well effect the
difficulty level of the Keeper player, and thus make it easier to score.
In the next section we will show how the implementation of Virtual Quidditch
effectively deals with these problems. We will show how processing can be
partitioned to various system components (games). We will show how the system
can deal with failures and keep both classes of objects operational even with multiple
component failures.
4.2 The Target Market Model and Virtual Quidditch
In this section we will begin to analyze the implementation of Virtual Quidditch thus
far. This will be done initially by using the Target Market Model (described in
section 3.1) and then further analysis will be made in section 4.3 using the System
Robustness Model (described in section 3.2). These models will be discussed within
the framework of the system goals presented in section 3.4 (System Goals). We have
regarded these goals as the requirements for the system.
23


The Target Market Model is necessary to understand how its model components
interact and force the resulting design decisions in the System Robustness Model.
Conversely the System Robustness Model will effect the market being defined in this
model. This has proven to be a good modeling technique for Virtual Quidditch, as we
have found that the system robustness will strongly effect our target market. The
System Robustness Model exposes conflicts in our goals that will effect the user
experience.
We start by describing Virtual Quidditch in terms of three of the model components
Life Cycle Modification Techniques, Intended Platform and Robustness. The
Robustness design element is only described briefly here. Virtual Quidditch and the
System Robustness Model are described in detail in section 4.3.
4.2.1 Life Cycle Modification Techniques
The goals of Virtual Quidditch did not specify any desire to alter the standard
software life cycle. We felt that the use of Object Oriented Technology would aid our
development by developing a model that we could try different algorithms
interchangeably. Further we felt that using RAD (Rapid Application Development)
[Martin 1991] techniques would aid us in a faster development.
24


4.2.1.1 Use of Object Oriented Analysis
Virtual Quidditch was analyzed as a system using elements of common Object
Oriented Analysis. The actor analysis [Jacobson 1992] rendered the following list of
actors:
Radio tower (changed to Commissioner in the implementation)
Referee
GUI (changed to UI in the implementation)
Game Agent (changed to Commissioner in the implementation)
Local Game (changed to Virtual Game in the implementation)
Fault Detector
The Radio Tower actor is charged with all external communications. The Referee
enforces the rules and keeps score. The GUI is the system input and output manager.
The Game Agent manages the players entrance into the game. The Local game is the
manager of the game logic, and thus controls the game on the local level. The fault
Detector manages the heartbeat and checks for faulted players. A detailed listing of
the actor analysis is presented in Appendix B.
Using this list of actors we were able to create the system object diagram that can be
seen in Figure 4.2.1.1. A below.
25


Virtual Quidditch
System Design
The focal point in this diagram is the Virtual Game. The Virtual Game holds all of
the state for the local game. It also contains all of the game logic. The
Communicator is the only link to other games and the Commissioner. The Fault
Detector manages detection and recovery from faults. The User Interface is the input/
output manager that allows the user to interact with the game. The Referee Actor
becomes just another player, and his logic is moved into the Virtual Game. By
creating our design in this manner we have isolated functionality. Our analysis has
shown that changes will also be isolated to one of the system design elements.
26


4.2.1.2 Game Obj ect Design
All objects on the pitch (field) have been designed in the Object Diagram presented in
Figure 4.2.1.2. A below.
Virtual Quidditch
Object Diagram
Figure 4.2.1.2.A Object Diagram
27


This diagram models the inheritance of all objects on the pitch. The bottom most
item is the token base class. From this class all others derive. To the left are the
static elements of the game. To the right are the moving items. Moving Token
inherits from Token and adds a speed property. Up and to the left we have the
GameBall base class. This base class has a pure virtual method moveBall that each
type ball will overload for its particular movement. The three types of balls (Quaffle,
Bludger and Golden Snitch) all inherit from GameBall. Back down to Moving Token
and up to the right we have the class Player Controlled Token. This class inherits
from Moving Token and adds the additional properties: health, broom, position, team,
net Address and ordinal Value. The Player Controlled Token class has several pure
virtual methods (Catch, Throw, Hold, Strike, MakeCall). The player classes (Keeper,
Chaser, Beater, Seeker, and Referee) use Player Controlled Token as base class. The
base methods of Player Controlled Token are overloaded to give the functionality
desired for each type of player.
4.2.1.3 Object Oriented Development
The use of Object Oriented techniques was carried over into the implementation of
Virtual Quidditch. Python [Lutz 1996] was selected as the implementation language.
Python is an object oriented scripting language. Python was designed to interfaces to
other languages to allow integration of efficient components built in complied
languages. Python also is a multi-platform environment similar to Java. This will be
28


discussed further in section 4.3.2 (Intended Platform). The decision to use Python
effectively changed our target machine to the Python virtual machine. Our goals
stated that the target machine be as general as possible. The use of object technology
promotes reuse and modularization of the implementation. Further object technology
promotes generalization and abstraction. Throughout out this thesis all of these
techniques are used.
4.2.1.4 Benefits of Using Object Oriented Techniques
Before moving on to the next section we thought that we should point out some of the
benefits from the use of object technology. The reuses of the token-passing algorithm
for distributed processing (section 4.4.2.3) were major steps in simplifying the
system. Not only were we able to reuse code via inheritance, but the system design is
radically simpler by this reuse. The object model used in the design of game objects
(section 4.2.1.2) was beneficial in keeping uniformity and simplicity to the
implementation of the game objects. Using inheritance we were able to separate the
performance logic of each object. Further we were able to create a hierarchy of game
objects, as more intelligence was needed. Last we used a message class for use in all
message passing (both internal and external) that again, created uniformity and
simplicity to the implementation.
29


4.2.2 Intended Platform
The goals of the game presented in section 4.1 (System Goals) state that the system
needs to be as platform independent as possible, in terms of both hardware and
software. The software environment under which we operate needs to be as open as
possible. At the same time we cannot plan the use of special purpose hardware to
help us. In this section we will discuss how this is implemented in Virtual Quidditch.
4.2.2.1 Independence Achieved by Using Python
Platform independence is achieved in one of two ways. We can produce a version of
our system for every platform we need, or we can use a level of indirection and
develop for a virtual machine. We chose the latter of these options. The project
team is currently using the platform independent language, Python. We chose to also
use Python in the development of Virtual Quidditch.
Python is an open source interpreted language that prides itself on simplicity and
elegance. The development team for Python has ported it to the most common OS
platforms (Mac, Windows, most Unixs). It should be noted that by taking this option
we have just deferred the responsibility for porting between platforms to the
developers of the Python virtual machine. There are many development
environments currently available to aid in production of Python software.
30


Pythons interpretive nature allows developers to interactively develop software.
This highly interactive development is one of the key requirements of RAD, extreme
[Beck 1999], and other development methods. These methods strive to bring quality
software to market in a much quicker development phase.
4.2.2.2 Effects on Communications
Part of our intended platform is the communications equipment to be used. Like
other equipment in this project our communications equipment cannot be of any
predetermined type. Earlier in section 3.3.3 (Communications) we had made an
estimate of 360 movement messages a second need to be sent or received by the local
game. While this is not huge, it is significant using commodity grade
communications equipment. Concerned that bandwidth would be a problem we
decided to use UDP [Stallings 1997] for transferring data between machines. UDP is
a veiy fast commonly used data transfer method. However UDP is also what is
considered an unreliable protocol, not guaranteeing delivery of a packet. Since our
design isolates the external communications of the system to the Communicator
object, we felt that it would work best to start with a fast protocol to make sure that
speed was not a problem. In future work we can explore switching to a more reliable
communications protocol.
31


4.2.2.3 Hardware We Cannot Depend On
Our goals require development for the parallel execution and distribution. The goals
also require platform independence, implying that we cannot depend on specific
hardware to help us. This hardware restriction is very significant, as we will see later
in the System Robustness Model. There are distributed systems, which provide the
performance we are seeking. We feel that it is important to take a short survey of
equipment available for this purpose. A high-speed interconnection network [Jordan
2002] would be very beneficial. Reducing latency issues that are very significant in
our design. Array processors could be helpful to a lesser extent. Cluster computing
[Barkia 2001] could be used both for fault tolerance and rendering of player
perspectives. These and more technologies would be helpful in the development of
Virtual Quidditch, however in our opinion they would be considered special
equipment and thus we cannot plan on their use. This is not an exhaustive list but
rather a sample to give the reader an idea how the project could have been helped
through specific hardware.
4.2.2.4 Other Possibilities
As mentioned earlier there are other methods of achieving the platform independence
we desire. The traditional method is to create a port version for each desired
platform. This is usually the method used when a third generation language compiled
language (C, BASIC, Fortran, and others) are used. Although this solution is very
32


straight forward, it quickly becomes complex managing multiple versions of the
software [Bersoff 1984],
Java is currently enjoying a strong popularity (and use). The motto, compile once
and run anywhere, speaks right to the market we are trying to develop for. Java is an
object-oriented language with strong support environments available. Java would be
a good alternative environment for the development of Virtual Quidditch.
4.2.3 Robustness
4.2.3.1 System Developed Coarse-Grained and Distributed
Our goals describe a system that distributes processing as much as possible. Because
we cannot expect any special purpose equipment to be used we must assume that
there can be high latency in message communications. These conditions will force
the system to be designed in a coarse-grained nature. In the next section we will
analyze this using the System Robustness Model. Keep in mind the give and take
nature of these two models. Software Life Cycle Enhancement Techniques and
Intended Platform effect the development of system robustness. System robustness
will intern will effect Software Life Cycle Enhancement Techniques and Intended
Platform.
33


4.3 Virtual Quidditch as Seen by the System Robustness Model
In this section we will show the implementation of Virtual Quidditch as applied to the
System Robustness Model to demonstrate how the various elements of Virtual
Quidditch interact.
4.3.1 Distributed Processing
In the development of the Virtual Quidditch system one of the stated goals is that the
game should distribute processing as much as possible. This goal strives to have as
flat of a logical hierarchy as possible. Passed down from the Target Market Model is
another goal to allocate resources via the Internet. This will greatly affect the
resulting game, as we will see throughout the System Robustness Model.
4.3.1.1 Game Layout
Although not stated specifically the implication of the stated goals was to have each
player on a separate machine. This is how the game is designed to function.
However it is also possible for a single machine to host multiple players, limited only
by the power of the machine. Realistically though, the game is a high speed
(simulated real time) interaction of players using a GUI. It is difficult for users to
realistically interact on a shared machine without multiple screens and keyboards.
The game layout is pictured in Figure 4.3.1.1 .A below.
34


Virtual Quidditch
Physical Game Layout
Figure 4.3.1.l.A Physical Game Layout
The game as defined in section 4.1.1 (Short description of Quidditch) has fourteen
players, and one referee. This is nice for our development in that we have a small
number of players (networked components). Further we have an unlimited number of
backup players. These backup players are users that have registered to play, and have
35


yet to enter the game. These players are listening for their entrance into the game, but
are presently available to do other computing tasks.
We have added an additional component to the game called the Commissioner.
This component provides a physical address (an IP number) for the players to log in
to. Further the commissioner also provides the connection information for players
entering the game. This entry can be either during the game startup or as players fault
and need to be replaced. Currently the commissioner component is implemented as a
website. In future work this component could be moved to be a regular replaceable
component (like other non-player objects).
Players communicate using the IP protocol. In order to allow more than one player
on a computer, players can be assigned different port numbers. By using IP we are
able to transparently communicate both locally and remotely. Currently we have
implemented communications using UDP datagrams [Stallings 1997] and a custom
message class. Future work could involve a change to using XML [St.Laurent
1999], This would require a change to using TCP/IP and communicating using the
HTTP protocol. Our design (see section 4.2.1) has isolated communications to a
single object to aid in this and other communication changes. A move to XML would
allow a much more dynamic messaging. XML would also allow players to cross
36


Internet firewalls, the current UDP implementation will not. As might be expected the
unreliable nature of UDP is problematic in the currently implemented
communications. It appears the some of our message packets are getting dropped.
This problem is most prevalent in communications with the commissioner.
We have developed a custom message class for communications both internal and
external to the local game. By defining a message class we have created a common
abstraction for all messages. This common abstraction simplifies synchronization.
As will be described further in section 4.3.3 (Synchronization). The abstraction
allows for variable number of parameters. It is through these parameters that we can
customize for all types of messages.
4.3.1.2 Game Distribution
Above we described the physical game layout, now we address how the game is
logically partitioned. Keep in mind the goal for a flat (as distributed as possible)
hierarchy. Also keep in mind that we have several components which are not owned
by any player (non-player controlled objects). In this section we will address how
Virtual Quidditch distributes processing of the game.
37


Players are running a version of the game on their local machine. The games
communicate together to form a system. Virtual Quidditch is this system of games.
By having the local machine render the local players view to the screen we are
parallel processing the largest segment of computation in Virtual Quidditch. Thus
our speedup over the hierarchical model is considerable. The logical game layout is
pictured in Figure 4.3.1.2. A below. Note that the diagram does not include all
possible players.
38


Virtual Quidditch
Game Layout
Figure 4.3.1.2.A Logical Game Layout
The game progresses in increments of one tenth of a second [Conway 1997] with the
movement heartbeat discussed earlier in section 3.3.3. At the present we have yet to
determine if this threshold is feasible using commodity grade equipment. In each
heartbeat the local player notifies all other players of its position and speed vector.
39


Each players game accepts message updates from the other players and calculates
their effect on the local game.
Each player keeps a copy of the entire state of the game (described earlier in section
3.3.2). This is because the local player will need all of the state to render the game to
the screen. Because of this we do not need to move more than position and speed
information from player to player on regular intervals so although movement
information (state) is continually being updated the bulk of the game state is not
changing regularly. In understanding how Virtual Quidditch operates we think of
each player as having a complete state of the game. This will be discussed further in
section 4.3.3 (Synchronization).
In order to keep our hierarchy flat each non-player-controlled object is processed by
all players. The processing is done round robin style [Silberschatz 1999] and the
algorithm will be discussed in detail in section 4.3.2 (Fault Tolerance). Like the
player movement this processing proceeds at a given heartbeat interval. This
heartbeat is separate from the movement heartbeat and so can be much slower.
Whichever player is processing for the non-player-controlled object at any given
time, will notify all other players of the actions of this object. Again this notification
is done via our standard message object.
40


The Commissioner solves the problem of how players find the game. Since the
players run the game ultimately there needs to be a universal address of where they
can start. Implemented as a website, the Commissioner keeps track of game players
and players on reserve. As players are added to the game the Commissioner notifies
them of the other players in the game. All of this processing could be implemented as
just another non-player controlled object, but we would still need a universal starting
point. See section 5.2 (Future Work) for more details on this possibility.
Other than meeting our stated goal of maximizing the distribution of processing, what
have we gained? Each local game is processing its own user interface. The rendering
of the game to the screen promises to be one of the most computationally intense
elements of the game. By having each local game rendering its own game we are
achieving significant speedup [Jordan 2002], Because of this speedup we can use
commodity grade equipment rather than high performance servers to process the
system.
4.3.1.3 Other Possibilities
Instead of distributing the processing extensively we could, use a client server
approach. In such an approach we would build the game to run on a single server
machine. This machine could be clustered and have redundant backup systems. Each
player would operate as an input/ output device. The server could stream the visual
41


representation to the local player. The resulting system would be hierarchical, but
would present a unified game to all players. Furthermore the hardware required for
the server machine would not be commodity grade.
Another approach would be to move the entire processing for the game among the
players round robin style. This would be an incremental computing approach. As
each player designated to do the computation, they would add their input and
compute the result on the game, then pass processing to another player. This design
is dependent on being able to move the processing though all players fast enough as
to give the impression that each player is interacting with the other players (again
simulated real time). We chose not to use this approach because we felt it would not
present as good of game to the players. We felt it was less likely to give the
impression of real time interaction. The player would only interact once each time
around the loop of players. This method would also create an order to player
movements. This could affect the game play.
4.3.2 Fault Tolerance
Fault tolerance can be built to varying levels of coarseness. The synchronization and
distribution techniques used interact with fault tolerance to determine the level of
granularity that can be effective. This will be a major factor in how we implement
Virtual Quidditch. As with Distribution Techniques presented above several of the
42


goals will pass through the Target Market Model to put requirements on the Fault
Tolerance in the System Robustness Model.
4.3.2.1 Coarse-Grained Fault Tolerance
The fault tolerance implemented in Virtual Quidditch is very coarse-grained. This is
a reflection of the other two components of the System Robustness Model.
Synchronization (section 4.4.3) is also coarse grained, and Distributed Techniques
have maximized distribution of processing while removing the use of special
hardware. In this section we will elaborate on the algorithms used to implement our
fault tolerance techniques. Then we will demonstrate how we have been able to
generalize our algorithm to support processes other than system fault tolerance.
Coarse-grained fault tolerance works on higher logical level that fine-grained. Its
main purpose is not to keep lower logical levels running to their completion. Rather
its purpose is to manage the system and keep faults at lower levels from affecting
other logical items at its level. Coarse-grained mechanisms usually do not actively
seek to determine a fault has occurred. These mechanisms will more likely use
techniques of notifications, or timers to recognize a fault. Then the code used to
recover is minimal, instead using functionality already built into the system. In the
next several sections we will see how this is implemented in Virtual Quidditch.
43


4.3.2.2 Simple Fault Detection and Recovery
Simply stated the system is unconcerned with keeping a player alive. The system is
built to detect when a player has faulted, and quickly restore each local game to a
correct working state.
At any one time a single game is performing the system fault tolerance algorithm.
This game is called the controlling game. The controlling game takes advantage of
the movement heartbeat discussed in section 4.3.1.2 (Game Distribution). A simple
check to see when the controlling game last got a heartbeat from each player will
yield games that have faulted. The system upon detection of a fault will notify all .
other players of the faulted player. Then the controlling game will remove the
faulting player from its local game. Each local game upon receiving notification of a
fault removes that player from their local game. The controlling game will then poll
the Commissioner for a replacement. Should a replacement be on hand the
Commissioner will add them using the same techniques as players are added at the
beginning of the game. The system is not dependent on the Commissioner sending a
replacement. The system will continue with the existing players until there are too
few players to have a meaningful game (one in the current implementation). Should
there be to few players the controlling game will send out a game end message.
44


This is a very simple method of detection. We have a problem in that it is not fault
tolerant itself Should the controlling game fault there is no way for it to be detected.
To remedy this we have implemented a token passing algorithm to share this
processing among all the games in the system.
4.3.2.3 Token Passing Scheme Used
The algorithm used to determine the controlling game is a simple token ring
[Stallings 1997] algorithm used in networking. The current games forming the
system are kept in a circular list. The token is a logical entity that is passed from
game to game in the list. When a game holds the token it is the controlling game.
Each game processes the simple fault tolerance scheme outlined above for a given
amount of time and then passes the token to the next game. By using a circular list
each game is able to determine where it is in relation to the current holder.
Every time the token is passed all games are notified. Upon notification each game
determines the time it should take for the token to get to it defined as timeToFault
Periodically each game compares the current clock to the timeToFault. If the
current time is greater than the timeToFault then the local game seizes control of
the token by sending a message passing the token to itself.
45


Once the game has seized the token it becomes the new controlling game. As the
new controlling game then executes the simple fault detection algorithm described
above, the faulting player will be removed and a request for replacement made to the
Commissioner. With the addition of the token passing algorithm, now a fault of the
controlling game is recoverable.
4.3.2.4 Roll Forward Technique Used
The system does not aid a new game entering the system by restoring to a previous
correct working state. This is commonly called a rollback [Silberschatz
2002][Haerderl983], In Virtual Quidditch the system rolls forward on a fault.
Because we are attempting to simulate real time interaction among players, the
present is more important than the past. As such, when a new game enters the system
it is expected that they will have to familiarize their self as the game is played.
In the case of Virtual Quidditch, the system will notify the Commissioner of the fault.
It becomes the Commissioners responsibility to replace the faulted player. If no
replacement is available the game continues on regardless, the system is rolling
forward. Hence we roll forward with the players we have, not expecting a
replacement to be added by the Commissioner. When (and if) a new player enters the
game the reconfiguration of the token-ring is automatic, since we are using the same
46


code as when players are added at the game start. The new player must familiarize
himself or herself to the on going game.
The roll forward technique is not new. Rather it is the way fault tolerance was done
before the development of the roll back technique. What is different is that we are
overly stating that fault recovery is limited in scope, and the controlling game will
need to have mechanisms in place to overcome a fault. The system will notify the
controlling game that a fault has taken place, and then will continue on.
4.3.2.5 Scheme Expanded for Other Distributed Functionality
Using the Object Oriented techniques of abstraction and generalization we are able to
separate the fault detection and recovery of the game from the process of distributing
processing (which itself is fault tolerant). Once we have separated the two we can
then use this processing distribution algorithm to process other items. Specifically
our non-player-controlled objects need to be processed by one of the games in the
system. By using our distribution algorithm we can share this processing and
increase the robustness of our system.
First we create an instance of the token-ring algorithm for each object. Next we add
specific code for that object. This allows each object to operate in a different manner.
47


We have three kinds of non-player-controlled objects plus the fault tolerance token.
We have created five token passing instances (there are two bludgers) to handle these
objects in Virtual Quidditch. Should we desire, we could combine the processing for
several of these objects to make a simpler implementation. The net effect is to lessen
the coarseness of our fault tolerance. So, even thought we are managing at a high
logical level, the system gives performance of a much finer grained implementation.
Below are three code segments demonstrating the implementation of the multi-token-
ring distribution algorithm.
48


min
A code sample from the message loop of the Fault Detector
mm
if not self.fdQ.empty():
m= self.fdQ.get(WAIT)
self.parseMessage(m)
for t in self.tokens:
#used
t.tokenComputation.tokenTask()
#token
# Send heartbeat message to all other pi
m= message(O)
m.setSenderld (self.localCommLink)
m.setCommand (Beat)
m.setParameters([self.myOV])
self.pubQ.put(m, 1)
# If the input queue is empty go on
# Get new message
# Figure out what to do with the message
# Loop on the different tokens being
# Perform the task involved with this
# Create message object
# Add sender id
# Add command
# Add player ordinal value
# Place in the publishers input queue
A code sample from inside the goldenSnitch class
The goldenSnitch class has an overloaded property of the tokenTask Class
used by each token type.
mm
def tokenTask(self): # Define the method footprint
if self.tokenRing.live(): # Check to see if I hold the token
self.moveGoldenSnitch() # Call method containing snitch
#movement logic
#Check to see if the fault interval on the fault token has expired
self.tokenBookeeping() # Check to see token needs to
#be passed or if timeToFault has expired
mm
The tokenTask base class used to enable specific functionality for each
token type.
mm
class tokenTask: #define class name
mm
The tokenTask class defines the processing that will be performed when a token of a
ring (virtualTokenRing) is live for processing. This is a base class that defines
structure of the ring processing. This class should be inherited and the task function
overridden for specific behavior.
Class properties:
myOV The ordinal value of the local player
outQ The default output message queue for this task
.mm
49


def___init_(self, outputQ, myOV, commLink, tokenRing): #Define constructor
self.outQ= outputQ # Create local reference to message
# queue
self.myOV= myOV # Create instance value of ordinal value
self.commLink= commLink # Create local copy of my net Address
self.tokenRing=tokenRing # Create local reference to controlling
# ring
def tokenBookeeping(self): # Define method footprint
if clock()> self.tokenRing.waitTill(): # Check to see if time to fault has expired
if self.tokenRing.live(): # Check to see if I hold the token
#lt is time for the local player to pass the token to the next holder
self.tokenRing.passToken(self.tokenRing.getlMextHolder())
else:
#token holder has faulted, restart token with the local player as holder
self.tokenRing.passToken(self.myOV)
def tokenTask(self): # Create virtual method (not really
# necessary in Python )
#A virtual function that should be overridden for specific functionality
pass
Code Sample 4.3.2.5.A Token Ring Class Definition
The first segment is the message loop for the fault detector object. Of particular
interest is the for loop. This structure loops through all defined token types. The
second segment shows a segment of the goldenSnitch class. This segment shows how
we overload the method tokenTask to define specific logic for this ring. The last
segment is the tokenTask class. This is the base class that the goldenSnitch class
above inheirits from. Notice the definition of the virtual method tokenTask. Also
notice the tokenBookeeping method. This method checks the time to fault and if
necessary passes the token. Notice how simple it is for the local game to seize
control of the token by creating a pass-token message to itself.
50


Now notice the effect of our token-ring algorithm has on the Virtual Quidditch
system. We have leveraged the distributed nature of the system to spread out the risk
of a failure. We have distributed the processing of several elements throughout the
system, allowing them to process these non-player-controlled objects. We believe
that the overhead incurred in communications and fault tolerance will be tolerated by
other computations needed by the system. Thus we have increased the robustness of
the system by making it less effected by faults without penalizing any single game.
4.3.2.6 Other Possibilities
There are always tradeoffs made when designing a system. In designing the fault
tolerance of Virtual Quidditch many options have been deemed inefficient because
we already had the movement heartbeat discussed in section 4.4.1.2 (Game
Distribution). With the movement heartbeat we have a constant update of player
activity. Using this information we no longer need to poll other users to check status.
An alternative would be the Bully algorithm [Silberschatz 1999], Using the Bully
algorithm all nodes are actively checking for the same time out event. Once a fault is
detected the node that detected it tries to elect itself as the controller by sending a
message saying so to all other nodes. Should there be a node with a higher priority
which receives the message then it too responds with a message trying to elect itself
51


as the controller. This process continues until the highest available node claims
control.
Another algorithm is the ARC-Net [Stallings 1997] algorithm used in networking.
When a fault is detected in an ARC-Net, a reconfiguration message is broadcast. At
this point all nodes sound off and the ring is dynamically reconfigured. This like the
Bully algorithm above wastes the information on hand from the movement heartbeat.
Further both of these algorithms require quite a bit of communications to resolve a
fault.
None of the alternatives found utilized the information already on hand. Most
required fast communications to be effective. As such none of these alternatives have
been pursued.
4.3.3 Synchronization
In all parallel processing systems synchronization is an important design component.
Synchronization is closely tied with program correctness. In this section we will '
apply the final design element of Virtual Quidditch to the System Robustness Model.
With the model complete we can then assess the Robustness being passed back up to
the Target market Model.
52


4.3.3.1 Use of Coarse-Grained Synchronization
Goals have defined the distribution model to maximize distribution of system
processing. The Intended Platform defined in the Target Market Model is for
computing systems that are accessible through the Internet. These two requirements
effectively make communications very costly. The requirement for commodity grade
equipment has further forced us to implement fault tolerance as coarse-grained
(section 4.4.2). These design elements when put together make coarse-grained
synchronization a necessity.
This is problematic. The game we are creating is a simulation of real time
interactions of players. By definition the real time interaction of any parallel
activities is very dependent on synchronization. In order to minimize the effect of
the coarse-grained nature of our system we have avoided any handshake type
communications. That is to say that the games in the system are designed to operate
by merely informing each other of changes. There is no acknowledgment returned,
nor are there requests for information.
4.3.3.2 Synchronization through Message Passing
Virtual Quidditch uses a simple method for the implementation of synchronization.
Distributed processes communicate via messages as described in section 4.3.1.1
(Game Layout). In order to implement this in a simple and efficient manner our
53


implementation uses a thread-safe queuing technique. The Queue object in the
Python library performs the low-level synchronization we need. So when an object is
created it makes public a handle to its input queue. When another object needs to
send a message it just adds the message to the target objects input queue.
#Player has faulted and I have the token... notify the virtual game
m= message(O) #Create message object
m.setSenderld(self.commLink) #Add my net address to sender id
m.setCommand(Player Fault Detect) #Add message command
#Add parameters
m.setParameters([p, str([self.game.participants[p].ordinalValue])])
self.vgQ.put(m, WAIT) #Add to targets queue
Code Sample 4.4.3.2.A Sample Message Passing
Code sample 4.4.3.2 demonstrates creation and passing of a message. This particular
message is from the fault detector module notifying the virtual game of a player fault.
The message object is created in the second line. Once all of the message properties
are set (lines 3-6) the final line shows the method call to add the message to the queue
(the virtual games queue is used here). The WAIT parameter for the put method tells
the queue to wait (block) for open space in the queue if necessary. The queue class is
built to be thread safe, allowing concurrent access by multiple threads.
54


Every object that makes its input queue public has at least one thread running to
service this queue. The sample below is from the communicator object.
#Loop forever
#get item from queue (waiting)
^Notify other players of position
while 1:
m= self.pubQ.get(WAIT)
if m.command==Beat:
msg= message (1)
msg.setSenderld (self.localAddress)
msg.setCommand (Move)
msg.setParameters
([Player,self.game.participants[netKey(self.localAddress)].location,
self.game.participants[netKey(self.localAddress)].speed, m.parameters[0]])
self.broadcastNow(msg)
elif m.command==Token Pass':
self.broadcastNow(m)
elif m.command==Detect Player Fault:
^commissioner
while self.NotifyCommisioner(m): #Keep trying till a OK response
pass
elif m.command==Player Fault:
self.broadcastNow(m)
elif m.command==End Game:
break
else:
print 'Publisher received unknown message + str(m.command)
#Broadcast token move
#Get replacement from
# Broadcast player fault
^Broadcast game end
#Exit loop
Code Sample 4.4.3.2.B Queue Handler
The Code Sample 4.4.3.2.B above demonstrates how messages are handled by a
simple loop structure. This particular code is from the Publisher queue in the
Communicator. Line 1 creates the looping structure. Line 2 is a call the local queue
object to get the next item from the queue. Note that the get method also uses the
WAIT parameter to block the thread until there are items in the queue. The rest of the
sample shows a series of nested if-then-else statements using the message command
property for determining how to process the message. All low-level synchronization
55


is performed by the Python queue library function using the thread safe queue object.
In using this method for synchronization we have effectively serialized the random
input to this object.
Messages passed to objects across network connections work with the exact same
code as simple inter-game communications. The communicator module determines
the path to the target object.
We have simplified our synchronization to a very simple message-passing algorithm.
The coarseness of the system is built into the messages themselves. As mentioned
above the messages do not require acknowledgments. By serializing the arrival of
messages we cannot give an immediate response. Because of this our messages are
notifications as opposed to true interactions.
4.3.3.3 Effects of Coarse-Grained Synchronization
The effects of the coarse-grained nature of the synchronization on the game are
profound. Since we are using a flat hierarchical design, there is no single game that
holds the true state of the game. Each local game holds its game state and is
constantly trying to synchronize this with all other game in the system, which are
trying to do the same thing. Hence at any point in time we can not expect any two
56


games in the system to have the same state, since each local game is constantly
changing its own state.
What does this mean to our game? First there is no correct game since no two
games should have the same state. Second, players will see a different game rendered
to their local UI. Third, the amount of variation will depend on the synchronization
rate of the games. We are trying to determine the fastest clock rate that we can
synchronize by. The system itself will rely on the referee to make the call, as what
he says is final.
This is a key element in the robustness of system, which will be passed back up to the
Target Market Model. This very well could be a key element in which determines the
success of the game in the market place. We are in effect trying to determine the
synchronization threshold to the user.
57


5. Limitations and Future Work
Throughout this thesis we have mentioned areas for future development. In this
section we will first discuss some of the limitations of the current Virtual Quidditch
system, then elaborate on areas for future development.
5.1 Limitations of Current Algorithms
Currently the communications between games and the commissioner are all using
UDP. UDP is an unreliable data communications protocol [Stallings 1997], By
design we have a limited idea of the available bandwidth, therefore a decision was
made to start with a fast communication protocol that we can expect to be supported
on the target machine. UDP however, is proving to be problematic, especially in
communications with the Commissioner. In order to get more reliable
communications we feel that change to full TCP/IP will be warranted in future work.
Further the current UDP implementation is inaccessible to users behind a firewall.
We are fell this will be problematic with our expected user base.
The current communications used by the system is a all-to-all method. This works
fine for the fifteen processing elements we use in Virtual Quidditch. However should
we try to apply this to larger systems this could be problematic. This is an
58


exponential curve on the communications going on internally in the game. It would
not take a very large number of processing elements to outstrip the available
bandwidth for communications.
While our token-ring algorithm for distributing processing is very effective it is also
problematic. Security will be a problem with this algorithm. The algorithm allows
for any processing element in the game to take command of the token. Should a
malicious player desire it would be easy to commandeer the processing for any or all
shared elements.
The fault tolerance is performed using the movement heartbeat. This is the message,
which a game sends to all other games once every heartbeat interval. This is a built
in element of Virtual Quidditch and may not be present in other systems. For use in
other systems adding a heartbeat could be a significant overhead depending on the
system being implemented.
Upon fault Virtual Quidditch will use the roll forward technique discussed in section
4.3.2.4. Using this technique the system does little to introduce new elements
(players) to the system, merely cleaning up after the fault instead. This effectively
moves much of the responsibility for fault handling upon the user system (the local
59


game in our case). It is unclear as to the extent to which this process can be
effectively used in other implementations of our algorithms.
5.2 Future Work
We believe that there is and will be a market for Virtual Quidditch for quite some
time. Currently we have implemented the infrastructure necessary for the game. This
infrastructure includes the communications, fault tolerance and distribution (token-
ring) algorithms. The player objects have been designed and skeleton classes
developed consistent with the object diagram (Figure 4.2.12. A). Thus far we have not
implemented specific logic for either specific game balls or the player types. The user
interface currently presents players rendered as cylinders and makes no differentiation
of player type. In its present state the game cannot be marketed. A significant effort
needs to be made in development of the ball intelligence and player logic. The
rendering to the screen needs to be significantly enhanced to present game in league
with similar games on the market.
The graphical interface has been implemented using the VPython package
(www.Vpython.orgT While this is a nice package for simple three-dimensional
representations we feel that it will not likely support the graphical demands that a
fully functioning game will need.
60


As mentioned several times throughout this paper our current UDP implementation is
problematic and restrictive. Future work in communications should require a move to
a more reliable protocol. Movement through common firewalls is a desirable and
needed development in our communications.
61


6. Summary
Our goal in the development of Virtual Quidditch was to see and analyze the tradeoffs
encountered in development of a distributed system. The Target Market Model and
the System Robustness Models were developed for this purpose. In chapter four we
went through each design element of both models, explaining Virtual Quidditch in
terms of that design element.
The Target Market Model defined a system of games operating on a set of networked
computers. The game running on each computer is constantly trying to synchronize
with all other games, which are likewise trying to synchronize. We have been
successful in identifying the market and using software engineering techniques to
further position the game in the market we have identified. In the goals presented in
the chapter three of this thesis the reader may have noticed that there is nothing about
the quality of the game to be presented. The importance of this will become evident
shortly.
We used the System Robustness Model to analyze the interplay of distribution, fault
tolerance and synchronization. The goals set our distribution of processing to be as
wide as possible. With distribution of processing maximized the System Robustness
62


Model shows us that fault tolerance will have to be coarse-grained. In Virtual
Quidditch we applied some custom algorithms (token passing) and techniques (roll
forward on exception) to successfully minimize the effects of this coarseness.
Using the System Robustness Model again, we see that synchronization is also coarse
because of our maximized distribution of processing. Again we applied techniques to
simplify and minimize the effects of the coarse synchronization. However we are not
sure we can attain the 360 movement messages a second that we have set as our target
synchronization rate.
In applying the analysis of our robustness to the Target Market Model we are unsure
if the level of robustness we desire can be achieved. This may affect our target
market. The user has some expectation of quality, which we have never defined. We
researched animation, and calculated an approximation of the synchronization
necessary to render this approximation. However because our current test system is
limited in scope, we simply cannot tell if this is acceptable to the games user.
If we refer back to the System Robustness Model we see that there is an arrow
pointing from synchronization back to distribution. This implies that distribution is
limited by synchronization. This probably seems counter to intuition, as is commonly
taught that synchronization is a problem with distributed systems, not the opposite.
63


Now let us look at our Virtual Quidditch implementation. We had no problem with
partitioning the computations to maximize distribution. Our problem is that to render
movement to the screen to simulate real-time interactions we need a constant number
of positional updates a second. This is in the problem space and is inherent to the
problem (game) we are trying to solve.
One of our goals in this thesis is to maximize the distribution of processing. Though
not directly stated, the impetus behind this goal is to test the limits of distributed
computing (especially with respect to super computing [Jordan 2002]). The results
we have attained using the analysis of the System Robustness Model speak directly to
this. Virtual Quidditch is easily partitioned into separately computable segments.
The game itself however, places demands on how effective the partitioning can be via
synchronization constraints. The only means we have to counter these demands are
specialty hardware.
Extrapolating from our results we can now make a statement about how effectively
distributed computing can be used in place of super computing. Distributed
computing environments will not be ready to replace super computers, as long as we
have problems whose inherent level of synchronization cannot be met by the
distributed environment.
64


Appendix A. Detailed Game Description
Quidditch Rules:
Object: Each team scores by moving the quaffle ball through the opposing
teams golden hoops. The scoring team receives ten points Play continues until the
golden snitch is captured, with the capturing team scoring 150 points. Team with the
most points when the golden snitch is captured wins.
Teams/ Players: two teams play a game. Each team consists of seven players. These
players are as listed.
1) 1 Seeker This player attempts to catch the golden snitch for his/her team.
2) 2 Beaters These players attempt to protect their team from bludger balls,
and if possible, direct them toward the opposing team.
3) 3 chasers -These players move the quaffle ball up the field and attempt to
score by putting it through the opposing teams golden hoops.
4) 1 Keeper- The goalie. Tries to protect his/her teams golden hoops.
Other objects on the field:
1) The referee
2) Quaffle This is a normal soccer size red ball. The chasers pass it among
themselves. It is affected by gravity.
65


3) Bludgers (two)- These are heavy bowling ball sizes objects. These balls have
been charmed to attack (strike) players at random.
4) Golden snitch This is a walnut sized ball that is self-propelled. It is very fast
and very erratic.
Scoring:
Each time a team is able to push the quaffle through one of the opponents golden
hoops they are awarded ten points. The team that catches the golden snitch is awarded
one hundred fifty points.
Penalties: Quidditch is a contact sport. Players are not allowed to harm the other
teams players. It appears that this is a call made by the referee. Opposing players
cannot knock the quaffle out of the hands of the Keeper without penalty. If a foul is
called on a player, the other team is awarded the quaffle. If a foul is called on a player
attempting to stop another player from scoring, the referee can award a penalty shot.
If, in the judgment of the referee, a players actions are excessive, the player can be
removed from the game.
The Field:
Called a pitch is vaguely defined as soccer sized field. There are no vertical
boundaries. The field is defined by the placement of the golden hoops. These hoops
66


are placed at opposing ends of a field. The hoops are about 50 feet in the air, and are
about a yard in diameter.
Other rules:
1) All players start the game on the ground.
2) Players can be substituted.
3) All players move through the air riding broomsticks.
4) Any player who falls off their broomstick is not replaced.
Game start-up
The game comes together in pickup fashion. Players arrive and state their desire to
play. When enough players are there, then the game begins. In this implementation
we picture an additional object, the League Commissioner. The Commissioner is
responsible for organizing the game, and starting it. Additionally if possible the
commissioner should keep a pool of players (free agents) available for replacement
players. The commissioner never plays the game, and therefore could be a static
implemented differently than other players
The process:
As I currently vision the game it would start as follows:
1) The Commissioners process is started. Players would start their local game,
and apply to play the game at a requested position.
67


2) The player is registered through the Commissioner. This would entail
something like selecting position and team. We could also allow other
individualization at this point. The registering process would setup the
necessary state for the player. As players are added all players state must be
updated to reflect this change in the game.
3) Once a player is registered they allowed to practice until the game begins.
So...
a. A players health would not be carried forward into the game.
b. The pitch would have to be created.
c. Quaffles and/ or bludgers would have to be available. However how
many and how they are added I do not know. There would probably
have to be a regulation set of balls at all times.
d. No referee until game time.
e. When the game start is announced... practice balls are removed, and a
unified release is made. Players are on their own to organize as a team.
4) Things that probably need to happen:
a. Would have a warning time before the start.
b. Commissioner announces two minutes to game time.
c. Commissioner announces 30 seconds to game time.
d. Referee appears and releases the balls.
68


Appendix B. Use-Case Analysis
In this initial analysis we attempted to gather the actors and enumerate their
operations (use cases). The goal of this analysis is to find the actors of the system.
Further each actor will have its operations as broadly defined as possible. If done
correctly, the system should be as open to change as possible. Further, hidden actors
should be rooted out.
Virtual Quidditch -Use Case Operation Analysis
Actor Operation
fault detector
fault detector
game Agent
game Agent
game Agent
game Agent
game Agent
game Agent
game Agent
GUI
Determine when a player is not responding
Notify the Virtual Game when a player is in a fault situation.
game Agent
Receive player requests to play, and put them into practice mode
Notify players of impending game start.
Receive final score.
Keep pool of alternates to be added to game.
Verify live state of player before substituting them into the game.
Receive requests for more players.
Know when both teams have a full squad, so it can start the game
Render the state of the game to the screen. This should be done often
enough to simulate motion.
69


GUI
GUI
GUI
GUI
GUI
GUI
GUI
GUI
GUI or Local
GUI or Local
Local game
Local game
Local game
Local game
Local game
Local game
Local game
radio tower
Receive commands from the user.
Receive from the user command of Change local players direction
Receive from the user command of Change local players speed
Receive from the user command of Change local players view
(direction looking)
Receive from the user command of Local player throws objects
Receive from the user command to catch objects
Receive from the user command to strike objects
Receive from the user command of strike objects with a stick
(direction and speed of swing)
Game Keep the state of the game.
Game Provide information to the User Interface for rendering.
Add new players to the local instance of the game.
Remove a player from the local instance game.
Cancel a player (remove the player without replacing him) from the
local instance of the game.
Request players from the reserve pool
Receive non-local player movements.
Make periodic movements for non-player objects
Have a practice mode
Publish game information (time outs, scores ...)
70


radio tower
Keep track of non-local player connections,
radio tower Accept communications from all other game instances
radio tower Receive game status messages (impending game start, game start, time
out, team scores)
radio tower Publish game start message
radio tower Publish scoring event
radio tower Publish to all other players movement updates of the local player,
radio tower Decode incoming messages from non-local players
radio tower Publish to specific other players notifications,
radio tower or fault detector Keep track of the communication heartbeat.
Referee Keep score
Referee Notify players of game start.
Referee Call player fouls.
Actor Analysis
The following actors have been identified:
Communicator (radio tower above):
The communicator is responsible for all communications among players. Because
each player is running an instance of the game, constant updates are mandatory.
71


The communicator must inform all other players of changes initiated on the local
machine. Like wise the communicator informs the local instance of notifications from
other players. It is currently possible for more than one player to reside on one
computer. The communicator should not initiate remote communications in-between
these instances of the game. Further duplicate commands need to be filtered out.
Fault Detector:
This actors job is to figure out when a player is no longer active. This could be from
communication problems, or simply the player unexpectedly leaving the game.
When such a situation is detected the Virtual Game is notified. The Virtual game
needs to be able to update the list of active players at all times during the game.
The Virtual Game:
The Virtual Game Actor continuously simulates the operation of the game. To do this
it needs to accept input from all other actors (communicator, User Interface, Fault
Detector). The Virtual Game actor maintains all state for the game. Whenever any
other actors make any changes to state, the Virtual Game decides how the change will
be handled and forwards the message.
User Interface:
The User Interface is the graphical display of current game situation. The target rate
of ten times a second to give the illusion of real time motion. The User Interface is
72


that of a first person role player (in game development terms). So the interface only
displays the portion of the game that is visible from his vantage point. At this point
we do not know what the controls of the user will look like. However, we do know
that the user needs to be able to control: speed and direction, view (where they are
looking), catching and throwing objects, beating objects with sticks,, position on
broom (optional)
User:
The user communicates exclusively with the User Interface as described above.
73


References
Barkia, David. Peer-to-Peer Computing: Technologies for Sharing and Collaborating
on the Net. Santa Clara, CA: Intel Press, 2001.
Beck, Kent. Extreme Programming Explained: Embrace Change. Reading, MA:
Addison Wesley Longman, Inc., 1999.
Bersoff, Edward H. Elements of Software Configuration Management. Software
Engineering. Los Alamitos, CA: IEEE Computer Society Press (1997), pp.
320-328.
Bigus, Joseph P., and Jennifer Bigus. Constructing Intelligent Agents with Java: a
Programmer's Guide to Smarter Applications. New York: John Wiley and
Sons, Inc, 1998.
Boehm, Barry. A Spiral Model of Software Development and Enhancement.
Software Engineering. Los Alamitos, CA: IEEE Computer Society Press
(1997), pp. 415-426.
Brooks, Frederick P. The Mythical Man Month: Essays in Software Engineering.
Reading, MA: Addison Wesley Longman, Inc., 1975.
Comer, Edward R. Alternative Software Life Cycle Models. Software Engineering.
Los Alamitos, CA: IEEE Computer Society Press (1997), pp. 404-414.
Conway, Matthew J. Alice: Easy-to-Leam 3D Scripting for Novices. A Dissertation
presented to the Faculty of the School of Engineering and Applied Science at
the University of Virginia, December 1997.
Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. Introduction to
Algorithms. Cambridge, MA: MIT Press, 1990.
Dix, Chris. Working with SOAP, The Simple Object Access Protocol. C/C++
Users Journal, Vol. 19, No. 1, January 2001.
Gamma, Erich, et. al. Design Patterns: Elements of Reusable Object-oriented
Software. Reading, MA: Addison Wesley Longman, Inc., 1995.
74


Gropp, William, Anthony Skjellum, and Ewing Lusk. UsingMPI: Portable Parallel
Programming with the Message Passing Interface. Cambridge, MA: MIT
Press, 1994.
Haerder, Theo, and Andreas Reuter. Principles of Transaction-Oriented Database
Recovery. Computing Surveys, Vol.15, No. 4, December 1983.
Jacobson, I., et. al., Object Oriented Software Engineering. Reading, MA: Addison
Wesley Longman, Inc., 1992.
Jordan, Harry, and Gita Alaghband. Fundamentals of Parallel Processing. Upper
Saddle River, NJ: Prentice Hall, 2002.
Li, M., O.F. Rana, M. S. Shields, and D. W. Walker. A Wrapper Generator for
Wrapping High Performance Legacy Codes as Java/CORBA Components.
SC2000: High Performance Networking and Computing Conference,
ACM/EEEE, Dallas, TX, 2000.
Lutz, Mark. Programming Python. Sebastopol, CA: OReilly & Associates Inc.,
1996.
Martin, James. Rapid Application Development. New York: MacMillan College
Division, 1991.
McCarthy, Bill, and Luke Cassidy-Dorion. Java Distributed Objects. Indianapolis:
Sams, A Division of Macmillan Computer Publishing, 1999.
Mills, Harlan D. Structured Programming: Retrospect and Prospect. Software
Engineering. Los Alamitos, CA: IEEE Computer Society Press (1997), pp.
195-203.
Natarajan, Balachandran, Aniruddha Gokhale, Shalini Yajnik, and Douglas C.
Schmit. Applying Patterns to Improve the Performance in Fault Tolerant
CORBA. Seventh International Conference on High Performance
Computing, ACM/IEEE, Bangalore, India, 2000.
Northrop, Linda M. Object-Oriented Development. Software Engineering, IEEE
Computer Society Press, Los Alamitos, CA, 1997, pp. 148-159.
75


Raymond, Eric S. The Cathedral & The Bazaar: Musings on Linux and Open Source
by an Accidental Revolutionary. Sebastopol, CA: OReilly & Associates Inc.,
OReilly & Associates Inc., 1999.
Rowling, J. K. Harry Potter and the Sorcerer's Stone. New York: Scholastic Press,
1997.
Rowling, J. K. Harry Potter and the Chamber of Secrets. New York: Scholastic
Press, 1998.
Rowling, J. K. Harry Potter and the Prisoner of Azkaban. New York: Scholastic
Press, 1999.
Rowling, J. K. Harry Potter and the Goblet of Fire. New York: Scholastic Press,
2000.
Silberschatz, Abraham, Henry F. Korth, and S. Sudarshan. Database System
Concepts, Fourth edition. New York: McGraw-Hill, 2002.
Silberschatz, Abraham, and Peter Galvin. Operating System Concepts, Fifth edition.
New York: John Wiley and Sons Inc., 1999.
Stallings, William. Data and Computer Communications, Fifth edition. Upper Saddle
River, NJ: Prentice Hall Inc., 1997.
St.Laurent, Simon. XML: A Primer, Second edition. Foster City, CA: M&T Books,
1999.
Vinoski, Steve. CORBA: Integrating Diverse Applications Within Distributed
Heterogeneous Environments. IEEE Communications, Vol. 14, No. 2,
February 1997.
Whisp, Kennilworthy. Quidditch Through the Ages. New York: Scholastic Press,
2001.
Yang, Zhonghua, and Keith Duddy. CORBA: A Platform for Distributed Object
Computing (A State-of-the-Art Report on OMG/ CORBA/ "ACMOperating
Systems Review, Vol. 30, No. 2, pp. 4-31.
76


Raymond, Eric S. The Cathedral & The Bazaar: Musings on Linux and Open Source
by an Accidental Revolutionary. Sebastopol, CA: OReilly & Associates Inc.,
OReilly & Associates Inc., 1999.
Rowling, J. K. Harry Potter and the Sorcerers Stone. New York: Scholastic Press,
1997.
Rowling, J. K. Harry Potter and the Chamber of Secrets. New York: Scholastic
Press, 1998.
Rowling, J. K. Harry Potter and the Prisoner of Azkaban. New York: Scholastic
Press, 1999.
Rowling, J. K. Harry Potter and the Goblet of Fire. New York: Scholastic Press,
2000.
Silberschatz, Abraham, Henry F. Korth, and S. Sudarshan. Database System
Concepts, Fourth edition. New York: McGraw-Hill, 2002.
Silberschatz, Abraham, and Peter Galvin. Operating System Concepts, Fifth edition.
New York: John Wiley and Sons Inc., 1999.
Stallings, William. Data and Computer Communications, Fifth edition. Upper Saddle
River, NJ: Prentice Hall Inc., 1997.
St.Laurent, Simon. XML: A Primer, Second edition. Foster City, CA: M&T Books,
1999.
Vinoski, Steve. CORB A: Integrating Diverse Applications Within Distributed
Heterogeneous Environments. IEEE Communications, Vol. 14, No. 2,
February 1997.
Whisp, Kennilworthy. Quidditch Through the Ages. New York: Scholastic Press,
2001.
Yang, Zhonghua, and Keith Duddy. CORBA: A Platform for Distributed Object
Computing (A State-of-the-Art Report on OMG/ CORBAj. ACM Operating
Systems Review, Vol. 30, No. 2, pp. 4-31.
76