Hi Tad, What you have written here is more in line with what I understood of the federation protocal where servers act merely as proxies and caches for Waves that they do not own. So all servers should end up with the same state space as you have indicated.
As you note, this does still leave the question unanswerd - what does Google do in their wave client? The recently released Python Wave client code also offers no clues as there is presently a bunch of "TBD" markers in the code where the client would perfrom OT. One thing that is clear is that clients will apply operations is different orders, so TP1 must be met. It will be interesting to see what the community comes up with on the client side as it is much more complex than what the server has to do. I wonder how long it will take before a correct implementation is developed! Cheers, Dan Tad Glines wrote: > I see the problem here. You think I'm still talking about site identifiers. > > My very first reply was about site identifiers. And we both ended up > being correct. I was correct in that wave OT doesn't use explicit site > identifiers. You where correct in that wave OT probably uses "implied" > site identifiers (client and server). > > I then read your blog in which you state that the server sends > transformed deltas to the client. My subsequent posts mostly focused > on the fact that the server doesn't send transformed deltas (we'll > ignore the "toy" client). Your blog is very well written and gives a > good detailed description of how OT works. The only discrepancy is > that the server doesn't send transformed delta's to the client > (federation remote). It sends the original un-transformed delta. > > I just did another review of the FedOne code and cleared up another > assumption I had made. The federation remote doesn't do OT the way we > had assumed. When a delta originates from the remote (client), the > delta passes through the remote (without OT) and is sent to the host. > > If we start with: > > Host [O1, O2, O3] > Remote1 [O1, O2, O3] > Remote2 [O1, O2] > > where: > > Remote1 has sent Oa > Remote2 has sent Ob > > When Host gets Oa it will not do OT and will apply it directly then > send it to Remote1 and Remote2. > When Host gets Ob it will transform it against O3 and Oa then send Ob > to Remote1 and Remote2. > > When Remote2 gets Oa it will notice that it is missing O3 and will > request it from the Host. Regardless of the order in which O3, Oa and > Ob arrive, Remote2 will optionally transform and apply them in the > order specified in the "applied_at" version of each delta. In this > example, O3 and Oa will be applied with out transformation and Ob will > be transformed against O3 and Oa before being applied. > > If Remote1 gets Ob first it will store it and wait for Oa before > applying Oa, transforming Ob against O3 and Oa and then applying Ob'. > > The resulting state space is: > > Host [O1, O2, O3, Oa, Ob'] > Remote1 [O1, O2, O3, Oa, Ob'] > Remote2 [O1, O2, O3, Oa, Ob'] > > This still leave the question of how Google handles OT in their client. > > -Tad > > On Tue, Dec 1, 2009 at 5:26 PM, Daniel Paull <[email protected]> wrote: > > Hello Tad, > > > > Following what you just wrote: > > > > Remote1 will end up with [O1, O2, O3, Oa, Ob'], where Ob' is IT( Ob, > > Oa ), and, > > Remote2 will end up with [O1, O2, O3, Ob, Oa'], where Oa' is IT( Oa, > > Ob ) > > > > So, as per my previous message, for Remote1 and Remote2 to converge to > > the same document state, then [Oa, Ob'] must have the same effect as > > [Ob, Oa']. Note that this is exactly what TP1 states. > > > > Please explain how convergence is possible without resorting to site > > identifiers (either explicit or implied) in the case of inserts at the > > same position, as per the traditional OT transformation functions. > > > > Perhaps you could write down what you think the transformation > > function is for transofrming an insert operation past another insert > > operation. > > > > Cheers, > > > > Dan > > > > > > Tad Glines wrote: > >> For purposes of OT, the federation remote is the client. And, in > >> FedOne, the federation host (the server) does not send transformed > >> deltas to the federation remote (the client). > >> So, if Oa is sent form Remote1 to the Host, then the Host will sent Oa > >> (and not Oa') to Remote2. > >> > >> On Tue, Dec 1, 2009 at 4:07 PM, Daniel Paull <[email protected]> wrote: > >> > My understanding is that the FedOne client/server interaction is > >> > nothing like what is described in the Google white paper, so it's not > >> > a good idea to use that as a reference. For example, the FedOne > >> > client does not do any OT, it does not receive an ACK from the server, > >> > etc, etc. As an example client/server implementation it is incomplete > >> > at best. > >> > > >> > Let's look at the state spaces you posted, but I will simplify to only > >> > two remote sites: > >> > > >> > Host [O1, O2, O3] > >> > Remote1 [O1, O2, O3, Oa] > >> > Remote2 [O1, O2, O3, Ob] > >> > > >> > Assuming order of arrival is Oa, Ob > >> > > >> > Host [O1, O2, O3, Oa, Ob'] > >> > Remote1 [O1, O2, O3, Oa, Ob'] > >> > Remote2 [O1, O2, O3, Ob, Oa'] > >> > > >> > For Remote1 and Remote2 to converge to the same document state, then > >> > [Oa, Ob'] must have the same effect as [Ob, Oa']. Note that this is > >> > exactly what TP1 states. > >> > > >> > Now, if Oa = ins( "Foo" ) and Ob = ins( "Bar" ) (ie, both insert at > >> > position 0) then you need to show that both [Oa, Ob'] and [Ob, Oa'] > >> > give thee same resulting document state, which will be either "FooBar" > >> > or "BarFoo". Please list an algorithm that can achieve this without > >> > resorting to site identifiers. > >> > > >> > Regarding site identifiers, the Wave protocol there really are only > >> > two sites involved - the client and the server. As such, no site > >> > identifiers are required as they can be implied. Consider code like > >> > the following from transformer.java: > >> > > >> > while (clientIndex < clientOp.size()) { > >> > clientOp.applyComponent(clientIndex++, clientTarget); > >> > while (clientPosition.get() > 0) { > >> > serverOp.applyComponent(serverIndex++, serverTarget); > >> > } > >> > } > >> > while (serverIndex < serverOp.size()) { > >> > serverOp.applyComponent(serverIndex++, serverTarget); > >> > } > >> > > >> > I expect that the line that states "clientPosition.get() > 0" gives > >> > you the traditional ordering on site id. If the code used ">=" rather > >> > than ">", then the ambiguous cases, such as inserts at the same > >> > position, would be resolved the other way around. > >> > > >> > > >> > Cheers, > >> > > >> > Dan > >> > > >> > > >> > On Dec 2, 3:06 am, Tad Glines <[email protected]> wrote: > >> >> Not a problem. I hadn't even noticed that the e-mail was not going to > >> >> the list. > >> >> > >> >> I read your blog. I don't know about Google's client implementation, > >> >> but the FedOne implementation doesn't work as you described it. > >> >> > >> >> The "toy" client doesn't perform OT at all. It sends the delta > >> >> directly to the server without applying it locally. And only applies > >> >> (composition no transformation) the transformed deltas that are sent > >> >> from the server. This means that the client won't display the > >> >> submitted text until the server has transformed and returned it. > >> >> > >> >> In the server-to-server case, only the original delta is transmitted. > >> >> The ProtocolAppliedWaveletDelta message contains the original, > >> >> un-transformed, delta and hashed version at which it was applied. > >> >> > >> >> Host [O1, O2, O3] > >> >> Remote1 [O1, O2, O3, Oa] > >> >> Remote2 [O1, O2, O3, Ob] > >> >> Remote3 [O1, O2, O3, Oc] > >> >> > >> >> Assuming order of arrival is Oa, Ob, Oc > >> >> > >> >> Host [O1, O2, O3, Oa, Ob', Oc'] > >> >> Remote1 [O1, O2, O3, Oa, Ob', Oc'] > >> >> Remote2 [O1, O2, O3, Ob, Oa', Oc'] > >> >> Remote3 [O1, O2, O3, Oc, Oa', Ob'] > >> >> > >> >> > >> >> > >> >> On Mon, Nov 30, 2009 at 7:15 PM, Daniel Paull <[email protected]> > >> >> wrote: > >> >> > Hello All, > >> >> > >> >> > It appears that I pressed the "reply to author" button rather than > >> >> > replying to this group this morning. My message and Tad's reply (Tad > >> >> > - I'm sure you'd be happy to have this published to the group) can be > >> >> > found below. Apologies for the confusion. > >> >> > >> >> > Tad - operations are executed in different orders on the server and > >> >> > client (lets forget the federation of servers as this is not what the > >> >> > OP was asking about). They must be executed in different orders since > >> >> > the client applies operations before sending them to the server, so > >> >> > operations concurrently performed by other clients will arrive after > >> >> > the local operation has been applied. This can even be seen in the > >> >> > diagram in the Google OT whitepaper - the server and client take > >> >> > different "OT paths", meaning that the client and server have applied > >> >> > operations in different orders. > >> >> > >> >> > You may also like to read my blog entry here: > >> >> >http://www.thinkbottomup.com.au/site/blog/Google_Wave_Operational_Tra... > >> >> > >> >> > As that might help you understand how clients will apply concurrent > >> >> > operations in different orders. > >> >> > >> >> > Cheers, > >> >> > >> >> > Dan > >> >> > >> >> > From Tad's email: > >> >> > >> >> > You're correct the result would be either "1716" (A first) or "1617" > >> >> > (B first). I should have remembered the way that works from my > >> >> > previous tests with wave OT. > >> >> > >> >> > However, Wave doesn't use server ID's in the way you mentioned. All > >> >> > delta's are sent to the federation host first, before being sent (by > >> >> > the fed host) to all other participating servers. So, while federation > >> >> > remote servers also perform OT, they do it in a fixed order as > >> >> > determined by the federation host. No server ID based ordering is > >> >> > necessary. > >> >> > >> >> > On Mon, Nov 30, 2009 at 4:58 PM, Daniel Paull <[email protected]> > >> >> > wrote: > >> >> > >> >> >> Tad, > >> >> > >> >> >> I don't think you're right at all! > >> >> > >> >> >> Clearly to preserve the intention of both users, the resulting > >> >> >> document must be wither "1617" or "1716" (assuming they delete two > >> >> >> characters and insert two characters. I had assumed that they just > >> >> >> deleted and inserted one character, so the result would be "167" or > >> >> >> "176". But this is a moot point.) > >> >> > >> >> >> If two operations (O1 and O2) happen concurrently, the they one must > >> >> >> be transformed to include the effect of the other in order to keep a > >> >> >> linear history of operations (ie, the state space or history buffer). > >> >> >> However, whether the decision is to order the operations as [O1, O2'] > >> >> >> or [O2, O1'], the resulting document state MUST be the same. This > >> >> >> is > >> >> >> the fundamental axiom of OT. Research and understand the TP1 > >> >> >> constraint for transformation operations. The link I provided in my > >> >> >> previous post to OT Functions in wikipedia should help you with this. > >> >> > >> >> >> If the order in which concurrent operations arrive at the server > >> >> >> affects the document state after those operations have been applied, > >> >> >> then the OT implementation is very, very broken. > >> >> > >> >> >> Cheers, > >> >> > >> >> >> Dan > >> >> > >> >> > -- > >> >> > >> >> > 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 > >> >> > athttp://groups.google.com/group/wave-protocol?hl=en. > >> > > >> > -- > >> > > >> > 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. > >> > > >> > > >> > > > > > -- > > > > 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. > > > > > > -- 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.
