On Dec 2, 9:26 am, 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.
The following is my theory on how it might work...
I will use client/server terminology as applicable to the Google Wave
white paper on OT.
Let client A generate
Oa = ins(0, "Foo")
and client B concurrently generates
Ob = ins(0, "Bar").
Let there be a *single* server.
The globally unique order in which the operations arrive and are
processed by the server provides the means to break symmetry – and is
an alternative to the use of site identifiers described in the
literature.
The trick is for server and client to use *different* Inclusion
Transforms for the case of insertions at the same position! Let the
server use Ts(O1,O2) and every client use Tc(O1,O2).
For example:
Ts(ins(p1,c1),ins(p2,c2)) :-
if (p1 < p2) return ins(p1,c1)
else return ins(p1+1,c1)
Tc(ins(p1,c1),ins(p2,c2)) :-
if (p1 <= p2) return ins(p1,c1)
else return ins(p1+1,c1)
Note that Ts uses '<' whereas Tc uses '<=' in the comparison of
insertion positions. The other way around would work as well. It
would need to be specified in a precise definition of the protocol.
Let the server receive Oa before Ob. Since Oa || Ob the server will
need to transform Ob to Ob’ = Ts(Ob,Oa).
According to the white paper, the server sends *transformed* versions
of operations to the client. So Ob’ not Ob is sent to client A.
Client A doesn’t need to transform Ob’ because it already includes Oa
in its context. Alternatively if untransformed Ob is sent to client
A, then client A will need to calculate Ob’ = Ts(Ob,Oa), which is
confusing.
The server also sends Oa to site B. Since Oa || Ob, client B will
need to transform Oa to Oa' = Tc(Oa,Ob).
Convergence is achieved because:
[Oa Ts(Ob,Oa)] ~ [Ob Tc(Oa,Ob)]
where ~ denotes the equivalence relation on lists of operations
(according to whether they produce the same final state).
Strictly speaking, the Google Wave approach doesn't involve a (single)
Inclusion Transformation function that satisfies TP1 (never mind TP2).
--
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.
