Sunday, December 19, 2004

Random Acts

We're working to come up with an approach to enable Croquet-based simulations involving ‘random’ events to be replicated on multiple machines. This is an interesting problem for us because of the fact that replication of computation would also replicate generation of the random numbers to be used in a simulation. This would usually be undesireable. For example, if we create a virtual coin toss simulation in Croquet that is intended to produce a random outcome (the outcome of either "heads" or "tails"), we would have to ensure that what might come up as “heads” on my instance is also “heads” on all other clients in the TeaParty. The problem is that if all of us are replicating the calculation of a random outcome, there would be nothing to ensure that what appears as “heads” on my machine would not be “tails” on yours. Solving this problem has deep implications on making the somewhat non-deterministic ODE (Open Dynamics Engine) integration with Croquet both deterministic and collaborative. Setting aside the obvious philosophical treatise that the act of structuring a form of deterministic randomness in cyberspace might warrant, we're presently considering two practical approaches to this issue.

One approach is to generate results on a master machine (the initiator of the event) and then replicating the random number computation (actually a pseudo-random number computation) on all other machines in the TeaParty (one machine simply tells all the other machines in the TeaParty that a new final result has been produced). In this way, when the triggering event or gesture happens on a particular machine, then that machine consults its own random number generator to produce a result. When the same event or gesture occurs on another machine, the random number generator on that machine is consulted to produce the result. For moderately complex simulations, there will be little guarantee of uniformity across ones that are moderately shared.

Another approach would be to get all participants to behave as if they are using the same random number generator. This would involve creating one random number generator that produces a well-distributed sequence of random values, regardless of which machine originates the request for any one of these values and the resulting sequence would be shared by all members of the TeaParty. In so doing, each request for the next random number would be shared as a TeaParty-wide event by all participating machines and no machine would be permitted to request an additional random number on its own that is not seen by all the other machines. This does not necessarily mean that there would be one generator for all purposes in all simulations running in the TeaParty. There could be one shared generator per ball in a billiards simulation, or one shared generator per billiard table in a simulation, or even one per TSpace. The point being that each of these shared generators is individually a single conceptual generator that is shared by all machines participating in the TeaParty.

1 comment:

Anonymous said...

A cool problem!

For a lot of Croquet applications, simply using pseudo-random numbers would be fine. In a lot of Croquet applications, people are pretty much on their honor not to cheat, anyway.

If you really want random numbers, how about putting the random number generator in its own special TeaParty with just one host in it? The main tea party can then request new random number from the RNG, and when the RNG responds, the messages will be replicated in the standard croquet style.

That is, there are:

RNGParty -- the party for random number generation
RNGHost -- the only host in this party
BridgeParty -- some guys trying to play bridge
Bridge1, Bridge2, ... -- nodes that are members of that party

BridgeParty can send a message to RNGParty that it wants the random number at index 10054, and RNGParty can message back that the random number at index 10054 is 42. The replication seems to work out correctly, from what little I understand of the croquet model.

-Lex Spoon