dkondr - Distributed objects in Croquet
[Recent Entries][Archive][Friends][User Info]
|
12:41 pm
[Link] |
Distributed objects in Croquet
It looks like time for object state synchronization in Croquet is determined by the slowest replica of the object on the net.
Bye, bye dialup...
From Croquet Architecture:
"How does Croquet actually achieve and support such "simultaneity"? What follows is a somewhat simplified walkthrough for what will happen without any error conditions:
Lets first assume that a User A clicks on a hyper-portal P on her/his screen. Actually, before anyone, including User A, sees anything, an event (hyper-portal P has been clicked on by A) gets broadcast to all the users in this space, directed at the DistOb-P. We want to think of DistOb-P as all of its replicas P1, P2, P3, P4, P5, etc. They all get the message-event at somewhat different real-times, but the message-event itself is labeled and ordered, as is their state-history. The replicas start independently computing the future that was implied by this event. They are given a deadline in approximate real-time to compute this future.
Now there’s a tricky part whose details we are going to skip over for the moment. The short version is that we have to ultimately have a distributed atomic transaction on our objects. In other words, at some point the system of replica objects has to commit to the same state everywhere in the same pseudo-time and as close to possible in the same real-time. If things go wrong — and there are many kinds of things that can go wrong in a highly distributed system of machines and networks of different speeds and reliability — we have to make sure that when the dust clears either the entire new version got computed, committed to and labeled, or no part of that transaction happened at all"
...
"Once they all commit to the new versions of their replica objects, they can generate a new display on the screen from the new objects. A very important thing to note here, is that the frame-rate that each user’s computer can generate can be very different because the frame-rate has nothing to do with the simulation processes underneath. They have to track transactionally, but the displays are just viewing processes that view as much as the local machine capacity permits. This is pretty darn cool!
There are some other really nice things that happen naturally with this model of computation. Suppose we set an object in motion. In this scheme, 'setting and object in motion" means that we have a model of what that motion is supposed to be given in real-time units (such as distance or revolutions per second). If the object's motion is uniform, then each replica can “take care of itself ” Regardless of the frame rate and hardware time of a local machine since each replica can compute its future positions quite accurately in a very interesting way that resembles a continuous function of time (i.e., when each machine decides it can compute a frame, it can ask the replica “where are you now?” and each may come up with a different answer because the display question is a real-time question and will be different for each replica on different speed machines. Yet, each replica has the same meaning for its behavior and state). The seemingly more complicated case of an object changing its state in a non-uniform way over time is quite similar and also makes use of the inherent use of relating behaviors to a continuous model of time flow. This is a very general solution for coordination of very large systems.
A Few More Details
How do the objects know whether they should commit or not? They have to coordinate, and the coordination has to be done in a way that is no worse than linear. Croquet’s TeaTime solution to this is to let the initiating object that did the original broadcast decide."
...
"So we can see that real-time here to a user that initiates an action depends on the round-trip time to the farthest away (in Internet temporal terms) user that is in the space (i.e. the report back success or failure, and then the broadcast of commit or undo). Even though many frames per second can be generated by an end-user machine, a frame that shows some new action from an end-user event will be delayed by the round trip time. But this round-trip time is pretty good these days. In sum, this scheme works very well over virtually all of the Internet using only the computers that the end-users already have."
|
|
| | | | From: | ![[info]](http://l-stat.livejournal.com/img/userinfo.gif?v=92.2) dkondr |
|---|
| Date: | October 13th, 2004 02:10 am (UTC) |
|---|
| | | (Link) |
|
More about round-trip expectations:
"A user's change change-message will travel round-trip across the network to its farthest reaches so that all the replicas in the system independently commit to the change order. Only then will a new screen display be generated for everyone on the network, one that incorporates the change (viewing processes are only allowed on stable versions of the object). Testing this solution using the Internet, we have found that the speed of this round-trip transaction is good enough to give the impression of simultaneity (the typical round-trip times in the US are about 30 to 60ms, and e.g. from Los Angeles to Magdeburg, Germany the round-trip times are typically around 100ms. The latter just exceeds the 12-frames/second guideline that E&S found was critical for jet fighter simulations)."
| | From: | dkondr |
|---|
| Date: | October 13th, 2004 02:21 am (UTC) |
|---|
| | Object states, messages, histories and real time | (Link) |
|
"The key idea for I/O coordination is that input and output events (to interactive devices) are synchronized with global universal time, which is coordinated among all sites involved in a computation. At the same time, objects behave like processes that exist in time, and each object's behavior is implemented by methods that explicitly manage the temporal evolution of the object. In a sense, object internal states are maintained as ordered histories, and operations are performed at ""pseudo-time" instants that are properly ordered with respect to I/O operations whose data connect with the objects.
Device I/O is temporally ordered as well. I/O events exist in real time, and provide the coordination between real-time and pseudo-time that is necessary and sufficient to achieve the proper user interface behavior. This provides an adaptive approach to real time programming that is not limited to real-time programming."
"Croquet objects interact by exchanging messages. The Croquet view of objects easily incorporates I/O devices, and even real-world objects outside the system, as first class objects in a natural way, whereas modeling objects as abstractions of storage only cannot represent such things as normal objects.
In Croquet, computational time and real time are loosely coupled. The code that executes the dynamic behavior of objects typically can execute a lot faster than the real-time behavior represented, so an object can carry out many seconds worth of behavior per second, if left to itself. The Croquet system's job is to coordinate the execution of objects so that all behaviors that can have a visible effect are completed in time to communicate those effects through the system interfaces. Since this is the only constraint, objects in the Croquet environment are free to implement a wide variety of strategies for computing their behaviors. This kind of object-specific strategy dramatically reduces the need for lock-step coordination among distributed concurrent activities. However, because objects maintain some element of past history in their representations, this kind of approach requires additional storage overhead per object. But the benefit of dramatically better scalability and reduced latency far outweigh the cost of extra storage.
The other key idea in TeaTime is our approach to resilience and fault tolerance. Most large-scale distributed virtual environments are quite difficult to handle because at any point in time some elements may become disconnected and other elements may be dynamically added. We recognize this issue in the Croquet object model - each object is responsible for maintaining sufficient information to recover from system disruptions. The key idea in TeaTime is that the state of objects evolves through a distributed two-phase commit protocol. Behaviors of all objects that influence each other are first computed, contingent on completion of all dependent object behaviors, and then those behaviors are atomically committed. If the behaviors are not completed in time, all contingent calculations are undone by the individual objects.
The principle of giving an object responsibility for its own behavior allows for a wide variety of strategies for individual objects to implement the proper resilience and recovery. In a networked virtual environment, these strategies can include dynamically adaptive behavior that can cope with heterogeneous hardware, wide variations of delay, and so forth. Applications programmers can tune applications to use new strategies that derive from the unique requirements of their application objects, or use packaged libraries that embed those strategies in abstract object classes that can be specialized for specific implementation."
|
|
