On Feb 28, 1:02 pm, Tad Glines <[email protected]> wrote:
>
> I've been working on implementing branching and merging using the wave OT
> code. My code passes a fairly simplistic test but I need to do more testing
> to see if there are any limitations.
>
Let's define branching as maintaining multiple streams of operations
that stem from the some common point in the history of operations
recorded by the server. For example, if the server's history is:
[O1, O2, O3, O4, O5, O6]
Then I might branch from O3 and generate Oa, Ob and Oc. Now the
server's history of operations is like the following (I was going to
draw a tree in ASCII art, but I expect it would be confusing when it
does not render properly with different fonts - I hope the following
make sense - B1 and B2 are branches):
Ocommon = [O1, O2, O3]
B1 = Ocommon + [O4, O5, O6]
B2 = Ocommon + [Oa, Ob, Oc]
In terms of OT, the operations O4, O5 and O6 appear to be concurrent
with respect to Oa, Ob and Oc.
Let's define a pair-wise merge of B2 onto B1 to be B1 plus the
operations from B2 less the common prefix. Of course, the operations
from B2 need to be transformed as part of this merge. For example,
merging B2 onto B1 would result in:
[O1, O2, O3, O4, O5, O6, Oa', Ob', Oc']
where [Oa', Ob', Oc'] = IT( [Oa, Ob, Oc], [O4, O5, O6] )
Note that if we instead merge B1 onto B2, we will get operations in
different orders:
[O1, O2, O3, Oa, Ob, Oc, O4', O5', O6']
where [O4', O5', O6'] = IT( [O4, O5, O6], [Oa, Ob, Oc] )
Let's emulate the TP2 puzzle that I noted in an earlier message, but
this time using branches rather than clients generate concurrent
operations. Let's start with a document whose state is "X" and create
three branches and generate one operation on each branch (note that
the common prefix is empty, so we can drop it from the above equations
for the sake of simplicity).
B1 = [O1] O1 deletes the "X"
B2 = [O2] O2 inserts "A" before the "X"
B3 = [O3] O3 inserts "B" after the "X"
If we wanted to merge all three branches together, then we need to
perform two pair-wise merges. For example, merge B1 onto B2 to form a
new branch (which we will call B4) and then merge B3 onto B4:
B4 = merge( B1, B2 ) = [ O2, O1' ]
B5 = merge( B3, B4 ) = [ O2, O1', O3' ]
B5 is the final merged result. More concisely, we can write this as:
merge( B3, merge( B1, B2 ) ) = [ O2, O1', O3' ]
There are 6 possible pair-wise merges that can be done in order to
merge all three branches together. All of these merges must provide
the the same final document state. However, just like in the TP2
puzzle, there are two of the six paths that may give an erroneous
result if TP2 is not satisfied. These are as follows:
merge( B3, merge( B2, B1 ) ) = [O1, O2', O3'], and
merge( B2, merge( B3, B1 ) ) = [O1, O3'', O2'']
As described previously when talking about the TP2 puzzle, the two
transformed inserts appear to be at the same position. Breaking this
tie can lead to producing either "AB" or "BA" as the final document
state. This ambiguity leads to divergence between branches where no
divergence should occur. Of course, if the OT functions satisfied
TP2, then no divergence would occur. Note that this is irrespective
of whether a client/server architecture is used or not.
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 at
http://groups.google.com/group/wave-protocol?hl=en.
