Operational Transformation algorithm
On Tue, Jun 11, 2013 at 12:34 AM, Upayavira <u...@odoko.co.uk> wrote: > For the uninitiated, what is OT? > > Upayavira > > On Mon, Jun 10, 2013, at 09:53 PM, Michael MacFadden wrote: > > Dave, > > > > Thanks for your thoughts. A few things to consider. There is a > > distinction between P2P messaging and P2P OT. A system could reasonable > > have a client server messaging architecture where the server is a hub and > > the clients are spokes. All messages from one client flow through the > > server to get to other clients. However, even in this arrangement OT can > > still happen in a P2P mode. If the server is simply acting as the > > messaging relay and doing no OT, then the OT can happen at the clients. > > > > Googles Wave leverages client-server messaging AND client-server OT. > > That > > is the server is participating in the OT. OT only happens in paris > > between the client and the server. > > > > In terms of mobile devices, unless we are talking about some form of > > bluetooth or local wifi, then it is likely that messaging with be client > > server. However, how OT happens is up for debate. > > > > There are pros and cons to doing OT in a client-server or P2P manner. > > Googles view was that if you have potentially hundreds or thousands of > > collaborators, then in a P2P mode you wind up with state vectors, vector > > clocks, or context vectors that are just to large. Each peer has to > > track > > the state of each other client. Operations typically have a context > > vector attached to them. In this case you have context vectors, and > > state > > tables that grow out of hand. Google chose to avoid this by using a > > client server OT model. > > > > I think that saying that the wave algorithm doesn't satisfy TP2 is a bit > > inaccurate. I believe it does satisfy TP2 in that three clients can > > still > > make concurrent edits to the document state. The server simply chooses > > to > > canonically order these in order to ensure that TP2 is honored. One > > could > > argue that the wave algorithm satisfies TP2 by never letting the > > situation > > arise in the first place, but in my view this still satisfies the > > requirement. > > > > FYI, I have worked extensively with Wave's OT, other systems OT > > algorithms, and have been working closely with the researchers who are > > working OT right now. I think this is a very good discussion. One I can > > bring to the larger OT community if we so desire. > > > > ~Michael > > > > On 6/10/13 9:38 PM, "Dave" <w...@glark.co.uk> wrote: > > > > >[John B - I wasn't sure where else it would be appropriate to ask this > > >question, but please forward on anywhere you think it appropriate] > > > > > >There are many things about Wave and WIAB that I would like to see > > >improved / changed, but based on my readings I've been content with the > > >TP1 OT approach chosen by google (not that I'm even close to an expert) > > >- even if the WIAB implementation would benefit from some love. > > > > > >But one of the things mentioned in the recent wave-forward hangout was > > >the weakness in Wave's OT implementation for a required canonical > > >version of a given wave (providing absolute ordering of changesets). > > >Specifically, this effectively prevents 3 party P2P messaging where > > >there isn't guaranteed to be that one canonical ordering. My > > >understanding is that Joseph is playing with some alternative OT > > >algorithms that are TP2, and therefore don't require arbitration of > > >changeset order. This was specifically called out as an advantage to > > >support P2P messaging and running the full stack on a phone. > > > > > >That got me thinking - why would you want to do that? What are the > > >benefits of P2P messaging, and are there other reasons to need TP2? > > > > > >Most of the messaging and collaboration systems I could think of are > > >client-server (some with federated servers) and Wave/WIAB support this > > >with TP1. Most networked phone apps that I'm aware of are also > > >client/server, and at first glance this seems a good thing - it makes > > >addressing easier and avoids issues with intermittent connectivity. The > > >ability to have a simple "wavelike" server (and detached clients) > > > > > >I suspect I'm missing something, and I wondered if I'm alone? > > > > > >My understanding is that technical interop between the various wave-like > > >communities will need us to use the same OT alogrithm (eventually), so > > >clarity on the pros/cons of keeping or changing the wave OT approach > > >would be a good first step in that direction! > > > > > >Dave > > > > >
