Smalltalk
› Squeak
› Croquet
›
Croquet - Dev
Re: efficient resync?
Locked
 
|
On Aug 24, 2006, at 8:30 PM, Kyle Hamilton wrote: > Hmm. I'm actually curious if anyone's looked at the Verse project > (http://www.uni-verse.org/) for ideas about synchronization and such. I have now :-) Thanks for the link. Croquet could receive some benefits from implementing the Verse protocol. It would be more efficient for certain media types (both due to the non-TCP/IP protocol, and hard-wired support for specific media types), and would gain interoperability with other applications that implement Verse. However, it assumes that lost packets can be ignored because subsequent packets will contain state that would have replaced the state in the lost packet, had it arrived. This is not suitable for Croquet; since you cannot (in general) predict the recursive changes that a received message will cause in the world. It is also less flexible. In order to support new object types, the protocol spec must be extended. On the other hand, Croquet supports arbitrary late- bound message sends, and therefore doesn't adjustments to its protocol. As a result, Verse might supplement Croquet's native networking protocol, but cannot replace it. Josh > -Kyle H > > On 8/23/06, Howard Stearns <[hidden email]> wrote: >> I'd like to learn how to tell when it's really necessary to resync >> after >> loosing a connection, and whether it's worth it to implement. >> >> While our lab wired networks are solid, wireless can be >> intermittent and >> ISP's sometimes drop folks overnight. Assuming I arrange to re- >> establish >> connection automatically (e.g., connect and login), it might not >> always >> be necessary to sync. And I hate waiting. >> >> One example is where there is no one else from whom to supply a sync: >> you win! Just keep using the island in the state it was in (possibly >> after registering yourself as beServer, setting router time to your >> island time, etc.). >> >> But what about other use cases? One attractive target is "The dropped >> wireless phone call." You and I are talking by cell phone, and for >> whatever silly reason, the call is disconnected. We both want to >> continue the conversation where it left off. Even if I the first guy >> back doesn't have to resync, making the second guy back resync will >> still force the first guy to wait the same amount of real time before >> continuing the conversation. Yuck. >> >> I don't know whether it's worth trying to be clever here. I could >> imagine schemes such as: >> - using consecutively numbered message to determine if we've >> missed a >> message before resync'ing, or >> - examine all the participants' unexecuted time periods >> (participant's >> island time through the timestamp of the last message they do have), >> assemble into continuous chains, pick the chain that has the most >> member's timestamps within the chain, and then distribute that >> chain to >> those members for execution. The others will have to resync. >> >> But it might be the case that while something like these might >> work, the >> performance characteristics are such that they hardly ever really >> help >> you win. >> Ideas? Discussion? >> >> -- >> Howard Stearns >> University of Wisconsin - Madison >> Division of Information Technology >> mailto:[hidden email] >> jabber:[hidden email] >> voice:+1-608-262-3724 >> >> >> > > > -- > > -Kyle H > > > -- > > -Kyle H > |
|
|
I have to wonder if an island that implemented the Verse protocol
could actually be created -- it would, if it kept the state, be able to know what state would have to be transferred. Regardless, Verse is a per-entity protocol. It'd be really good as a "catch-up new clients" protocol, as it would be able to express the current state of all the individual entities at the time of connection, then have the current protocol send the additional messages. (Verse might also work with the time synchronization issue, since it can keep the idea of the time much more closely synchronized than 30,000 queued messages can. If an 'island' is viewed as an entity, then the verse server could keep track of what it was initialized to be, and then update it as new messages are sent out to it.) This might also help solve the "wireless network disreco' problem as well. If the verse server keeps track of what it /should/ be, as well as what messages it hasn't received acknowledgements of, it could determine if a full verse-reset or a message-replay would be more bandwidth-effective. Just some thoughts. -Kyle H On 8/24/06, Josh Gargus <[hidden email]> wrote: > > On Aug 24, 2006, at 8:30 PM, Kyle Hamilton wrote: > > > Hmm. I'm actually curious if anyone's looked at the Verse project > > (http://www.uni-verse.org/) for ideas about synchronization and such. > > I have now :-) Thanks for the link. > > Croquet could receive some benefits from implementing the Verse > protocol. It would be more efficient for certain media types (both > due to the non-TCP/IP protocol, and hard-wired support for specific > media types), and would gain interoperability with other applications > that implement Verse. > > However, it assumes that lost packets can be ignored because > subsequent packets will contain state that would have replaced the > state in the lost packet, had it arrived. This is not suitable for > Croquet; since you cannot (in general) predict the recursive changes > that a received message will cause in the world. It is also less > flexible. In order to support new object types, the protocol spec > must be extended. On the other hand, Croquet supports arbitrary late- > bound message sends, and therefore doesn't adjustments to its > protocol. As a result, Verse might supplement Croquet's native > networking protocol, but cannot replace it. > > Josh > > > > > -Kyle H > > > > On 8/23/06, Howard Stearns <[hidden email]> wrote: > >> I'd like to learn how to tell when it's really necessary to resync > >> after > >> loosing a connection, and whether it's worth it to implement. > >> > >> While our lab wired networks are solid, wireless can be > >> intermittent and > >> ISP's sometimes drop folks overnight. Assuming I arrange to re- > >> establish > >> connection automatically (e.g., connect and login), it might not > >> always > >> be necessary to sync. And I hate waiting. > >> > >> One example is where there is no one else from whom to supply a sync: > >> you win! Just keep using the island in the state it was in (possibly > >> after registering yourself as beServer, setting router time to your > >> island time, etc.). > >> > >> But what about other use cases? One attractive target is "The dropped > >> wireless phone call." You and I are talking by cell phone, and for > >> whatever silly reason, the call is disconnected. We both want to > >> continue the conversation where it left off. Even if I the first guy > >> back doesn't have to resync, making the second guy back resync will > >> still force the first guy to wait the same amount of real time before > >> continuing the conversation. Yuck. > >> > >> I don't know whether it's worth trying to be clever here. I could > >> imagine schemes such as: > >> - using consecutively numbered message to determine if we've > >> missed a > >> message before resync'ing, or > >> - examine all the participants' unexecuted time periods > >> (participant's > >> island time through the timestamp of the last message they do have), > >> assemble into continuous chains, pick the chain that has the most > >> member's timestamps within the chain, and then distribute that > >> chain to > >> those members for execution. The others will have to resync. > >> > >> But it might be the case that while something like these might > >> work, the > >> performance characteristics are such that they hardly ever really > >> help > >> you win. > >> Ideas? Discussion? > >> > >> -- > >> Howard Stearns > >> University of Wisconsin - Madison > >> Division of Information Technology > >> mailto:[hidden email] > >> jabber:[hidden email] > >> voice:+1-608-262-3724 > >> > >> > >> > > > > > > -- > > > > -Kyle H > > > > > > -- > > > > -Kyle H > > > > -- -Kyle H |
|
|
In reply to this post by Joshua Gargus-2
On Aug 25, 2006, at 12:31 AM, Kyle Hamilton wrote: > I have to wonder if an island that implemented the Verse protocol > could actually be created -- it would, if it kept the state, be able > to know what state would have to be transferred. > > Regardless, Verse is a per-entity protocol. It'd be really good as a > "catch-up new clients" protocol, Maybe. It would be "better" than what we currently have (in quotes because the benefits have to be balanced against the additional complexity of supporting it, and for newcomers to understand the big picture). However, I think that something like BitTorrent would be a better fit. Verse appears to be targeted at efficient fine-scale updates to specific types of media data. For instance, an artist can tweak the position of an individual vertex in a mesh; Verse deals with this efficiently. But, since island snapshots are immutable, this capability of verse is of no use. > as it would be able to express the > current state of all the individual entities "all of the individual entities"? Only those types that it supports. In particular, it doesn't support mobile code or tracking the effects on state of arbitrary message sends. Please correct me if I'm wrong. Sorry, I have to run to work. Thanks for the interesting ideas. To summarize, I can't see how Verse can become the main protocol for the transport of Croquet data (because of the provable impossibility of determining all of the state affected by a message without executing it), but it might still be useful as a supplementary method of transferring certain state (although the performance characteristics would have to be compared to those of an overlay network such as BitTorrent, for our particular use case). Cheers, Josh > at the time of > connection, then have the current protocol send the additional > messages. (Verse might also work with the time synchronization issue, > since it can keep the idea of the time much more closely synchronized > than 30,000 queued messages can. If an 'island' is viewed as an > entity, then the verse server could keep track of what it was > initialized to be, and then update it as new messages are sent out to > it.) > > This might also help solve the "wireless network disreco' problem as > well. If the verse server keeps track of what it /should/ be, as well > as what messages it hasn't received acknowledgements of, it could > determine if a full verse-reset or a message-replay would be more > bandwidth-effective. > > Just some thoughts. > > -Kyle H > > On 8/24/06, Josh Gargus <[hidden email]> wrote: >> >> On Aug 24, 2006, at 8:30 PM, Kyle Hamilton wrote: >> >> > Hmm. I'm actually curious if anyone's looked at the Verse project >> > (http://www.uni-verse.org/) for ideas about synchronization and >> such. >> >> I have now :-) Thanks for the link. >> >> Croquet could receive some benefits from implementing the Verse >> protocol. It would be more efficient for certain media types (both >> due to the non-TCP/IP protocol, and hard-wired support for specific >> media types), and would gain interoperability with other applications >> that implement Verse. >> >> However, it assumes that lost packets can be ignored because >> subsequent packets will contain state that would have replaced the >> state in the lost packet, had it arrived. This is not suitable for >> Croquet; since you cannot (in general) predict the recursive changes >> that a received message will cause in the world. It is also less >> flexible. In order to support new object types, the protocol spec >> must be extended. On the other hand, Croquet supports arbitrary >> late- >> bound message sends, and therefore doesn't adjustments to its >> protocol. As a result, Verse might supplement Croquet's native >> networking protocol, but cannot replace it. >> >> Josh >> >> >> >> > -Kyle H >> > >> > On 8/23/06, Howard Stearns <[hidden email]> wrote: >> >> I'd like to learn how to tell when it's really necessary to resync >> >> after >> >> loosing a connection, and whether it's worth it to implement. >> >> >> >> While our lab wired networks are solid, wireless can be >> >> intermittent and >> >> ISP's sometimes drop folks overnight. Assuming I arrange to re- >> >> establish >> >> connection automatically (e.g., connect and login), it might not >> >> always >> >> be necessary to sync. And I hate waiting. >> >> >> >> One example is where there is no one else from whom to supply a >> sync: >> >> you win! Just keep using the island in the state it was in >> (possibly >> >> after registering yourself as beServer, setting router time to >> your >> >> island time, etc.). >> >> >> >> But what about other use cases? One attractive target is "The >> dropped >> >> wireless phone call." You and I are talking by cell phone, and >> for >> >> whatever silly reason, the call is disconnected. We both want to >> >> continue the conversation where it left off. Even if I the >> first guy >> >> back doesn't have to resync, making the second guy back resync >> will >> >> still force the first guy to wait the same amount of real time >> before >> >> continuing the conversation. Yuck. >> >> >> >> I don't know whether it's worth trying to be clever here. I could >> >> imagine schemes such as: >> >> - using consecutively numbered message to determine if we've >> >> missed a >> >> message before resync'ing, or >> >> - examine all the participants' unexecuted time periods >> >> (participant's >> >> island time through the timestamp of the last message they do >> have), >> >> assemble into continuous chains, pick the chain that has the most >> >> member's timestamps within the chain, and then distribute that >> >> chain to >> >> those members for execution. The others will have to resync. >> >> >> >> But it might be the case that while something like these might >> >> work, the >> >> performance characteristics are such that they hardly ever really >> >> help >> >> you win. >> >> Ideas? Discussion? >> >> >> >> -- >> >> Howard Stearns >> >> University of Wisconsin - Madison >> >> Division of Information Technology >> >> mailto:[hidden email] >> >> jabber:[hidden email] >> >> voice:+1-608-262-3724 >> >> >> >> >> >> >> > >> > >> > -- >> > >> > -Kyle H >> > >> > >> > -- >> > >> > -Kyle H >> > >> >> > > > -- > > -Kyle H |
|
|
In reply to this post by Joshua Gargus-2
Kyle-
Thanks for the pointer. I certainly like their take on the value of connected computing! I'm not quite following how this would work for Croquet, either in general or in my resync case. It seems like uni-verse is a well-tuned but ad-hoc protocol for some very specific media types. I'm not quite sure I followed what the "magic" was -- the organizing principle that lets you win over a specific domain -- or what that domain of applicability is. For slowly changing composite media, like meshes, I think I get it. Croquet is good at letting you use different mechanisms for different purposes, and on our project we are using Simplified Tea Time for general collaboration, but we are storing "media" outside the islands. Meshes could be stored in uni-verse as long as the loose coupling of uni-verse time and island/tea time was "good enough." For our project, the media is immutable, but under the right circumstances of "good enough", uni-verse might allow mutability. But uni-verse doesn't seem to be intended, for example, for collaborative streaming media. Only streaming audio has been added, apparently reluctantly, and "Streams are always monaural, there is no built-in support for e.g. stereo; if stereo sound is desired, two channels must be manually synchronized." But synchronization, as I understand it, seems to be explicitly not part of the uni-verse model: "While most commands are order-independent and idempotent, some commands can not be. For these commands, there is a special transmission mode called "ordered". Ordered commands must be delivered to the receiving application in the order sent. This introduces latency, but is the only acceptable way to deal with certain kinds of data." Under these circumstances, I didn't really follow what uni-verse's notion of time is. -Howard |
|
|
In reply to this post by Joshua Gargus-2
Josh Gargus wrote:
> > On Aug 25, 2006, at 12:31 AM, Kyle Hamilton wrote: > >> I have to wonder if an island that implemented the Verse protocol >> could actually be created -- it would, if it kept the state, be able >> to know what state would have to be transferred. >> >> Regardless, Verse is a per-entity protocol. It'd be really good as a >> "catch-up new clients" protocol, > > Maybe. It would be "better" than what we currently have (in quotes > because the benefits > have to be balanced against the additional complexity of supporting > it, and for newcomers > to understand the big picture). > > However, I think that something like BitTorrent would be a better > fit. Verse appears to be > targeted at efficient fine-scale updates to specific types of media > data. For instance, an > artist can tweak the position of an individual vertex in a mesh; Verse > deals with this efficiently. > But, since island snapshots are immutable, this capability of verse is > of no use. snapshots. As you may or may not know, Croquet stores high-res textures outside of the island; low-res textures inside the island may contain a locator object that allows the high-res texture to be resolved at render-time. If the high-res texture is not present on a particular machine, then it can be downloaded from the network. I have generalized this mechanism to support other types of media, adding specific support for video and soon meshes. This type of data is not necessarily strictly immutable. For example, there may be a mesh somehow identified as "hi-res default bunny avatar". If there were to be a master copy somewhere, then it could be gradually refined by artists, and the changes propagated by Verse. I'm not necessarily advocating this approach; I just wanted to highlight the area the Verse seems most promising for. Problems remain: can the "master copy" server handle 100 000 concurrent connections (rough figure, assuming 100 million total Croquet users), or even 1000? Thanks again for your input, Josh |
|
|
In reply to this post by Joshua Gargus-2
I'm going to respond to several mails at once, here... unfortunately,
I'm suffering severe allergies today, and am having trouble putting my thoughts into words. If there's anything you don't understand, chances are I'm not explaining it properly, so just tell me what you understood from what I said and what you're confused about, and I'll see if I can explain it more completely and appropriately. One of the things about Verse is that it was designed to be extensible. Just because something is not currently supported in its media types does not mean that it cannot be. An island snapshot is stable/immutable -- but the island state is unstable/mutable. Having something that can interpret the flow of data to determine how something gets added or modified (since I'm not extremely familiar with the "flow" of teatime or croquet) and use that knowledge to create a verse "snapshot" which can be used to populate a new world-instance. My understanding of the current discussion is that there is a rather large time lag in adding a new world-instance caused by the combination of: a) transmission of an island snapshot b) transmission of all deltas from that island snapshot to current. This appears to be an O(n^(number of participants)) problem. The snapshot is a given size, but the deltas are being generated by each participant. (And, since there is no "master" in the island interplay, there is no central repository for authoritative information.) In order to maintain some kind of order, having a verse-like server would be useful. (If you look at 'meshes' as being 'sets of coordinates with their normals', then individual avatars can be viewed as mesh-points, and the entire set of avatars in the island can be viewed as a mesh. Even if the individual avatars' meshes and textures must be obtained elsewhere, the basic data about where they are and what their orientation is is suited to a verse-type protocol -- as later locations of avatars DO overwrite earlier ones, since a single avatar cannot be in two places at once.) Other aspects of the islands may not be so cut-and-dried. (I'm thinking about things like logo programs -- forward 10, rotate -90, pen down, forward 10, rotate -90, forward 10, pen up, rotate -90, forward 10, rotate -90, pen down, forward 10, pen up.) As the verse documentation states, there are certain types of things that cannot be time-overridden. I realize that the current structure is based on a simplified TeaTime, and I am not suggesting a different basis for that. However, in terms of network resource usage, there ARE things which can be optimized in ways that TeaTime does not, and this discussion specifically brought verse to my mind because of it. (I'm also certainly not suggesting that verse itself would be a good fit for such an optimizing system.) However, I do think that everyone is getting a bit hung up on the concept of 'time'. (Yes, there are time-sensitive events in teatime and croquet -- an example would be sun/moon positioning and thus light sourcing.) But, part of this seems to be based on an idea that the router is going to be queueing up all of these messages and then sending them, serially, to the next instance of the island that comes up. If it takes several days for the next client to connect, this causes problems. And that seems to be where the discussion stands at the moment. I've put forth an idea that I became aware of elsewhere as a discussion point, since obviously SOMETHING needs to be done about this... but I don't know what it is, and nobody's come up with a consensus on what to do yet. As for the Verse master server being able to handle N(huge number) connections, there is only a "proof-of-concept" no-security server available right now. However, the protocol EXPLICITLY recognizes the concept of clusters of verse servers that share data in some as-yet-undefined manner. (In this case, I'm thinking more along the lines of "Second Life-like Asset Server".) If a given 'locator' can be turned into a pointer, and then updated when the mesh it points to is updated, then there wouldn't be any problem with updating the meshes with different versions. (Also: if you have a cluster of verse-like servers, they can individually create the same content stream, which means that they can act like bittorrent peers with built-in trackers.) Anyway. Again, my apologies if this is not understandable -- when I've got this bad of allergies, I tend to go back later and try to figure out what I was trying to drivel on about. I sincerely hope that everyone gets at least something from my ramblings, even if it's just a talking point that could eventually make things "better" (quoted for the same reason that Josh quoted it). Thanks for your time. -Kyle H On 8/25/06, Josh Gargus <[hidden email]> wrote: > > On Aug 25, 2006, at 12:31 AM, Kyle Hamilton wrote: > > > I have to wonder if an island that implemented the Verse protocol > > could actually be created -- it would, if it kept the state, be able > > to know what state would have to be transferred. > > > > Regardless, Verse is a per-entity protocol. It'd be really good as a > > "catch-up new clients" protocol, > > Maybe. It would be "better" than what we currently have (in quotes > because the benefits > have to be balanced against the additional complexity of supporting > it, and for newcomers > to understand the big picture). > > However, I think that something like BitTorrent would be a better > fit. Verse appears to be > targeted at efficient fine-scale updates to specific types of media > data. For instance, an > artist can tweak the position of an individual vertex in a mesh; > Verse deals with this efficiently. > But, since island snapshots are immutable, this capability of verse > is of no use. > > > as it would be able to express the > > current state of all the individual entities > > "all of the individual entities"? Only those types that it > supports. In particular, it doesn't > support mobile code or tracking the effects on state of arbitrary > message sends. Please > correct me if I'm wrong. > > Sorry, I have to run to work. Thanks for the interesting ideas. To > summarize, I can't see how > Verse can become the main protocol for the transport of Croquet data > (because of the > provable impossibility of determining all of the state affected by a > message without > executing it), but it might still be useful as a supplementary method > of transferring > certain state (although the performance characteristics would have to > be compared to those > of an overlay network such as BitTorrent, for our particular use case). > > Cheers, > Josh > > > > > at the time of > > connection, then have the current protocol send the additional > > messages. (Verse might also work with the time synchronization issue, > > since it can keep the idea of the time much more closely synchronized > > than 30,000 queued messages can. If an 'island' is viewed as an > > entity, then the verse server could keep track of what it was > > initialized to be, and then update it as new messages are sent out to > > it.) > > > > This might also help solve the "wireless network disreco' problem as > > well. If the verse server keeps track of what it /should/ be, as well > > as what messages it hasn't received acknowledgements of, it could > > determine if a full verse-reset or a message-replay would be more > > bandwidth-effective. > > > > Just some thoughts. > > > > -Kyle H > > > > On 8/24/06, Josh Gargus <[hidden email]> wrote: > >> > >> On Aug 24, 2006, at 8:30 PM, Kyle Hamilton wrote: > >> > >> > Hmm. I'm actually curious if anyone's looked at the Verse project > >> > (http://www.uni-verse.org/) for ideas about synchronization and > >> such. > >> > >> I have now :-) Thanks for the link. > >> > >> Croquet could receive some benefits from implementing the Verse > >> protocol. It would be more efficient for certain media types (both > >> due to the non-TCP/IP protocol, and hard-wired support for specific > >> media types), and would gain interoperability with other applications > >> that implement Verse. > >> > >> However, it assumes that lost packets can be ignored because > >> subsequent packets will contain state that would have replaced the > >> state in the lost packet, had it arrived. This is not suitable for > >> Croquet; since you cannot (in general) predict the recursive changes > >> that a received message will cause in the world. It is also less > >> flexible. In order to support new object types, the protocol spec > >> must be extended. On the other hand, Croquet supports arbitrary > >> late- > >> bound message sends, and therefore doesn't adjustments to its > >> protocol. As a result, Verse might supplement Croquet's native > >> networking protocol, but cannot replace it. > >> > >> Josh > >> > >> > >> > >> > -Kyle H > >> > > >> > On 8/23/06, Howard Stearns <[hidden email]> wrote: > >> >> I'd like to learn how to tell when it's really necessary to resync > >> >> after > >> >> loosing a connection, and whether it's worth it to implement. > >> >> > >> >> While our lab wired networks are solid, wireless can be > >> >> intermittent and > >> >> ISP's sometimes drop folks overnight. Assuming I arrange to re- > >> >> establish > >> >> connection automatically (e.g., connect and login), it might not > >> >> always > >> >> be necessary to sync. And I hate waiting. > >> >> > >> >> One example is where there is no one else from whom to supply a > >> sync: > >> >> you win! Just keep using the island in the state it was in > >> (possibly > >> >> after registering yourself as beServer, setting router time to > >> your > >> >> island time, etc.). > >> >> > >> >> But what about other use cases? One attractive target is "The > >> dropped > >> >> wireless phone call." You and I are talking by cell phone, and > >> for > >> >> whatever silly reason, the call is disconnected. We both want to > >> >> continue the conversation where it left off. Even if I the > >> first guy > >> >> back doesn't have to resync, making the second guy back resync > >> will > >> >> still force the first guy to wait the same amount of real time > >> before > >> >> continuing the conversation. Yuck. > >> >> > >> >> I don't know whether it's worth trying to be clever here. I could > >> >> imagine schemes such as: > >> >> - using consecutively numbered message to determine if we've > >> >> missed a > >> >> message before resync'ing, or > >> >> - examine all the participants' unexecuted time periods > >> >> (participant's > >> >> island time through the timestamp of the last message they do > >> have), > >> >> assemble into continuous chains, pick the chain that has the most > >> >> member's timestamps within the chain, and then distribute that > >> >> chain to > >> >> those members for execution. The others will have to resync. > >> >> > >> >> But it might be the case that while something like these might > >> >> work, the > >> >> performance characteristics are such that they hardly ever really > >> >> help > >> >> you win. > >> >> Ideas? Discussion? |
|
|
In reply to this post by Joshua Gargus-2
On Aug 25, 2006, at 5:00 PM, Kyle Hamilton wrote: > I'm going to respond to several mails at once, here... unfortunately, > I'm suffering severe allergies today, and am having trouble putting my > thoughts into words. If there's anything you don't understand, > chances are I'm not explaining it properly, so just tell me what you > understood from what I said and what you're confused about, and I'll > see if I can explain it more completely and appropriately. > > One of the things about Verse is that it was designed to be > extensible. Just because something is not currently supported in its > media types does not mean that it cannot be. > > An island snapshot is stable/immutable -- but the island state is > unstable/mutable. Having something that can interpret the flow of > data to determine how something gets added or modified (since I'm not > extremely familiar with the "flow" of teatime or croquet) and use that > knowledge to create a verse "snapshot" which can be used to populate a > new world-instance. Coming up with that "something" is the tricky bit. See below, re: things that can and cannot be time-overridden. > > My understanding of the current discussion is that there is a rather > large time lag in adding a new world-instance caused by the > combination of: > a) transmission of an island snapshot > b) transmission of all deltas from that island snapshot to current. The latter isn't significant. Currently, a snapshot is made upon demand; we don't store an old snapshot + messages. From the time that a new participant asks for a snapshot, it begins to receive exactly the same messages that everyone else gets. It does not have to download and process through a backlog. > > This appears to be an O(n^(number of participants)) problem. The > snapshot is a given size, but the deltas are being generated by each > participant. (And, since there is no "master" in the island > interplay, there is no central repository for authoritative > information.) In order to maintain some kind of order, having a > verse-like server would be useful. > I was going to say that "it seems to me to be O(n)". But I was thinking that "n" is the number of participants. What does "n" signify? > (If you look at 'meshes' as being 'sets of coordinates with their > normals', then individual avatars can be viewed as mesh-points, and > the entire set of avatars in the island can be viewed as a mesh. Even > if the individual avatars' meshes and textures must be obtained > elsewhere, the basic data about where they are and what their > orientation is is suited to a verse-type protocol -- as later > locations of avatars DO overwrite earlier ones, since a single avatar > cannot be in two places at once.) > > Other aspects of the islands may not be so cut-and-dried. (I'm > thinking about things like logo programs -- forward 10, rotate -90, > pen down, forward 10, rotate -90, forward 10, pen up, rotate -90, > forward 10, rotate -90, pen down, forward 10, pen up.) As the verse > documentation states, there are certain types of things that cannot be > time-overridden. The problem is not that many types of Croquet objects cannot be time- overridden. The problem is that even for things that can, individually, be time overridden, other non-time-overridable things might depend on their state. This statement, even elaborated upon, is difficult to grasp without understanding that Croquet is based on "replicated computation" rather than "replicated state". I'll try to say what this means intuitively; below, I provide a pointer to a more rigorous description. Synchronization in Croquet is based on the following notion: if, at some arbitrary point in time, you have replicas with identical state, then if they receive the same messages in the same order, then they will remain in sync. Any messages that are dropped or executed out of order can cause a "Butterfly effect" where the replicas diverge arbitrarily. Here's a contrived but concrete example: imagine a Doomsday Weapon that either melts the world or doesn't depending upon how much light is falling upon a sensor at the instant that someone clicks the Big Red Button. If a blimp/mesh is flying across the sky, then a fortuitously dropped packet might save the world by causing the blimp's shadow to linger a bit longer over the sensor, just as the Button is pressed. Too bad for everyone with decent internet connections! > > I realize that the current structure is based on a simplified TeaTime, > and I am not suggesting a different basis for that. However, in terms > of network resource usage, there ARE things which can be optimized in > ways that TeaTime does not, and this discussion specifically brought > verse to my mind because of it. (I'm also certainly not suggesting > that verse itself would be a good fit for such an optimizing system.) You certainly managed to spark a discussion; thanks. > However, I do think that everyone is getting a bit hung up on the > concept of 'time'. (Yes, there are time-sensitive events in teatime > and croquet -- an example would be sun/moon positioning and thus light > sourcing.) But, part of this seems to be based on an idea that the > router is going to be queueing up all of these messages and then > sending them, serially, to the next instance of the island that comes > up. If it takes several days for the next client to connect, this > causes problems. No, this isn't the way that Croquet works. When the router receives a message, it immediately (well, ASAP) sends a copy of the message to each replica. There is no intentional long-term queuing of messages. Have you looked at the Croquet Programming Guide distributed with the SDK? It has a 15-page section called "Croquet System Overview" that describes the model and implementation far better than I can hope to here. > > And that seems to be where the discussion stands at the moment. I've > put forth an idea that I became aware of elsewhere as a discussion > point, since obviously SOMETHING needs to be done about this... but I > don't know what it is, and nobody's come up with a consensus on what > to do yet. > Your idea will definitely be in my mind when I think about these issues in the future. > As for the Verse master server being able to handle N(huge number) > connections, there is only a "proof-of-concept" no-security server > available right now. However, the protocol EXPLICITLY recognizes the > concept of clusters of verse servers that share data in some > as-yet-undefined manner. (In this case, I'm thinking more along the > lines of "Second Life-like Asset Server".) If a given 'locator' can > be turned into a pointer, and then updated when the mesh it points to > is updated, then there wouldn't be any problem with updating the > meshes with different versions. > I'll have to read the Verse docs more closely. Cheers! Josh > (Also: if you have a cluster of verse-like servers, they can > individually create the same content stream, which means that they can > act like bittorrent peers with built-in trackers.) > > Anyway. Again, my apologies if this is not understandable -- when > I've got this bad of allergies, I tend to go back later and try to > figure out what I was trying to drivel on about. I sincerely hope > that everyone gets at least something from my ramblings, even if it's > just a talking point that could eventually make things "better" > (quoted for the same reason that Josh quoted it). > > Thanks for your time. > > -Kyle H > > > > On 8/25/06, Josh Gargus <[hidden email]> wrote: >> >> On Aug 25, 2006, at 12:31 AM, Kyle Hamilton wrote: >> >> > I have to wonder if an island that implemented the Verse protocol >> > could actually be created -- it would, if it kept the state, be >> able >> > to know what state would have to be transferred. >> > >> > Regardless, Verse is a per-entity protocol. It'd be really good >> as a >> > "catch-up new clients" protocol, >> >> Maybe. It would be "better" than what we currently have (in quotes >> because the benefits >> have to be balanced against the additional complexity of supporting >> it, and for newcomers >> to understand the big picture). >> >> However, I think that something like BitTorrent would be a better >> fit. Verse appears to be >> targeted at efficient fine-scale updates to specific types of media >> data. For instance, an >> artist can tweak the position of an individual vertex in a mesh; >> Verse deals with this efficiently. >> But, since island snapshots are immutable, this capability of verse >> is of no use. >> >> > as it would be able to express the >> > current state of all the individual entities >> >> "all of the individual entities"? Only those types that it >> supports. In particular, it doesn't >> support mobile code or tracking the effects on state of arbitrary >> message sends. Please >> correct me if I'm wrong. >> >> Sorry, I have to run to work. Thanks for the interesting ideas. To >> summarize, I can't see how >> Verse can become the main protocol for the transport of Croquet data >> (because of the >> provable impossibility of determining all of the state affected by a >> message without >> executing it), but it might still be useful as a supplementary method >> of transferring >> certain state (although the performance characteristics would have to >> be compared to those >> of an overlay network such as BitTorrent, for our particular use >> case). >> >> Cheers, >> Josh >> >> >> >> > at the time of >> > connection, then have the current protocol send the additional >> > messages. (Verse might also work with the time synchronization >> issue, >> > since it can keep the idea of the time much more closely >> synchronized >> > than 30,000 queued messages can. If an 'island' is viewed as an >> > entity, then the verse server could keep track of what it was >> > initialized to be, and then update it as new messages are sent >> out to >> > it.) >> > >> > This might also help solve the "wireless network disreco' >> problem as >> > well. If the verse server keeps track of what it /should/ be, >> as well >> > as what messages it hasn't received acknowledgements of, it could >> > determine if a full verse-reset or a message-replay would be more >> > bandwidth-effective. >> > >> > Just some thoughts. >> > >> > -Kyle H >> > >> > On 8/24/06, Josh Gargus <[hidden email]> wrote: >> >> >> >> On Aug 24, 2006, at 8:30 PM, Kyle Hamilton wrote: >> >> >> >> > Hmm. I'm actually curious if anyone's looked at the Verse >> project >> >> > (http://www.uni-verse.org/) for ideas about synchronization and >> >> such. >> >> >> >> I have now :-) Thanks for the link. >> >> >> >> Croquet could receive some benefits from implementing the Verse >> >> protocol. It would be more efficient for certain media types >> (both >> >> due to the non-TCP/IP protocol, and hard-wired support for >> specific >> >> media types), and would gain interoperability with other >> applications >> >> that implement Verse. >> >> >> >> However, it assumes that lost packets can be ignored because >> >> subsequent packets will contain state that would have replaced the >> >> state in the lost packet, had it arrived. This is not suitable >> for >> >> Croquet; since you cannot (in general) predict the recursive >> changes >> >> that a received message will cause in the world. It is also less >> >> flexible. In order to support new object types, the protocol spec >> >> must be extended. On the other hand, Croquet supports arbitrary >> >> late- >> >> bound message sends, and therefore doesn't adjustments to its >> >> protocol. As a result, Verse might supplement Croquet's native >> >> networking protocol, but cannot replace it. >> >> >> >> Josh >> >> >> >> >> >> >> >> > -Kyle H >> >> > >> >> > On 8/23/06, Howard Stearns <[hidden email]> wrote: >> >> >> I'd like to learn how to tell when it's really necessary to >> resync >> >> >> after >> >> >> loosing a connection, and whether it's worth it to implement. >> >> >> >> >> >> While our lab wired networks are solid, wireless can be >> >> >> intermittent and >> >> >> ISP's sometimes drop folks overnight. Assuming I arrange to re- >> >> >> establish >> >> >> connection automatically (e.g., connect and login), it might >> not >> >> >> always >> >> >> be necessary to sync. And I hate waiting. >> >> >> >> >> >> One example is where there is no one else from whom to supply a >> >> sync: >> >> >> you win! Just keep using the island in the state it was in >> >> (possibly >> >> >> after registering yourself as beServer, setting router time to >> >> your >> >> >> island time, etc.). >> >> >> >> >> >> But what about other use cases? One attractive target is "The >> >> dropped >> >> >> wireless phone call." You and I are talking by cell phone, and >> >> for >> >> >> whatever silly reason, the call is disconnected. We both >> want to >> >> >> continue the conversation where it left off. Even if I the >> >> first guy >> >> >> back doesn't have to resync, making the second guy back resync >> >> will >> >> >> still force the first guy to wait the same amount of real time >> >> before >> >> >> continuing the conversation. Yuck. >> >> >> >> >> >> I don't know whether it's worth trying to be clever here. I >> could >> >> >> imagine schemes such as: >> >> >> - using consecutively numbered message to determine if we've >> >> >> missed a >> >> >> message before resync'ing, or >> >> >> - examine all the participants' unexecuted time periods >> >> >> (participant's >> >> >> island time through the timestamp of the last message they do >> >> have), >> >> >> assemble into continuous chains, pick the chain that has the >> most >> >> >> member's timestamps within the chain, and then distribute that >> >> >> chain to >> >> >> those members for execution. The others will have to resync. >> >> >> >> >> >> But it might be the case that while something like these might >> >> >> work, the >> >> >> performance characteristics are such that they hardly ever >> really >> >> >> help >> >> >> you win. >> >> >> Ideas? Discussion? > |
|
|
In reply to this post by Joshua Gargus-2
Perhaps I am misunderstanding the context of the disucssion here, but in
Croquet the "router" is not intended to be a "server". Consequently, I am not sure how the concept of a server enters into message ordering. Josh is right - this is about replicating computation, not state. The abstract definition of teatime/croquet need make no reference to a notion of state, but directly defines the messages generated in terms of the history of messages that have been sent at prior instants of teatime. (there is no "time" in the computational ordering). Teatime instants are bound to real time instants relatively loosely, and the only real requirement is that teatime instants are committed in monotonically increasing order as real time passes at each island instance. This idea of an object being a mapping of input message history to output message history is due to Alan Kay, more or less. The idea of an object as a unit of state storage is a mental crutch that carries over from non-object-oriented thinking (i.e. C++ or Algol). It really belongs with the idea that a variable is a block of memory (rather than a name for an object). |
|
|
In reply to this post by Joshua Gargus-2
On 8/25/06, Josh Gargus <[hidden email]> wrote:
> > > An island snapshot is stable/immutable -- but the island state is > > unstable/mutable. Having something that can interpret the flow of > > data to determine how something gets added or modified (since I'm not > > extremely familiar with the "flow" of teatime or croquet) and use that > > knowledge to create a verse "snapshot" which can be used to populate a > > new world-instance. > > Coming up with that "something" is the tricky bit. See below, re: > things that > can and cannot be time-overridden. That 'something' could fairly easily be a headless island peer that remains connected to the router. I've yet to figure out how to implement that, though. > > My understanding of the current discussion is that there is a rather > > large time lag in adding a new world-instance caused by the > > combination of: > > a) transmission of an island snapshot > > b) transmission of all deltas from that island snapshot to current. > > The latter isn't significant. Currently, a snapshot is made upon > demand; we don't > store an old snapshot + messages. From the time that a new > participant asks for > a snapshot, it begins to receive exactly the same messages that > everyone else > gets. It does not have to download and process through a backlog. ...okay, then I'm confused. What was the problem with WiscWorlds staying up over the weekend, then? > > This appears to be an O(n^(number of participants)) problem. The > > snapshot is a given size, but the deltas are being generated by each > > participant. (And, since there is no "master" in the island > > interplay, there is no central repository for authoritative > > information.) In order to maintain some kind of order, having a > > verse-like server would be useful. > > I was going to say that "it seems to me to be O(n)". But I was > thinking that "n" > is the number of participants. What does "n" signify? O is number of operations, n is number of messages. (Maybe it should be O(n*p), where p is number of participants.) > > Other aspects of the islands may not be so cut-and-dried. (I'm > > thinking about things like logo programs -- forward 10, rotate -90, > > pen down, forward 10, rotate -90, forward 10, pen up, rotate -90, > > forward 10, rotate -90, pen down, forward 10, pen up.) As the verse > > documentation states, there are certain types of things that cannot be > > time-overridden. > > The problem is not that many types of Croquet objects cannot be time- > overridden. > The problem is that even for things that can, individually, be time > overridden, > other non-time-overridable things might depend on their state. > > This statement, even elaborated upon, is difficult to grasp without > understanding > that Croquet is based on "replicated computation" rather than > "replicated state". > I'll try to say what this means intuitively; below, I provide a > pointer to a more > rigorous description. Replicating computation is perfectly fine -- but if the computation has already occurred on at least one node, then why not send the current state (including the results of the computation) when synchronizing? (My understanding of 'replicated computation' is basically this: since there's no desire for a single 'master', instead of having a single machine calculate trigonometry for a given act (such as physics for a simple simulation) and then transmit that all around, the fact that the computation must be performed is sent around, and each node computes it separately.) > Synchronization in Croquet is based on the following notion: if, at > some arbitrary point > in time, you have replicas with identical state, then if they receive > the same messages > in the same order, then they will remain in sync. Understood. > Any messages that are dropped or executed out of order can cause a > "Butterfly effect" > where the replicas diverge arbitrarily. Here's a contrived but > concrete example: > imagine a Doomsday Weapon that either melts the world or doesn't > depending upon > how much light is falling upon a sensor at the instant that someone > clicks the Big Red > Button. If a blimp/mesh is flying across the sky, then a > fortuitously dropped packet might > save the world by causing the blimp's shadow to linger a bit longer > over the sensor, just > as the Button is pressed. Too bad for everyone with decent internet > connections! You're basically trying to solve the "internet musical jam" problem, which is a very hard problem to solve.... and the reason is this: You're trying to use an inherently unreliable link as a reliable link -- meaning, you're trying to "abstract away" the unreliability so that you don't have to take it into account. I think you've just explained, in an extremely succinct manner, why this doesn't work. Thus, I think it's going to have to become a hybrid model (which the developers have suggested as being possible) where certain events MUST be single-computation/replicated-result. > Have you looked at the Croquet Programming Guide distributed with > the SDK? It has a 15-page section called "Croquet System Overview" > that describes the model and implementation far better than I can hope > to here. I've looked at it, but I'm also looking at the discussion here, and the two just aren't meshing. That's why I'm confused -- I view the "Croquet System Overview" as an ideal, and the discussions here as the reality. > > And that seems to be where the discussion stands at the moment. I've > > put forth an idea that I became aware of elsewhere as a discussion > > point, since obviously SOMETHING needs to be done about this... but I > > don't know what it is, and nobody's come up with a consensus on what > > to do yet. > > > Your idea will definitely be in my mind when I think about these > issues in > the future. Even if it ends up getting tossed out, at lhe least I hope its consideration brings about some good. :) > > As for the Verse master server being able to handle N(huge number) > > connections, there is only a "proof-of-concept" no-security server > > available right now. However, the protocol EXPLICITLY recognizes the > > concept of clusters of verse servers that share data in some > > as-yet-undefined manner. (In this case, I'm thinking more along the > > lines of "Second Life-like Asset Server".) If a given 'locator' can > > be turned into a pointer, and then updated when the mesh it points to > > is updated, then there wouldn't be any problem with updating the > > meshes with different versions. > > I'll have to read the Verse docs more closely. Look at the Verse design documentation (akin to the Croquet System Overview). It expresses the concepts more clearly than I can, as I'm not an expert with either Verse nor Croquet (obviously). -Kyle H |
|
|
In reply to this post by Joshua Gargus-2
On Aug 25, 2006, at 10:05 PM, Kyle Hamilton wrote: > On 8/25/06, Josh Gargus <[hidden email]> wrote: > > ...okay, then I'm confused. What was the problem with WiscWorlds > staying up over the weekend, then? > The issue that Howard was describing was about how a participant can automatically recover when the socket-level connection breaks and is re-established. In particular, under what circumstances can the participant avoid a complete re-sync. >> > This appears to be an O(n^(number of participants)) problem. The >> > snapshot is a given size, but the deltas are being generated by >> each >> > participant. (And, since there is no "master" in the island >> > interplay, there is no central repository for authoritative >> > information.) In order to maintain some kind of order, having a >> > verse-like server would be useful. >> >> I was going to say that "it seems to me to be O(n)". But I was >> thinking that "n" >> is the number of participants. What does "n" signify? > > O is number of operations, n is number of messages. (Maybe it should > be O(n*p), where p is number of participants.) That sounds more like it. >> >> The problem is not that many types of Croquet objects cannot be time- >> overridden. >> The problem is that even for things that can, individually, be time >> overridden, >> other non-time-overridable things might depend on their state. >> >> This statement, even elaborated upon, is difficult to grasp without >> understanding >> that Croquet is based on "replicated computation" rather than >> "replicated state". >> I'll try to say what this means intuitively; below, I provide a >> pointer to a more >> rigorous description. > > Replicating computation is perfectly fine -- but if the computation > has already occurred on at least one node, then why not send the > current state (including the results of the computation) when > synchronizing? > When you sync and receive a snapshot, this is what does happen. The new joiner doesn't receive all of the messages from the beginning of time. Instead, they receive a snapshot which is a serialized version of all of the objects in the island (including their references to one another). In my "intuitive" description from the last mail, I was careful to say that the replicas are in sync at some arbitrary time, rather than that the replicas start synchronized. Sending the entire state of the world to a new participant is the way that the new participant is brought up to date. Subsequently, replicated computation keeps them in sync. > (My understanding of 'replicated computation' is basically this: since > there's no desire for a single 'master', instead of having a single > machine calculate trigonometry for a given act (such as physics for a > simple simulation) and then transmit that all around, the fact that > the computation must be performed is sent around, and each node > computes it separately.) > This is correct. >> Synchronization in Croquet is based on the following notion: if, at >> some arbitrary point >> in time, you have replicas with identical state, then if they receive >> the same messages >> in the same order, then they will remain in sync. > > Understood. <snip "Butterfly effect"> > You're basically trying to solve the "internet musical jam" problem, > which is a very hard problem to solve.... and the reason is this: > You're trying to use an inherently unreliable link as a reliable link > -- meaning, you're trying to "abstract away" the unreliability so that > you don't have to take it into account. > > I think you've just explained, in an extremely succinct manner, why > this doesn't work. But it does work! Howard's original question is not about what to do when packets are lost. We have (at least an interim) answer to that question: TCP provides reliable, in-order transmission. This allows us to avoid the bufferfly effect at the expense of some additional latency. So far, the tradeoff seems to be favorable (unless you want to build a 1st-person shooter on top of Croquet). > > Thus, I think it's going to have to become a hybrid model (which the > developers have suggested as being possible) where certain events MUST > be single-computation/replicated-result. > I agree that certain events must be SC/RR, but not due to the model requiring this for synchronization. *I* am not a replicated computation. I have only one body with two hands typing on this keyboard. If you consider the stream of keystrokes that I generate as a computational process (which it is), then it is clear that it must be SC/RR. The same goes for webcams, etc. A related use case is visualizing a supercomputer simulation within Croquet. Obviously my PowerBook can't simulate a nuclear reaction in a timely manner; instead, we use Croquet to allow multiple participants to interact with the simulation at the same time. It is scenarios like the latter that caused the architects to ensure that a hybrid approach is possible. People who own supercomputers tend to have deep pockets :-) >> Have you looked at the Croquet Programming Guide distributed with >> the SDK? It has a 15-page section called "Croquet System Overview" >> that describes the model and implementation far better than I can >> hope >> to here. > > I've looked at it, but I'm also looking at the discussion here, and > the two just aren't meshing. That's why I'm confused -- I view the > "Croquet System Overview" as an ideal, and the discussions here as the > reality. > If I haven't helped to clear things up, keep the questions coming. >> >> I'll have to read the Verse docs more closely. > > Look at the Verse design documentation (akin to the Croquet System > Overview). It expresses the concepts more clearly than I can, as I'm > not an expert with either Verse nor Croquet (obviously). Thanks, Josh > > -Kyle H > |
|
|
In reply to this post by Joshua Gargus-2
On Aug 26, 2006, at 1:37 AM, Josh Gargus wrote: > > When you sync and receive a snapshot, this is what does > happen. The new joiner doesn't receive all of the messages > from the beginning of time. Instead, they receive a snapshot > which is a serialized version of all of the objects in the island > (including their references to one another). > > In my "intuitive" description from the last mail, I was careful to > say that the replicas are in sync at some arbitrary time, rather > than that the replicas start synchronized. Sending the entire > state of the world to a new participant is the way that the new > participant is brought up to date. Subsequently, replicated > computation keeps them in sync. I just wanted to emphasize this point. In a meaningful sense, a new participant is not "playing Croquet" until it has already synced and is participating in replicated computation (i.e. it is using Simplified TeaTime). For those who are intimately acquainted with Croquet's design and implementation, it is typically clear from the context whether we mean all-of-Croquet or just Simplified Teatime. This may not be clear to other readers; this email is partly an attempt to drive this into my own head, so that I cause less confusion in the future :-) Specifically, when I said that a hybrid approach is possible but not necessary in Croquet, I was more accurately referring to Simplified TeaTime. Cheers, Josh |
«
Return to Croquet - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |