Hi Torben, Consider state space (called a linear history buffer in other OT literature) to be a persistent message queue. In distributed computing we use sequence numbers to track which messages have been received by the consumer of the message queue. In the event of a communications failure, messages may be lost (eg, messages that are in flight, or perhaps rollback occurred if there was a crash). Upon reconnection, simple handshaking where sequence numbers are exchanged is sufficient to determine what needs to be resent. The "server revision" number represents this sequence number.
In the more general OT approaches where peer to peer connections are made (ie, not forced to be client/server as it is in Wave), a vector of (site id, sequence number) - often denoted as an (s, t) pair - are used in place of a simple sequence number. This vector is called a Vector Time and represents a snapshot of the document that includes all operations that are "in" the vector time - that is, all operations from each "s" that have a sequence number less than "t". I find it interesting that upon reconnection after a crash and rollback, you might get back operations that you generated and sent to another node only moments before your crash. That's just one exciting feature of OT - fault tolerance. It seems that what you are missing is the handshaking (exchange of equence numbers) during reconnection - would you agree? Cheers, Dan On Jan 21, 4:41 am, Torben Weis <[email protected]> wrote: > Hi Brett, > > I think we had a little misunderstanding with regard to my initial problem. > > In your example, what would happen if Client1 lost connection to the server > after step3? > Upon reconnect it does not know whether its in-flight delta has been > accepted or not > and it as IMHO no chance of finding out. So should it send the delta again > or not? > > As long as there is no such crash (as in your example), it will of course > converge properly. > > Greetings > Torben > > 2010/1/20 Brett Morgan <[email protected]> > > > > > Heya Torben, > > > I have attached a java class that I believe implements Daniel's scenario. > > First off, note that I'm not implementing the wave federation algorithm, as > > federation isn't my goal. My goal is to build web apps that use wave's OT. > > That said, here is the output of the aforementioned java class showing that > > the server and the two clients converge. > > > State of system after step 1 > > server editHistory[0]: > > Client 'Client1' at server revision 1 with document > > Client 'Client2' at server revision 1 with document > > State of system after step 2 > > server editHistory[0]: > > Client 'Client1' at server revision 1 with document ++"Hello"; with edit > > in flight ++"Hello"; > > Client 'Client2' at server revision 1 with document > > State of system after step 3 > > server editHistory[0]: > > Client 'Client1' at server revision 1 with document ++"Hello"; with edit > > in flight ++"Hello"; > > Client 'Client2' at server revision 1 with document ++"Hello"; with edit > > in flight ++"Hello"; > > State of system after step 4 > > server editHistory[0]: > > Client 'Client1' at server revision 1 with document ++"Hello"; with edit > > in flight ++"Hello"; with cached edit __5; ++"Going to hell"; > > Client 'Client2' at server revision 1 with document ++"Hello"; with edit > > in flight ++"Hello"; > > State of system after step 5 > > server editHistory[0]: > > server editHistory[1]: ++"Hello"; > > server editHistory[2]: ++"Hello"; __5; > > Client 'Client1' at server revision 2 with document ++"Hello"; with cached > > edit __5; ++"Going to hell"; > > Client 'Client2' at server revision 2 with document ++"Hello"; > > State of system after step 7 > > server editHistory[0]: > > server editHistory[1]: ++"Hello"; > > server editHistory[2]: ++"Hello"; __5; > > server editHistory[3]: __10; ++"Going to hell"; > > Client 'Client1' at server revision 4 with document ++"HelloHelloGoing to > > hell"; > > Client 'Client2' at server revision 4 with document ++"HelloHelloGoing to > > hell"; > > > On Thu, Jan 21, 2010 at 7:15 AM, Torben Weis <[email protected]>wrote: > > >> Hi Brett, > > >> thanks for the hint to your project. I did not know it before. > > > It had it's coming out party at LCA. And I think I'm going to rip it down > > and start again, this time using long poll based notification. I couldn't do > > long polls while I was targeting AppEngine as my deployment environment. > > >> However, I would like to see a proof (i.e. a short explanation is > >> sufficient) how you intend to solve the problem I have mentioned. > >> Running code is no proof :-) > > > If running code doesn't merit existence proof status, then i'm fucked. =) > > >> For some reasons I strongly doubt that your code (or any possible code) > >> can handle this without changes to the C/S protocol. > > > The client/server protocol in the FedOne code base, unless i miss my guess, > > isn't doing OT. > > >> Your application seems to be different anyway. If I am not mistaken (I > >> just read the wave you mentioned) you are running > >> a web client which connects to your web server which connects to FedOne. > >> Right? > > > Heh, no. I'm not using FedOne, just the OT component of FedOne. I'm > > building out the capacity to be able to have gwt web clients running OT sync > > with a webserver. It works, but I lack the theoretical grounding to prove > > it. > > >> The problem I mentioned is between your web server and FedOne. In my case > >> it is between QWaveClient and FedOne. > >> Your web app can of course recover as long as FedOne and your web server > >> are stable. But what happens if your > >> WebServer crashes in an unfortunate moment? Your code will suffer from the > >> very problem I described. > > > If the web server goes down with unsync'd state, everything goes shiny. At > > this point I force the clients to drop all state and reload. > > >> However, would like to be proven wrong here since this would give me a > >> solution to my initial problem :-) > > > Sorta, kinda, maybe. > > >> Greetings > >> Torben > > >> 2010/1/20 Brett Morgan <[email protected]> > > >>> Actually, no, OT deals with this case. My almost working code that I > >>> presented at LCA2010 deals with this edge case. Unfortunately it has bugs, > >>> and dies in the arse randomly. Sigh. > > >>> Wave that I presented from: > > >>>https://wave.google.com/wave/#restored:wave:googlewave.com!w%252BTBvx...<https://wave.google.com/wave/#restored:wave:googlewave.com%21w%252BTB...> > >>> The code: > >>>http://code.google.com/p/wave-ot-editor/source/browse/#svn/wave-ot-ed... > > >>> I can put together a JUnit test case showing that this case actually > >>> stabilises using the Wave OT code, if that would help... > > >>> On Wed, Jan 20, 2010 at 11:40 AM, Torben Weis > >>> <[email protected]>wrote: > > >>>> Hi Brett, > > >>>> thanks for the suggestion. > >>>> However, it seems to me that this approach is not completely correct. > > >>>> Imagine two clients which are sending a delta against the same server > >>>> version. > >>>> The delta says to insert "Hello" at some position in a blip. > >>>> The correct outcome is "HelloHello" being inserted. > >>>> Now one client fails to submit its delta, the other one succeeds. > >>>> The client that failed cannot detect that it failed, because the other > >>>> delta looks exactly the same. Thus, in the end "Hello" will be inserted > >>>> only once. > > >>>> I agree that this is an academic corner case, but I see no solution for > >>>> this > >>>> when relying on delta comparisons. > > >>>> Greetings > >>>> Torben > > >>>> 2010/1/19 Brett Morgan <[email protected]> > > >>>>> If you are transforming your docops, you can compare the docops coming > >>>>> back down for equality. You are doing client side transformations, > >>>>> right? > > >>>>> org.waveprotocol.wave.model.operation.OpComparators is the FedOne code > >>>>> for comparing equality of ops. Which, after a whole bunch of edge case > >>>>> checking turns into the following comparison: > > >>>>> DocOpUtil.toConciseString(a).equals(DocOpUtil.toConciseString(b)) > > >>>>> In short, comparing docops for equality is easy, as long as you keep > >>>>> transforming your docops... > > >>>>> On Wed, Jan 20, 2010 at 9:42 AM, Torben Weis > >>>>> <[email protected]>wrote: > > >>>>>> Hi James, > > >>>>>> How about when the client connects to the server again it does a > >>>>>>> history > >>>>>>> check against the known good deltas it has sent out. If the last > >>>>>>> delta > >>>>>>> it sent out isn't in the history, then it hasn't been received. > > >>>>>> The problem is that this is impossible. How should QWaveClient > >>>>>> recognize a delta as > >>>>>> being its own? The server has perhaps transformed the delta, i.e. > >>>>>> simple delta comparison > >>>>>> is not possible and looking at version numbers does not help either. > > >>>>>> Greetings > >>>>>> Torben > > >>>>>>> -- > > >>>>>>> James Purser > >>>>>>>http://wavingtheshiny.collaborynth.com.au > >>>>>>> Wave Addresses: > >>>>>>> [email protected] (wave.google.com) > >>>>>>> [email protected] (wavesandbox.com) > >>>>>>> [email protected] (collaborynth.com.au FedOne Server) > >>>>>>> Skype: purserj1977 > >>>>>>> GTalk: [email protected] > > >>>>>>> -- > >>>>>>> You received this message because you are subscribed to the Google > >>>>>>> Groups "Wave Protocol" group. > >>>>>>> To post to this group, send email to [email protected]. > >>>>>>> To unsubscribe from this group, send email to > >>>>>>> [email protected]<wave-protocol%2bunsubscr...@goog > >>>>>>> legroups.com> > >>>>>>> . > >>>>>>> For more options, visit this group at > >>>>>>>http://groups.google.com/group/wave-protocol?hl=en. > > >>>>>> -- > >>>>>> --------------------------- > >>>>>> Prof. Torben Weis > >>>>>> Universitaet Duisburg-Essen > >>>>>> [email protected] > > >>>>>> -- > >>>>>> You received this message because you are subscribed to the Google > >>>>>> Groups "Wave Protocol" group. > >>>>>> To post to this group, send email to [email protected]. > >>>>>> To unsubscribe from this group, send email to > >>>>>> [email protected]<wave-protocol%2bunsubscr...@goog > >>>>>> legroups.com> > >>>>>> . > >>>>>> For more options, visit this group at > >>>>>>http://groups.google.com/group/wave-protocol?hl=en. > > >>>>> -- > >>>>> Brett Morganhttp://domesticmouse.livejournal.com/ > > >>>>> -- > >>>>> You received this message because you are subscribed to the Google > >>>>> Groups "Wave Protocol" group. > >>>>> To post to this group, send email to [email protected]. > >>>>> To unsubscribe from this group, send email to > >>>>> [email protected]<wave-protocol%2bunsubscr...@goog > >>>>> legroups.com> > >>>>> . > >>>>> For more options, visit this group at > >>>>>http://groups.google.com/group/wave-protocol?hl=en. > > >>>> -- > >>>> --------------------------- > >>>> Prof. Torben Weis > >>>> Universitaet Duisburg-Essen > >>>> [email protected] > > >>>> -- > >>>> You received this message because you are subscribed to the Google > >>>> Groups "Wave Protocol" group. > >>>> To post to this group, send email to [email protected]. > >>>> To unsubscribe from this group, send email to > >>>> [email protected]<wave-protocol%2bunsubscr...@goog > >>>> legroups.com> > >>>> . > >>>> For more options, visit this group at > >>>>http://groups.google.com/group/wave-protocol?hl=en. > > >>> -- > >>> Brett Morgan > > ... > > read more »
-- You received this message because you are subscribed to the Google Groups "Wave Protocol" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/wave-protocol?hl=en.
