Hi, all. The initial discussion of this thread seems due to the absence of "replace (update) operation". John Barstow may be confusing the sequence of delete and insert operations as a replace operation.
It might be true that only insert and delete operations are enough to edit text documents. However, if we need to update some complicated objects such as graphical object and want to change minor attributes of them, such as color or position, replace operation will be demanded. As we saw in the examples, if a sequence of delete and insert operations emulates such replace operation, multiple objects will be obtained. Does the Google wave have any plan for the OT algorithm to support the replace operation? Hyun-Gul 2009/12/2 Brett Morgan <[email protected]> > I just want to clarify here that by "client", you are talking about > the remote wave servers, not the traditional usage of the term client, > for example of web client that displays content from a wave server. > > The many uses of the term client in this context are going to lead to > people becoming confused if we are not careful. > > On Dec 2, 3:35 pm, Daniel Paull <[email protected]> wrote: > > The FedOne source does not implement server acknowledgements, nor does > > the FedOne example client perform any OT, so reading the FedOne source > > is not going to help at all. The only information that exists at this > > point in time on how the client and server interact is in the Google > > OT white paper. > > > > Dan > > > > Brett Morgan wrote: > > > Dan, > > > > > The basis of this is already in the published FedOne source. You could > > > check what they have done instead of trying to figure out what they > > > should have done. > > > > > brett > > > > > On Dec 2, 2:19 pm, Daniel Paull <[email protected]> wrote: > > > > Oops - forgot the important bit! The Google OT White paper states: > > > > > > "When a server acknowledges a client's operation, it means the server > > > > has transformed the client's operation, applied it to the server's > > > > copy of the Wavelet and broadcasted the transformed operation to all > > > > other connected clients." > > > > > > So, unless that is in error, transofrmed operations are sent from the > > > > server to the clients. > > > > > > It seems crazy to send to original, untransformed operation to the > > > > clients as the clients will have to repeat the transformation work > > > > that the server has already done! > > > > > > Dan > > > > > > Daniel Paull wrote: > > > > > 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. > > > > ... > > > > 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]<wave-protocol%[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.
