Current work
Click here for the Rendezvous summary.
Click here for latest news.
June 05
We're actually in the middle of testing, results to follow, but in the meantime,
there is now a video of Rendezvous at work.
Feb 05 - Knockabout and Rendezvous, what next? LUCID?
After a great deal of coding, a workable implementation of Rendezvous, running
over Knockabout - in this case with no profiling only recovery mechanisms based
on rules of the Knockabout game - in particular a rule to kick and a rule to
change a player's speed and direction, making the player either move to kick
the ball so that the ball's position could be rectified, or move to its own
ideal position, depending on what seemed better. Interesting results - the
consistency wasn't high, but then the whole system is pretty loosely coupled,
so that's not a big shock, but it seemed fairly random at different latencies
how inconsistent the player's and ball's position would be. Hard to be sure,
but I think that's good! Just need to improve the actual inconsistency a bit
overall - more rules (will need reflection because otherwise the games
programmer is essentially doing all the hard part!), control theory, lots of
stuff to look at. Full details on progress in paper 3
Next I think the plan is to go for integrating Rendezvous with Duncan's work on
LUCID, which segregates peer to peer based nodes into areas of interest, and in
the case of Rendezvous would cut down the necessary network traffic hugely - if
it'd work! That's a NOSSDAV paper idea though, with not much time to do it, and
at the minute not really a clear enough idea of what it'd be about. Might
produce some interesting Rendezvous effects though.
I think looking further in the future, it'd be good to really take a look at the
reflection stuff. The Rendezvous mechanism has been through a load of changes
in the last month or so working towards the ACE deadline - in particular the
removal of reachability needs for calculations. Plus the implementation had a
whole load of interesting effects, especially avoiding the profiling issue
altogether, which was probably the main focus of big blue ball, and something
else we ought to get back to.
Even more work we could do... There's this whole idea about control theory. In
the obvious sense - player control directly, AI players and that sort of thing,
but much more interestingly as applied to Rendezvous as a whole. If the basic
recovery mechanism is the proportional control, and integral control is tied up
in the idea of profiling, leading to the intriguing thought that we might not
have worked out that we also need derivative control yet, and the prospect of
actually being able to tune the Rendezvous mechanism!!
Update - Feb/March 05
Managed to put together the paper for NOSSDAV, and for the first time had an
actual many player implementation of Knockabout and Rendezous, with the help of
LUCID. There were teething problems of course, but the game itself was
fantastic! Really, very good fun, and even held up to people playing in the
same room and talking, because goals managed to get rectified quite rapidly
(few seconds). Lots of "was that you that scored?" conversations, and grumbling
about other people tackling all the time. Very frantic and entertaining. Main
issues were with losing your own player altogether (inconvenient) although
easier to find now with the new map of the game, and one player who lost touch
with the others completely just had his own separate game, which as it
turns out is easier and so he scored a lot - depends if it happens at the start
though as at the start makes all other views consistent and so the other
players tend to be determined to keep the ball on the centre spot! Very hard...
More testing - watch this space!
(Note, for older work go to The story so far)
January - March 2004
The initial stages of Rendezvous were concentrated on more research oriented
goals, seeking out the best means of implementing the Rendezvous concept and
comparing it to previous work in the relevant fields. Initially this focussed
on rollback and other means of correcting errors, plus event aggregation and
methods normally applied to the differences in latencies between cooperating
distributed users in games. A great deal of the research at this stage was
based on the implementation of collaborative computer games where shared state
is used.
Simultaneously, we were also considering the method of implementation of
Rendezvous and exactly how it was expected to interact with the system it was
trying to correct. Various possibilities were considered - in particular
reflection and formal modelling (although we didn't research formal modelling
as we have previous background in that area). We also looked into agents and
their application in both gaming software and collaborative robotics.
Similarly, negotiation of tasks and control theory as the engineering
equivalent of a converging application were also investigated.
As time progressed we were looking deeper and deeper into the most appropriate
use of experimentation to determine our ideal method of progress. We wanted to
form initial results and thorough analysis into both our ideas and our methods
before we took any further steps, as our ideas at this stage are unproven. As a
means of simplifying our initial experiments we did briefly investigate the
equivalences to be found in the field of file synchronisation, where files are
stored on a server and can be altered by different people. This, although
eventually rejected as a backwards step for the research, brought to light a
number of useful theories, especially ideas about the nature of the reflection
required in order to make use of a Rendezvous mechanism.
For instance, when we considered the use of a text document as an example, the
document could be resynchronised easily if different sections of the document
were edited (at least to some extent) but if the same paragraph was altered by
two different users, we would ideally want Rendezvous to encourage the user
still editing to tend towards the text used by the other user - so spell
checkers and inparticular grammar checkers should have an extra level that
looked at the differences in two texts and encouraged convergence with
underlining and suggestions that were along the right lines! We thought that in
fact this required a different degree of reflection - not reflection of the
program or the tasks but reflection only of the state. However, the state is
affected by the processes performed on it, so the program itself my yet come
into the equation.
Research was also carried out into potential conferences and workshops at which
this work could be published for future reference.
Much of the work covered in this section is also mentioned in the
related work section.
Possibilities - some initial ideas on the experiment
- non-real time - ie calendar (bit backwards)
- java RMI or C# equivalent - simulated rendezvous
- robot, simple position or orientation (etc) rendezvous.
March - the experiment and its connection to Duncan's work
With the fundamental details of the experiment now in place, I also needed to
speak to Duncan, who's broadly working in the same group. He has been working
in the area of consistency and entertainment applications with Joe longer than
I have as part of his PhD, and he is also working on his own, related,
experiments on the locally developed distributed augmented reality game. To
summarise, Duncan's work is currently in the area of relevance filtering and
trying to perform peer to peer gaming with low latency. Naturally, Duncan has
looked into consistency, but for the moment that is not his area and so he's
intending to implement a standard TimeWarp consistency method for use with his
own experiments. Later, we plan to make use of that by replacing the TimeWarp
method (or whatever he chooses) with the Rendezvous equivalent to provide an
even greater range of useful results in a second round of experiments on the
game.
Duncan's peer to peer system uses a "Can" peer to peer method, which requires
new members of the peer to peer group to know someone already within the group
(except at the start). Each time a new member joins, the area (within the game)
controlled by each member is divided up, so that every member controls an area
and makes sure that monsters and so on are functioning. These areas are divided
up arbitrarily according to actual cartesian coordinates within the game.
However, the players still maintain control over their own actions, so to
minimise the communications necessary, if a player is the first to move into a
particular area they are delegated the task of looking after that area by the
actual owner (the owner doesn't change) until they leave. It doesn't matter if
the player is already controlling an unoccupied area, as unoccupied areas have
very little activity - just wandering monsters that no one can currently see.
The controller of an area must keep track of both players and monsters within
an area and make sure that they're all aware of each other as appropriate.
Further to this information about Duncan's current status, we also discussed the
Rendezvous Pong experiment at length, and clarified the expectations of it more
thoroughly. As discussed before, the arbitrator used in the Rendezvous Pong
experiment should initially be completely application specific and its methods
completely pre-determined. Later stages will allow it to be extended to cover
more generic problems. The functionality to be applied to the Rendezvous Pong
arbitrator is described below:
If application A controls its paddle and the ball, and application B controls its
paddle...
If the ball leaves A then B experiences disconnection (or delay) before the
ball reaches B, then initially B should simulate its own ball in a trajectory
as close to the original as possible and A should position the now uncontrolled
paddle B in a position in which it is initially ambiguous whether or not B will
hit the ball. If B reconnects before the ball reaches the line where paddle B
waits, then convergence should be relatively simple. However, if the ball
reaches line B, A should see that B has hit the ball - regardless of the
(currently unknown) outcome of B. If B then reconnects at this stage, it will
be able to tell A whether or not it hit the ball. If B did hit the ball
as A has necessarily assumed (hitting the ball wrongly is recoverable, missing
wrongly is not) then the two arbitrators must merely manipulate the still
travelling ball (and paddles) into a convergent position - as by now they are
unlikely to be exactly identical, probably it would be a simple matter to
ensure that once A had hit (or missed) they could have completely converged.
If, however, B had missed the ball when A had assumed that the ball was hit,
the arbitrator for A must then ensure that A does hit the ball on this
turn by encouraging the paddle to arrive in the right position without completely
taking control (so the paddle cannot move without the player chosing to move
it, but the arbitrator could subtley affect the position to ensure that the
ball is hit. Once the ball has been hit it would be an easy matter to ensure
that B misses.
With this system in place it would still be possible for both A and B to miss,
but increasingly unlikely. A and B can still both miss if either A refuses to
cooperate with the arbitrator in the situation described above (so essentially
A misses on purpose) or perhaps in case of a continued disconnection - in which
case it would become unacceptable to continue to guarantee that A hits the ball
just in case B missed as this would make the game unplayable. This situation is
still under consideration
The plans described do, however, lend themselves well to the planned second
experiment, which is intended to incorporate the augmented reality game used in
Duncan's work. In this scenario Duncan's relevance filtering and low latency
work would almost certainly complement the Rendezvous need for convergence, as
the system would be extended to cover a number of players and any relevant
factors which might require convergence after a disconnection/latency incident.
It is anticipated that ultimately these experiments will be furthered with real
life experiments using collaborating robots.
Experiment 1 - the experiment itself
Taking into account our ideas and research so far, we have now formed an
experiment to be carried out to demonstrate and test a simplified version of
the Rendezvous system.
The idea
no rollback
semi-transparent entity to facilitate error corrections
between clients
entity located between processes and shared state
'encourage' convergence of state
'encourage' state not to diverge (eg network disconnection
- may come later)
free running clients (not appropriate to consider
applications where synchronised clocks are essential as these types of
applications should not be operating in the conditions of network latency and
disconnection that we wish to deal with
Hypothesis 1:
An arbitrator can ensure convergence of shared state over a range of
network latencies (includes race conditions)
Hypothesis 2:
An arbitrator can ensure convergence of shared state after disconnection of
clients
The experiment
Pong!
C# application both to fit in with other current work in
the area (this research group) and to enable possible transfer to mobile phone
sockets based communication
artificial delay controller
Stage 1
moving paddles
shared ball
view
application A controls ball
arbitrator must keep player uncertain whether ball has been
missed or not if definite information delayed
A few notes
doesn't need to be completely transparent - access to
application state if necessary (reflection) - going up rather than going down
like normal
make use of application semantics - may be application
specific
work out how to get application information later
somewhat equivalent to engine management - ie user input vs
engine but the arbitrator knows the engine's limits and the car's limits
The plan
Version 1 of the game should simply be put together in a standard OO way, with
the arbitrator clear and distinct but no means for the arbitrator to be
generated at the start. Complete knowledge of the game can be assumed. This
section should work on the ideal arbitrator and collect results to that end
about the difference in timings and positions between Application A and
Application B. Classes should perhaps extend different arbitrators to
experiment with the ideal model whilst keeping all data clean and available.
Following on from the initial tests with a straight forward OO Pong game, means
of creating an arbitrator without prior detailed knowledge of the game code may
be considered - including formal definitions, and reflection.
A few future thoughts
Windy pong?
Pong is quite predictable, it may be too easy to get a
perfect arbitrator - what about having gusts of wind to make the ball hard to
predict? (this may be implemented as part of stage 1)
Smart Phone Pong
Pong is ideally suited to the mobile phone, can we make it
work across the 1 second GPRS delays?
IPv6
Another possible extention.
This limit wasn't bad, over the widely expected range of GPRS
delays, and the playability (given the stage of development of the game)
was reasonable, plus we were reasonably sure that we could work out a new
and improved way of manipulating the rules and the arbitrator so that it
could continue further. However, at this stage we also started to write a paper
for 13th Euromicro Conference on Parallel, Distributed and Network-based
Processing and from there began to consider the wider implications of our
results. This led to the conclusion of the Pong game (for now - we still hope
to trial the arbitrator across GPRS but that we'll be trialling a generic
arbitrator rather than this specific one).
Sept 2004 - The Rules and Variables, Experiment 2: Big Red Ball
Various rules on which Rendezvous will ultimately based were developed from the
original Pong experiment, details of which are described in
Rendezvous paper 2 submitted to WACERTS 04. These rules govern the
underlying premise of Rendezvous, including detection of divergence between
collaborating states, determination of Rendezvous convergence targets and
profiling of each collaborating member in order to anticipate divergence and
deal with errors even during delay conditions.
Before implementation of Rendezvous proper, however, certain details of the
implementation must be properly determined. In particular, the use of critical
variables as a means of detecting a divergence of collaborating shared states,
and also the use of profile variables as a means of determining which of a
given member's real state details are maintained in profiles in other
collaborators. The properties of these variables and their effects on the
system as a whole are notable, as although they appear relatively insignificant
they in fact underpin the operation of the entire system, thus determining its
ultimate behaviour.
Big red ball is an experiment based in the robotics area, with real life
variables put into effect rather than those used in a virtual environment as
they are prone to manipulation to produce expected, rather than accurate,
results unless great care is taken. The robot will push a red ball along
towards a target location whilst also maintaining and recording its profile and
critical variables, thus enabling analysis of the ideal values of these
variables and how they affect the task as a whole.
These results in place, they can be added to existing understanding of
Rendezvous as a mechanism and its expected behaviour.
