I think you might take a look at this - https://github.com/campadrenalin/ConcurrenTree. ConcurrentTree is an attempt to create "dsitributed" tree of OT nodes that can receive operations in any order.
On Tue, Jun 11, 2013 at 1:53 AM, Michael MacFadden < michael.macfad...@gmail.com> wrote: > As a follow up. While technically wave satisfies TP2 (in some regard) > there are some other issues with the way it does so. Good info can be > found here: > > http://www.thinkbottomup.com.au/site/blog/Google_Wave_Intention_Preservatio > n_Branching_Merging_and_TP2 > > > And > > http://www.corvalius.com/blog/index.php/technology/dissecting-googles-wave- > technology/ > > > On 6/10/13 11:28 PM, "Dave" <w...@glark.co.uk> wrote: > > >Michael, > > > >On 10/06/13 21:53, 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. > > > >Good point. > > > >> 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. > > > >ok - I guess this is the what I was really asking. What are the > >advantages of doing OT in a 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'm not familiar enough with Wave's code, but these sound like valid > >design choices, even more so when aiming for a client on a phone or > >phone like device? > > > >I guess having the server participate in OT also seems instinctively > >more natural to me, so I'm trying to get up to speed with why a > >wave-like system would benefit from P2P / TP2 style OT. > > > >> 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. > > > >Perhaps my understanding of the differences between TP1 and TP2 is > >incorrect? I thought TP1 resolved the three-way conflict by breaking it > >down into two pairs (A+B = AB, AB+C = ABC), where TP2 also effectively > >allows multiple changesets without implying order(so A+B+C = A+C+B = > >C+B+A etc.). > > > >Both allow 3 or more participants, but TP1 requires changes to be merged > >one at a time, which wave implements with a canonical ordering of > >changesets. TP2 removes the requirement for a canonical ordering, and > >allows the changesets to be applied in any order, with a guarantee that > >once all changes are merged, the final document will be the same - > >irrespective of the order the changes were applied. > > > >> 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 > >> > >> > > > > >
